Cs234 lecture 3 model free policy evaluation
Def: Policy Evaluation is computing the value of all states given a particular policy $\pi$. Policy evaluation can be wither model-based (requires the transition and reward probabilities) or model-free (does not require information about transitions and rewards)
Recall from Lecture 2: Model-Based Dynamic Programming Iterative Method for Policy Evaluation For $k$ = 1… until convergence; For all states s:
-
$V_k^\pi(s) = R^\pi(s,\pi(s)) + \gamma \sum_{s’ \in S} P^\pi(s’ s, \pi(s))V^\pi_{k-1}(s’)$
In Dynamic Programming, we use $V^\pi_{k-1}(s’)$ as an estimate for the actual value of the reward at state $s’$. This estimation is called bootstrapping (Appendix 1).
Cons:
- Requires assumption that state is Markov.
- This is model-based: requires an explicit model of the reward function.
Model Free Policy Evaluation
Def: Episode: A complete sample of a policy on the MDP until termination. Def: Below, let $G_{i,t} = \sum_{t’ = t}^\infty \gamma^{t’-t}r_{t’} = r_{i,t} + \gamma r_{i,t+1} + \cdots $ be the expected reward for episode $i$ starting at time $t$.
Monte Carlo Policy Evaluation
Simulate the policy many times and average rewards recieved. Several variants exist (Appendix 2). This is performed once per episode. The value of every state is updated once the episode is completely sampled through. The most common variant for the update used is incremental every-visit MC, which performs the incremental update $V^\pi(s) = V^\pi(s) + \alpha (G_{i,t} - V^\pi(s))$ for each sampled episode. $t$ in $G_{i,t}$ refers to the time when a particular state was seen according to some update rule in the episode, but the updates occur after the episode has already been run through. $\alpha$ is chosen $\ge 1/N(s)$ where $N(s)$ is the number of unique states visited so far. Other variants are first-visit MC and every-visit MC (Appendix 2).
(Note: We can apply the same Monte Carlo update, but to learn the state-action value function (aka Q function) instaed of the V function. In this case the update is This is the policy evaluation step used in Monte Carlo Control.)
Pros: Does not assume state is Markov.
Cons:
- Requires episodic settings (processes must terminate). In particular cannot handle settings with self-loops.
- Generally a very high variance estimator, and reducing variance can require a lot of data.
- Slow to update: Only one update every episode.
Temporal Difference (TD) learning
This is the most popular method of the three. It is a combination of Monte Carlo and Dynamic Programming Methods. We sample episodes, but instead of updating at the termination of each episode, for every time step $(s_t,a_t,r_t,s_{t+1})$ we observe in every episode we perform the bootstrapped update
Pros: Updates are applied much faster, after every action instaed of every episode, so generally much lower variance than Monte-Carlo Methods. Since we also bootstrap, TD can be used in episodic or infinite-horizon cases.
However, TD updates can take a bit longer to propagate than Monte Carlo, because you only update your reward for the state that you’re currently in. You don’t backpropagate the reward information to states that you previously visited, which happens in Monte Carlo.
(Note: We can apply the same TD update, but to learn the state-action value function (aka Q function) instaed of the V function. In this case we need to observe $(s_t,a_t,r_t,s_{t_1}, a_{t+1})$, and the update is This is the policy evaluation step used in SARSA.)
TD[0] is bootstrapping after the first reward, TD[1] is boostrapping after the second reward, etc.
Summary of the Three Methods:
(See Appendix 3 for a case where MC/TD give different results)
Rationale: DP and TD use bootstrapping. This handles onn-episodic domains, but is a biased estimate of value and requires the Markov Assumption.
DP is model-based learning (needs transition model), whereas MC/TD is model-free and requires no models. All three have convergence guarentees.
Tradeoffs:
If the world is not Markovian, you don’t want to make the Markov assumption and get wrong results, so Monte Carlo is better.
If the world is Markov, TD is a lot faster.
(TD[0] converges to DP policy V^\pi for the MDP with the maximum likelihood estimates for teh dynamics and the reward model)
Appendix 1: Policy Evaluation - Dynamic Programming
Note that in the Dynamic Programming method we are bootstrapping the future expected rewards by using $V_{k-1}^\pi$ as a stand-in for the sum of future rewards. In policy evaluation, this is precise (not an estimate) because we are in the model-based case, but in the model-free case generally using this substitution would be a biased estimate.
** **
Appendix 2: Variants of Monte Carlo Policy Evaluation
No bias becuase the state information you use is iid.
(Equivalent Formulation to Every-visit Monte Carlo)
If you go to a state multiple times in every episode, your returns are correlated so it’s no longer iid. But its still consistent and has a lot lower variance.
Appendix 3: Different between the three methods for model-free policy evaluation:
The above supposes the online case- being able to sample the above observations many many times, and perfomring updates each time.
V(A) = 0 in ML estimation, but V(B) = 3/4 in TD estimation.
Appendix 4: Stats Recap
Mean Squred Error is Bias^2 + Variance