Understanding Monte Carlo Algorithms for Reinforcement Learning with a Blackjack Case Study

Introduction

Reinforcement learning (RL) requires an agent to learn optimal policies from reward feedback in complex environments. When the environment dynamics are unknown, model‑free methods such as Monte Carlo (MC) become essential.

Model‑Free vs Model‑Based

Model‑based RL uses a transition model p(s',r|s,a) for planning, while model‑free RL learns directly from sampled state‑action‑reward trajectories. MC belongs to the model‑free class because it does not estimate or use p(s',r|s,a).

V‑Function Estimation with MC

For episodic tasks, the value V(s) is estimated as the average return following the first (first‑visit MC) or every (every‑visit MC) occurrence of state s in an episode. Both methods converge to the true V(s) as the number of episodes grows.

Using the classic Blackjack (21) game, the state space is defined by the player’s sum (12‑21), a boolean indicating a usable ace, and the dealer’s visible card (2‑11), yielding 200 states. Monte Carlo simulations (e.g., 5 million episodes) produce heat‑maps of V(s) for a “stick at 20” policy, showing that conservative policies perform poorly except when the player holds 20 or 21, and that states with a usable ace have higher values because the ace can be counted as 1 to avoid busting.

Q‑Function Estimation

Extending MC to action‑value estimation, each state‑action pair (s,a) is treated as a new “state”. For Blackjack there are 200 × 2 = 400 (state,action) pairs. A random policy (50 % hit, 50 % stick) yields Q‑function heat‑maps where actions with a usable ace dominate, while hit actions at high sums (e.g., 21) have Q = ‑1 because they always bust.

Exploration vs Exploitation

Monte Carlo methods can suffer from insufficient exploration when a deterministic policy repeatedly selects the same action, leaving many state‑action pairs unvisited. This classic exploration‑exploitation dilemma can be mitigated by strategies such as explicit‑start (launching multiple episodes from each (s,a) pair) or random‑start (sampling initial states uniformly). Random‑start is simple but may create a distribution mismatch between training data and the true environment, leading to sub‑optimal policies.

Conclusion

Monte Carlo algorithms provide model‑free value and action‑value estimation without requiring transition models, offering state‑independent updates, scalable computation, and applicability to large‑state problems. The next step is to address the exploration‑exploitation trade‑off, for example with ε‑greedy policies and improved start‑state techniques.