RL 05: Model Free Control

• On policy vs Off policy: Learning on the job vs learning while using someone else’s policy
• In most real problems,
  • MDP model is unknown - but experience can be sampled.
  • MDP model is known - but is too big to use, except by sampling, so it doesn’t matter anyway.
• On policy learning:
  • Learn on the job
  • Learn about policy $\pi$ from experience sampled from $\pi$ - sample actions from it while at the same time evaluating the policy.
• Off policy learning:
  • Looking over someone’s shoulder
  • Learn about (evaluate) policy $\pi$ from experience sampled from another behaviour policy $\mu$

On Policy Learning

• Revision: Policy iteration is
  1. Evaluate a policy’s value function
  2. Improve the policy by being greedy on this value function
  3. repeat until convergence to optimal policy

Monte Carlo Control

Monte-Carlo Evaluation

• Can we plug in Monte-Carlo to evaluate value function and then iterate and improve the policy?
• Two problems with this:
  • State Value function evaluation (such as via Bellman expectation backup) needs state transition probabilities - the dynamics model of the MDP. We don’t have that in model-free.
    • Alternative is to use Action value function, evaluate with Monte Carlo for state-action pair values, and then choose a greedy policy, which allows us to do control in a model-free way.
    $${\pi }^{\prime }(s)=\underset{a\in \mathcal{A}}{\mathrm{argmax}}q(s,a)$$
  • But, greedy policy means we may not explore the entire state space - so we may get stuck and not see the states and actions that contribute to the correct estimate of the value function.
    • So instead of being greedy, we choose to be $ϵ$-greedy. We choose the greedy option most of the times, but with a small probability $ϵ$, we choose a completely random action from the set of all actions. $$\pi (a\mid s)=\{\begin{array}{ll}\frac{ϵ}{m}+1-ϵ& \text{ if }a=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{q}_{\ast }(s,a)\\ \frac{ϵ}{m}& \text{ otherwise }\end{array}$$
    • This, asymptotically, guarantees we will explore all possible actions.
• Just like before in Value Iteration - we can just do a few steps of policy evaluation instead of all the way. What does it look like for Monte Carlo?
  • We improve the policy for each episode - each episode is considered one round of policy evaluation.

GLIE (Greedy in the Limit of Infinite Exploration)

• GLIE entails 2 conditions:
  • You make sure that asymptotically, all state-action pairs are explored infinitely many times.
  • Eventually, the policy converges on a greedy (not just $ϵ$-greedy) policy
• One way to achieve this is to decay $ϵ$ to $0$ with some schedule, say $ϵ=\frac{1}{k}$, $k$ being the number of episode sampled.

GLIE Monte Carlo Control

• Sample $k^{th}$ episode
• Incrementally update the state-action value-function estimate mean for each state-action pair in the sample episode.
• Let new policy be $ϵ$-greedy on this estimated action value function with $ϵ=\frac{1}{k}$
• Your policy will eventually converge to $q_{\ast }(s,a)$

TD Control

v/s MC

• Advantages:
  • TD has lower variance
  • Online
  • Incomplete sequences
• So, the natural idea then is:
  • Apply TD to $Q(s,a)$
  • Use $ϵ$-greedy policy improvement
  • Update every time step instead of every episode.

SARSA: On-Policy Control

• For each episode, initialize $S$, $Q$ (arbitrarily), and $A$ from $Q$ (using $ϵ$-greedy). Then, for each step of the episode:
  1. We start with a state-action pair $S,A$ (no sampling yet)
  2. We want to update $Q(S,A)$ under our $ϵ$-greedy policy.
  3. We take action $A$ and observe/sample from the environment the reward $R$ we get and the state $S^{\prime }$ we end up in.
  4. Sample from our own policy (hence on policy) the next action $A^{\prime }$
  5. Make this update. $Q(S,A)\leftarrow Q(S,A)+\alpha \left(R+\gamma Q\left(S^{\prime },A^{\prime }\right)-Q(S,A)\right)$
  6. Repeat from $(1)$ for the new pair $S^{\prime },A^{\prime }$ in the next step.
• SARSA converges to the optimal policy $q_{\ast }(s,a)$ if:
  • GLIE sequence of policies
  • Robbins-Munro sequence of step-sizes ${\alpha }_t$ - they are not too small and not too large. $$\begin{array}{rl}& \sum _{t=1}^{\infty }{\alpha }_t=\infty \\ & \sum _{t=1}^{\infty }{\alpha }_t^2<\infty \end{array}$$

$n$-step SARSA

Same as $n$-step TD but with state-action-value functions.

• $q_t^{(1)}=R_{t+1}+\gamma Q(S_{t+1})$
• $q_t^{(2)}=R_{t+1}+\gamma R_{t+2}+{\gamma }^{2}Q(S_{t+2})$
• …and so on
• $n$-step return: $q_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\dots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}Q\left(S_{t+n}\right)$
• $n$-step SARSA learning: $$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \times [q_t^{(n)}-Q(S_t,A_t)]$$

SARSA($\lambda$)

• Same as TD($\lambda$) - weighted sum of all $n$-step returns. $$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \times [q_t^{\lambda }-Q(S_t,A_t)]$$
• Again, to keep it online, we can’t do Forward SARSA($\lambda$), because that needs us to go till the end of episode, which may not exist.
  • Again, we build some eligibility traces to do a backward view.

Off-policy Learning

• Evaluate target policy $\pi (a|s)$ while following $\mu (a|s)$
• Why?
  • Learn about the environment through experiences of another agent - including possibly a human.
  • Re-use experiences from another policy.
  • Learn about optimal policy while following exploratory policy (to cover the state-action space better)
  • Learn about multiple policies while following one policy

Q-Learning: Off Policy Control

• We allow both target and behaviour policies to improve.

• Target policy $\pi$ is greedy w.r.t. $Q(S,A)$ and behaviour policy $\mu$ is $ϵ$-greedy w.r.t. $Q(S,A)$

• This means,

  • When choosing what action to take, use the $ϵ$-greedy behaviour policy $\mu$. This ensures exploration.
  • When making an update to the $Q$-value, use the greedy policy $\pi$ for TD target (choose the max $Q$ over all actions in $S^{\prime }$). This ensures optimality.

• For each episode, initialize $S$, $Q$ (arbitrarily). Then, for each step of the episode:

  1. Sample an action $A$ from $Q$ (using $ϵ$-greedy policy $\mu$)
  2. We take action $A$ and observe/sample from the environment the reward $R$ we get and the state $S^{\prime }$ we end up in.
  3. Make this update using $a^{\prime }=\underset{a}{\mathrm{argmax}}Q(S^{\prime },a)$ sampled from our target policy $\pi$ $Q(S,A)\leftarrow Q(S,A)+\alpha \left(R+\gamma \underset{a^{\prime }}{\max }Q\left(S^{\prime },a^{\prime }\right)-Q(S,A)\right)$
  4. Repeat from $(1)$ for the new $S^{\prime }$ in the next step.