2. Monte Carlo Algorithms

Model-Free Prediction

Model-Free Prediction is where we assume we have no knowledge of the transitions and rewards, we learn from actual experiences without prior knowledge of the model. We estimate the value function for all states of the problem using Monte Carlo.

Link to original

Monte Carlo Reinforcement Learning

Monte Carlo Reinforcement Learning

• Generate random rollouts (path through state space)
• Sample and average the returns from state-action pairs
• As number of visits to states increases, $V^{\pi }(s)$ will converge on optimal values

Like Value Iteration, Monte Carlo can use discounted rewards from a given state (Return): $G=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots +{\gamma }^{T-1}{R}_T$ Value function is the expected return of a given state: $v_{\pi }(s)=E_{\pi }[G_t|S_t=s]$

Link to original

Monte Carlo Policy Evaluation

First-Visit Monte Carlo

First-Visit Monte Carlo: average the returns only the first time a state is visited in each episode; if a given state appears again, ignore it.

Link to original

Every-Visit Monte Carlo

Every-Visit Monte Carlo: average the returns following every visit to a state in an episode; count for each subset of the episode that state appears in.

Link to original

Episode (AI)

One episode: full set of state and actions until we reach a terminal state (and utility).

Link to original

Value of state is the average sum for all episodes it appeared in.

Evaluation Example

Consider Markov Decision Process with three states and undiscounted rewards (i.e. $\gamma =1$). Consider three sample episodes: Using First-Visit and Every-Visit, what are $V^{\pi }(s)$ for $A$ and $B$?

First-Visit $V(A)=(5+-5+-5)/3=-1.66$ $V(B)=(0+-3+-3)/3=-2$

Every-Visit $V(A)=(5+2+2+-5+-5)/5=-0.2$ $V(B)=(0+-2+-3+-4+-3)/5=-2.4$

As number of visits (or first visits) to $s\to \infty$, $V^{\pi }(s)$ will converge to the true values. While it yields the correct outcome, the time and compute resource is extensive. Only works in episodic MDPs, given it needs to reach an endpoint (terminate) in order to calculate returns.

Arguably considered the most basic form of reinforcement learning.

Blackjack policy that only sticks on 20 or 21.