[강화학습] CS 234 class 3 & class 4

https://www.youtube.com/watch?v=dRIhrn8cc9w&list=PLRQmQC3wIq9yxKVK1qc0r2nPuInn92LmK&index=3 https://www.youtube.com/watch?v=j080VBVGkfQ&list=PLRQmQC3wIq9yxKVK1qc0r2nPuInn92LmK&index=4 

Model Free Evaluation - Policy Evaluation without knowing how the world works

학습목표

1. Dynamic programming [class 3]
2. Monte Carlo policy Evaluation [class 3]
3. Temporal Difference (TD) [class 3]
4. $ϵ-greedy$ policy [class 4]

1. Dynamic Programming - 세상이 어떻게 돌아가는지 모를때 - reward/ policy algorithm 모를때

• If we knew dynamics and reward model, we can do policy evaluation

[Alg] Dynamic Programming

1. Initialize $V_0^{\pi }(s)=sforalls$
2. For $k=1$  Until converge
3. $\mathrm{\forall }s\in S,V_k^{\pi }(s)=r(s,\pi (s))+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,\pi (s))V_{k-1}^{\pi }(s^{\prime })$

$V_k^{\pi }(s)$  is exactly the k-Horizon value of state s Under policy  $\pi$ 

$V_k^{\pi }(s)$  is an estimate of the infinite horizon value of state s Under policy $\pi$ 

$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|s_t=s]\approx \mathbb{E}[r_t+\gamma V_{k-1}|s_t=s]$

 

2. Monte Carlo

• $G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\dots$ in MDP M under policy $\pi$ 
• $V^{\pi }(s)={\mathbb{E}}_{T\sim \pi }[G_t|s_t=s]$
  • Expectation over trajectories T Generated by following $\pi$ 

• Simple idea : Value = mean return
• If trajectories are all finite, sample set of trajectories & average returns
• Does not require MDP dynamics/rewards -> requires some samples
• Does not assume state is Markov
• Can only be applied to episodic MDPs
  • Averaging over returns from a complete episode
  • Requires each episode to terminate

• Aim : estimate $V^{\pi }(s)$  Given episodes generated under policy $\pi$ 
  • $s_1,a_1,r_1,s_2,a_2,r_2,...$ Where the actions are sampled from $\pi$ 
• $G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+...$ in MDP M under policy $\pi$ 
• $V^{\pi }(s)=\mathbb{E}[G_t|s_t=s]$
• MC computes empirical mean return
• Often do this in an incremental fashion
  • After each episode, update estimate of $V^{\pi }$ 

[Alg] Monte Carlo

1. Initialize $N(s)=0$ : number of times we visited, $G(s)=0,\mathrm{\forall }s\in S$ 
2. Loop
   1. Sample episode $i=s_{i,1},a_{i,1},r_{i,1},s_{i,2},a_{i,2},r_{i,2},...,s_{i,T_i}$ 
   2. Define $G_{i,t}=r_{i,t}+\gamma r_{i,t+1}+{\gamma }^2{r}_{i,t+2}+...+{\gamma }^{T_{i-1}}{r}_{i,T-i}$ as return from time step $t$  Onwards in $i_{th}$  episode
   3. For each time step $t$  Till the end of the episode $i$
      1. If this is the first time t That state s Is visited in episode $i$
         1. Increment counter of total first visits : $N(s)=N(s)+1$ 
         2. Increment total return $G(s)=G(s)+G_{i,t}$ 
         3. Update estimate$V^{\pi }(s)=\frac{G(s)}{N(s)}$  

3. Temporal Difference (TD)

• Monte Carlo 와 Dynamic programming의 융합!
• Model-free
• 아무 상황에서나 다 쓸 수 있음!
• Immediately updates estimate of $V$  After each $(s,a,r,s^{\prime })$  tuple
• Updates and Samples

• Aim: estimate$V^{\pi }(s)$   Given episodes generated under policy $\pi$ 
• $G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+...$ in MDP M under policy $\pi$ 
• $V^{\pi }(s)=\mathbb{E}[G_t|s_t=s]$
• Recall Bellman operator (if know MDP models)
  • $B^{\pi }V(s)=r(s,\pi (s))+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,\pi (s))V(s^{\prime })$
• In incremental every-visit MC, update estimate using 1 sample of return (for the current $i_{th}$episode)
  • $V^{\pi }(s)=V^{\pi }(s)+\alpha (G_{i,t}-V^{\pi }(s))$

• Insight : have an estimate of $V^{\pi }$ , use to estimate expected return
  • $V^{\pi }(s)=V^{\pi }(s)+\alpha ([r_t+\gamma V^{\pi }(s_{t+1})]-V^{\pi }(s))$

[Alg] Temporal Difference

1. Initialize $V^{\pi }(s)=0,\mathrm{\forall }s\in S$
2. Loop
   1. Sample tuple $(s_t,a_t,r_t,s_{t+1})$(s_t,a_t,r_t,s_{t+1})\)
   2. $V^{\pi }(s_t)=V^{\pi }(s_t)+\alpha ([r_t+\gamma V^{\pi }(s_{t+1})]-V^{\pi }(s_t))$

Dynamic ProgrammingMonte CarloTemporal Difference

	Dynamic Programming	Monte Carlo	Temporal Difference
Can use w/out access to true MDP models	o	o	o
Usable in continuing(non-episodic) setting	o		o
Assumes Markov Process	o		o
Converges to true value in limit	o	o	o
Unbiased estimate of value		o
Usable when no models of current domain		o	o

 

4. $ϵ-greedy$ policy

 

explore와 exploit을 균형있게 택하는 방법!

 

a state action value $Q(s,a)$ is

$\pi (s|a)=arg\underset{a}{max}Q(s,a)$ With probability $1-ϵ+\frac{ϵ}{|A|}$ Else random action