Stanford CS234 Lecture 8

Stanford CS234: Reinforcement Learning | Winter 2019 | Lecture 8

Policy-Based Reinforcement Learning

Recall last lecture → where we learned to find state-value($V$) or state-action value($Q$) for parameter $w$(or $\theta$) and use such to build (hopefully)optimal policy($\pi$)

Today we’ll take that policy ${\pi }^{\theta }$ as parameter

$${\pi }^{\theta }(s,a)=P[a|s;\theta ]$$

our goal is to find a policy with maximal value function $V^{\pi }$

Benefits and Demerits

Advantages	Disadvantages
- better converges properties

• works efficiently with high-dimension or continous action spaces
• can learn stochastic policies | - converges to local optima rather than global
• inefficient & high varience |

Stochastic properties needed at aliased environment

• Value-based Rl would take features(combination of actions & is ther a wall?)

$$Q_{\theta }(s,a)=f(\varphi (s,a),\theta )$$

• Policy-based RL would take those features and directly make decisions of action

$${\pi }_{\theta }(s,a)=g(\varphi (s,a),\theta )$$

it the policy were deterministic agent would get stuck anyway at either A or B

whereas stochastic policy leaves probability of moving both directions.

deterministic policy

stochastic policy

Policy Objective Function

our goal is to find best parameter $\theta$ that returns maximal value for given policy ${\pi }_{\theta }(s,a)$

• episodic env(H steps till terminate)

$$J_1(\theta )=V^{{\pi }_{\theta }}(s_1)$$

• continuing env($\text{infin}$)

$$J_{avV}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)V^{{\pi }_{\theta }}(s)$$

*$d^{\pi }$ : stationary distribution of Markov chain

Policy-based RL is an optimization problem!

there sure are gradient-free approaches... simple and precise, even works for undifferentiable, and easy to parallelize. However, it’s extremely sample-inefficient!!!

Policy Gradient

policy gradient is very much like CNN. set $V(\theta )=V^{{\pi }_{\theta }}$, assuming episodic MDPs

we search for local maximum of $V$ with gradient of $\theta$

$$\mathrm{\nabla }\theta =\alpha {\mathrm{\nabla }}_{\theta }V(\theta )$$

where $\alpha$ is learning rate and ${\mathrm{\nabla }}_{\theta }V$ is policy gradient

we compute policy gradient to estimate by Finite Differences method

💡 Finite Difference(유한차분법) → 수치해석 기법으로 미분 근사에 많이 쓰임!(오차 : $O(h^2)$)

Score Function and Policy Gradient Theorem

the Policy vlaue →(probability that we observe a particular trajectory)*(reward of trajectory)

$$V(\theta )=E[\sum _{t=0}^{T}R(s_t,a_t)|{\pi }_{\theta }]=\sum _{\tau }P(\tau ;\theta )R(\tau )$$

the very $\theta$ that maximizes $V(\theta )$ here woul be the optimal $\theta$ we were looking for

$$\arg \underset{\theta }{max}V(\theta )=\arg \underset{\theta }{max}\sum _{\tau }P(\tau ;\theta )R(\tau )$$

take gradient w.r.t $\theta$

$$\begin{array}{ccccccccc}{\mathrm{\nabla }}_{\theta }V(\theta )& =& {\mathrm{\nabla }}_{\theta }\sum _{\tau }P(\tau ;\theta )R(\tau )& =& \sum _{\tau }\frac{P(\tau ;\theta )}{P(\tau ;\theta )}{\mathrm{\nabla }}_{\theta }P(\tau ;\theta )R(\tau )& =& \sum _{\tau }\frac{{\mathrm{\nabla }}_{\theta }P(\tau ;\theta )}{P(\tau ;\theta )}P(\tau ;\theta )R(\tau )& =& \sum _{\tau }P(\tau ;\theta )R(\tau ){\mathrm{\nabla }}_{\theta }P(\tau ;\theta )\end{array}$$

${\mathrm{\nabla }}_{\theta }V(\theta )=\sum _{\tau }P(\tau ;\theta )R(\tau ){\mathrm{\nabla }}_{\theta }P(\tau ;\theta )$

Approximate with empirical estimate for m sample paths

$$
\begin{matrix}
\nabla_\theta V(\theta) \approx \hat{g} = (1/m)\sum_{i=1}^m R(\tau^i) \nabla_\theta P(\tau^i ; \theta)\
=(1/m)\sum^m_{i=1} R(\tau^i) \sum^{T-1}{i=1}\nabla_\theta log{\pi_\theta}(a^i_t|s_t^i)
\end{matrix}
$$

“moving up in trajectory of log probaility of the sample based on its quality→score”

increase weight of things that lead to high reward

Decompose the log term

we call that ${\mathrm{\nabla }}_{\theta }lo{g}_{{\pi }_{\theta }}(s,a)$ the score function

Policy Gradient Algorithms and Reducing Variance

$$
\nabla_\theta V(\theta) \approx (1/m)\sum^m_{i=1} R(\tau^i) \sum^{T-1}{i=1}\nabla_\theta log{\pi_\theta}(a^i_t|s_t^i)
$$

This approximation us unbiased but noisy → high variance! So we approach with two fixes that make it practical

• Temporal structure
• Baseline
• Alternatives to using Monte Carlo returns

Temporal structure

REINFORCE(Monte-Carlo policy gradient)

→ we do all the update and get another episode!

How to compute this differential with respect to policy parameters?

Classes of policies considered

• Softmax → discrete action space

  

  features observed - average feature over the action

• Gaussian → coutinuous action space

  

  이해 잘 안됨...

• Neural network