This chapter describes simulation-based methods to evaluate value functions and state-action value functions, focusing on problems that are sufficiently small so that policies can be represented in tabular form, that is, as a look-up table. Three broad classes of techniques are considered: Monte Carlo methods, temporal differencing, and Q-learning. Numerous variants of these methods are presented. Important trade-offs are considered for each method, including offline vs. online implementation, synchronous vs. asynchronous updating, exploration vs. exploitation, on-policy vs. off-policy recursions, and variance vs. bias. Policy evaluation and optimization using simulation-based methods are presented for episodic models, discounted models, and average reward models. Policy iteration type algorithms are introduced. The chapter concludes with a case study of the queuing service rate control application, comparing simulation-based solutions with those obtained using classical methods from Chapters 5–7.

This chapter presents model-free RL algorithms that learn value functions or policies directly from experience. Q-learning is introduced with updating rules for state–action values. Monte Carlo methods are developed for episodic tasks. The stochastic approximation framework provides mathematical foundations. Temporal difference algorithms bootstrap using value estimates. Q-learning for stochastic MDPs and SARSA for on-policy learning are presented. Multi-step methods interpolate between Monte Carlo and one-step TD.