CS285 | Lecture 4 Introduction to Reinforcement Learning
04 Oct 2022
CS285 Lecture3는 파이토치 관련한 내용이라 생략했다. Lecture 4에서는 MDP가 무엇인지, Markov chain 관점에서의 RL, state value function, state-action value function인 Q function에 대해서 다뤘다. 그 다음 기본적인 RL 알고리즘을 이루는 세개의 파트(generate sample, fit model/estimate reward, improve policy) 다양한 RL algorithm 종류들에 대해 간단하게 훑고, RL algorithm마다 주요하게 생각하는 trade-off, assumption들을 다뤘다.
- [policy] $\pi_{\theta}(a_t\mid o_t)$ : distribution over action $a_t$ condition on observations $o_t$. $\theta$ means that policy depends on a vector of parameter. In Deep RL, we often represent policy as a Deep Neural Network (otherwise, represent object such as value function)
- Imitation learning에서 배웠듯이, observation은 state의 stochastic function이라고 볼 수 있다. (full state를 infer하기 위한 모든 정보를 포함하지 않을 수 도 있는) Fully observed / Partially observed인 경우 모두에 대해 다룰 것이다. -
- Reward function은 기본적으로 scalar valued function으로, 어떤 state / action이 더 나은지 말해준다. (state에만 depend하는 경우도 있다.)
- RL의 Objective는 현재 상태에서 High reward를 받는 Action을 고르는 것이 아닌, Future reward를 고려하는 것이다. (정확히 말하면 accumulated reward).
- state, action, $r(s,a)$, $p(s’\mid s,a)$ 를 MDP(Markov Decision Process)라고 부른다.
Markov Chain에 대해서 먼저 얘기하자.
- State는 discrete할 수도 있고, Continuous할 수 도 있다.
-
Transition operator라고 부르는 이유는 timestep $t$ 에서 state i인 확률 $\mu_{t,i}$이 vector라고 해보자. 그러면 transition prob을 Matrix로 써 다음과 같이 정의할 수 있고, 다음과 같은 식을 쓸 수 있기 때문에 operator라고 한다.
\[\mu_{t+1}=T_{i,j} \vec\mu_{t}\] - state $t$에 대한 확률은 state $t-1$에 conditionally independent하다.
action을 추가하기 위해선 Markov Chain에서 Markov Decision Process로 넘어가야 한다.
- $T_{i,j,k}$를 $\mu_{t+1,i}$를 계산하기 위한 linear operator로 볼 수 있다.
Partially observed MDP에 대한 내용이다.
- 추가적인 두가지 object이 필요하다. Observation space $O$, emission(observation) probability $\varepsilon$.
- Reward function은 동일하다.
- 전형적인 Partially observed MDP 혹은 Palmdp에서는 observation에 근거하여 decision을 하게 된다.
- Policy를 directly하게 학습한다고 가정하자.
- state→policy→action
- (state,action)→transition prob → next state
- MDP에서, trajectory에 대한 prob distribution을 적어 볼 수 있다.
- trajectory는 state와 action의 sequence이다.
- Control problem을 finite horizon이라고 가정하자. (decision making task가 유한번 이뤄진다.)
- Chain rule 을 이용해서 위와 같이 작성할 수 있다.
- $p_{\theta}(T)$ : trajectory를 $T$로 표시한다.
- RL의 Goal은 trajectory distribution에 대한 Expected value of sum of rewards를 maximize 하는 policy를 찾는 것이다.
- MDP를 Markov chain으로도 해석 가능하다.
- action과 state를 묶은 augmented state로 생각하면, augmented state들은 markov chain을 이룬다.
- 우리는 또한 objective를 marginalize out해서 위와 같이 작성할 수 있다. 위와 같이 도출해낸 식은 Infinite horizon case에 적용할때 유용하다.
- Reward가 positive라면 infinite horizon의 경우 objective가 발산할것이다.
- objective를 finite하게 할 방법을 찾아야한다.
- 저 Expected Value를 T로 나누는 것 또한 방법이 될 수 있다. (common한 방법은 아님)
- 나중에 discount라는 개념을 배우면, objective에 대해 finite한 값을 구할 수 있다.
- $s_t,a_t$에 대한 분포인 $p(s_t,a_t)$가 stationary distribution으로 수렴할 수 있나? (single distribution으로 수렴, K가 무한으로 간다면?)
- 만약에 이것이 사실이라면, stationary distribution $\mu$에 대해 $\mu = T\mu$라고 적을 수 있어야 한다.
- ergodicity와 aperiodic한 특성의 가정하에(Markchain의 특성), stationary distribution이 존재한다고 말할 수 있다. (cf, aperiodic = markov chain이 Periodic하지 않다. ergodicity = 모든 state는 다른 모든 state에서 0이 아닌 확률로 모두 접근 가능하다. Ergocity가 중요한 이유는 만약 그렇지 않다면, MDP에서 시작하는 state마다 reachable한 state들이 달라지고, 그것이 의미하는 바는 stationary distribution이 존재하지 않는다 라고 할 수 있다.)
- $\mu$를 찾는 방법은 eigenvalue 1을 갖는 eigen vector를 찾는 것이다.
그래서 이 markov chain을 충분히 forward를 했을때, 결국 $s_t,a_t$에 대한 분포는 $\mu$에 수렴할 것이고, t가 $\infty$으로 간다면, 이 marginal값의 합의 expectation은 stationary distribution $\mu$에 의해 결정될 것이다.
- RL 기저에 있는 basic principle은 expectation을 optimizing하는 것이다.
- expected value는 expectation을 취하는 Function 자체가 discontinuous할 때도 continuous하다. 이 사실은 왜 RL이 미분이 불가능한 objective에 대해 optimize하는 gradient descent와 같은 smooth optimization을 사용할 수 있냐에 대해 이해할때 매우 중요하다.
- 간단한 예를 들어보자. 길에 떨어지면 -1, 길에 유지하면 +1이라고 해보자. 이 예시에서의 reward는 Discontinuity하다. 그리고 각 action들에 대한 확률 분포인 $\theta$가 있다고 하자. (베르누이 분포)
- $\theta$를 고려하면 reward가 smooth해진다.
이제 수업에서 다룰 RL Algorithm들에 대해 다뤄보자.
세가지 basic part로 이뤄진다.
- generate samples : RL은 trial and error를 통해 배우는 모델이다. trial part는 환경에서 policy를 배우기 위해 markov decision에서 Interact하면서 sample들을 모은다. Sample들은 trajectory들이다. 나중에 exploration에 배우겠지만, trajectory distribution에서 조금 벗어난 샘플들을 모을 수 도있다.
- fit model : 어떠한 model을 학습하는 파트이다. model의 dynamics(model based RL) 혹은 value function을 학습한다. 다시말하면 초록박스는 기본적으로 현재 policy, policy가 잘하고 있는지, 어떤 reward를 받고 있는지 등, 어떤 것을 estimate한다.
- improve the policy : policy를 더 좋게 바꾸는 블럭이다.
대부분의 알고리즘들이 위의 세개 파트를 포함하고 있다. 어떤 알고리즘은 이 중 하나가 매우 단순할 수/ 복잡할 수 도 있다.
이것은 이전 슬라이드에 대한 간단한 예시이다. 세개의 trajectory에 대해 evaluate하게되고, sum of their reward를 통해 evaluate하게 된다. 초록박스에서 reward에 대해 summation을 하고, 파란박스에서 gradient를 취하게 된다.
Model based RL procedure에 대해 알아보자. 초록박스에서 어떠한 모델(신경망)을 학습하게된다. 이전 슬라이드의 초록박스에서는 그냥 reward를 summation한 것에 비해, 이 슬라이드는 Network에 fit하게 만든다. (일종의 supervised learning을 사용한다고 보면된다.)
이후의 수업에서 이런것들을 더 자세하게 배울것이다. (RL 알고리즘에 따라 어떤것들이 있는지 설명해주기 위해서 언급한 내용이다.)
어떤 파트가 cheap/expensive할까?.
- 오렌지 박스 : real-world에서 sample들을 모으는 것이라고 하면, 연산에 드는 cost가 매우 expensive할 것이다. mujoco는 실제 시간보다 10000배 빠르기 때문에, cost가 trivial할 것이다.
- 초록 박스 : policy를 단순히 reward를 합치는 것에 의해서 estimate한다면 trivial할 것이지만, Neural Net으로 모델을 estimate(train)한다면 expensive할 것이다.
- 파란 박스 : 한번의 gradient step을 하는 것이라면 매우 cheap하겠지만, model와 policy에 대해 backprop해야 된다면 expensive할 것이다.
e.g) Q-learing과 같은 경우 대부분의 내용이 초록박스에 대한 내용이고, 파란박스에서는 단순히 argmax를 사용한다.
Value function에 대해 배워보자. RL algorithm을 디자인 할때 혹은 개념적으로 RL objective를 생각할때 중요한 개념이다.
RL의 objective는 expectation으로 정의될 수 있다. Chain rule을 이용해서 nested Expectation을 두번째 줄처럼 $E_{s_1~p(s_1)}[…\mid s_1]$에 대해 작성해볼 수 있다. Q)만약 위의 가로에 있는 저 파트를 안다고 하면 어떻게 될까? 이것을 $Q(s_1,a_1)$이라고 해보자. 만약 $(s_1,a_1)$에 대한 Q값을 안다고 하면, first time step에서 policy를 최적화하는 것은 매우 쉬워진다. 모든 action을 취해보고 가장 큰 Q를 주는 action을 고르고, 해당 action에 100%의 확률을 주면 된다.
$Q^{\pi}(s_t,a_t)$에 대한 저 식이 Q에 대한 정의이고, $(s_t,a_t)$에서 시작해서 남아 있는 시간에 대해 policy를 roll out한 것의 expected sum of reward를 뜻한다.
매우 유사한 개념인 Value function도 정의해보자. Q와 다른것은 $state$에 대해서만 condition on 되어있는 것이다. $V^{\pi}(s_t)$는 state $s_t$에서 시작해서 policy를 roll out한것의 expected sum of reward를 의미한다. Value function은 또한 expected value over action of Q function으로 정의될 수 있다. $s_1$으로부터의 expectation of value function이 전체 RL의 objective라고 볼 수 있다.
Q function과 Value function들을 어디에다가 쓸까?.
- Idea1이 policy iteration algorithm의 가장 기본적인 원리이고, 이것을 이용해서 q-learning algorithm을 유도해낸다. $\pi$가 어떤것인지 상관없이, 항상 $\pi$를 향상시킬 수 있다.
- Idea2는 policy gradient를 배울 다음 수업에서 다루는 내용이다. Good action a의 prob을 증가시키기 위해 gradient를 계산한다. 기본적으로 $V^\pi(s)=E[Q^\pi(s,a)] \space under\space\pi(s\mid a)$이고, 이는 $s$에서 policy를 사용했을때의 평균적으로 어떻게 할지에 대한것이다. 즉, 평균보다 더 좋다는 것은 $Q^{\pi}(s,a)>V^{\pi}(s)$를 의미한다.
- 이 내용들은 매우 중요하다!. model-free RL을 공부할때, revisit할 것이다.
Q-function/Value function은 policy가 얼마나 좋은지 evaluate할 수 있는 object들이다. 그것들을 fit/learn하게되고, 그것들을 파란박스에서 사용하게 된다.
Different type of RL algorithm들에 대해 훑어 보자.
- Policy gradient는 $\theta$에 대해 위의 objective를 direct하게 derivative를 계산하여, gradient descent를 사용한다.
- Value-based method은 optimal policy를 위한 value/q function을 estimate한다. Neural Net과 같은 것으로 나타내지는 이런 value/q function들을 policy를 향상시키기 위해 사용한다. Pure-value based funciton은 policy를 direct하게 표현하지 않고, argmax of Q function과 같이 implicit하게 표현한다.
- Actor-critic method는 위의 두가지 방법에 대해 hybrid한 것이다. Actor-critic method는 value/q function을 배워서, policy를 향상시키기 위해 그것들을 더 좋은 gradient를 계산 하는 것에 사용한다.
- Model-based RL : transition model을 estimate해서, 그 transition model을 explicit policy없이 planning하는데 사용하거나 policy를 향상시키기 위해 사용한다. (transition model을 사용하는 것에는 다양한 방법이 있다.)
Model-based algorithm에 대해서부터 설명해보자.
- 초록색 박스에서 $p(s_{t+1}\mid s_t,a_t)$에 대한 어떠한 모델을 학습한다. $s_t,a_t$를 input으로 하는 Neural Net일수 있고, output은 $s_{t+1}$에 대한 probability distribution일 수도 있고, deterministic model일 수 도 있다. (deterministic model은 $s_{t+1}$을 directly하게 예측하는 모델이라고 볼 수 있다.)
- 파란박스에 대해서는 여러가지 옵션이 있다. model based algorithm들은 이 파트를 어떻게 구현하냐에 따라 많이 달라진다.
- e.g) 체스게임이 어떤 규칙으로 작동하는지 배우고, monte-carlo tree search와 같은 discrete planning algorithm과 같은 것을 이용해 chess를 play할 수 있다. 또는 continuous env of robot physics를 배워서 어떠한 optimal control or trajectory optimization procedure를 사용할 수 있다.
- numerical stability를 고려하기 위해 어떠한 trick들을 사용해야 한다. e.g, second order method가 first order method보다 더 잘 작동하는 경향이 있다 (backpropagate gradients in to the policy에 관해)
- Value/q function을 배우기 위해 모델을 사용하고, 해당 value/q function을 policy를 향상시키기 위해 사용하는 것이다. 어떠한 dp모델을 사용할 수 도 있고, model-free RL을위해 additional data를 generate하는 방법도 있다.
- 초록 박스 : 보통 $V(s),Q(s,a)$를 표현하기 위해 Neural Net을 사용한다.
- 파란 박스 : pure-value based method이다. policy를 Neural Net등을 이용하여 explicit하게 표현하지 않고, argmax와 같은 것을 이용해 implicit하게 표현한다.
- 파란 박스 : gradient of the expected value of the reward를 이용해 계산한다.
- 초록 박스 : compute by adding reward.
- c.f) roll out = sample of policy.
Actor-critic : hybrid between value-based methods and policy gradient methods.
왜 이렇게나 많은 다른 algorithm들이 있을까?. 하나의 RL만 배우고 적용하지 않고, 이것들을 배워야 할 이유는 뭘까? 이러한 알고리즘들은 여러가지 trade-off가 있다.
중요한 Trade off 중 하나는 Sample efficiency에 대한 것이다. (이후 수업들에서도 다룰 예정) Orange box에서, 환경으로부터 sample들을 generate할때 좋은 policy를 얻기 위해선 몇개의 sample들이 필요할까?를 물어볼 수 있다.
또 다른 trade-off는 stability & ease of use이다. RL algorithm들은 꽤 복잡하다. 다양한 parameter사이, how you sample, how you explore, how you fit your model/value function, how you update your policy등에 대해서 trade off/choice를 요구한다.
Different algorithm들은 different assumption을 요구한다.
- Do they handle Stochastic environment or deterministic environment?
- Do they handle continuous state and action or discrete?
- Do they handle episodic problem ( problem with fixed $T$ horizon) or infinite horizon or both?
우리가 직면한 문제에 따라 이것들에 대해서 trade off를 결정해야 한다.
Algorithm의 sample efficiency를 결정하는 데 있어, 가장 중요한 질문 중 하나는 off policy algorithm이냐 혹은 아니냐에 대한 질문이다.
- Off policy algorithm : 이전에 수집한 샘플들로 policy를 향상시킬 수 있냐에 대한 알고리즘이다.
- On policy algorithm : policy가 바뀔 때 마다 이전 샘플들을 버리고, 새로운 샘플들을 생성하는 것을 필요로 한다. 이러한 의미에서 on-policy algorithm은 꽤 비효율적이다. e.g, policy gradient algorithm은 각 gradient step을 할때마다 새로운 샘플들을 모아야 한다.
왜 비효율적인 알고리즘을 사용해야할까? (그냥 왼쪽에 있는 것들을 사용하지 않고,) e.g, 매우 빠른 simulator를 사용하는 경우 sample를 생성하는 비용이 매우 cheap할 것이다 예를들어 Chess를 한다고 했을때, simulating chess는 매우 빠르다. 그래서 이런 경우 대부분의 computation time은 value function/policy를 update에 사용될 것이다. 이런 경우 sample efficiency가 문제가 아닐것이고, 이런 경우 efficiency에 대한 위의 수평선이 flip될것이다.
Stability & ease of use에 대해서 알아보자.
- Does our algorithm converge? → fixed solution으로 수렴하는 것을 보장하냐 혹은 진동하거나 발산하냐에 대한 것이다.
- Does it converge, to what? → local optimum으로 수렴하나? 등등.
만약 optimization 혹은 supervised learning background를 갖고 있다면, 이런것들이 왜 질문일까?에 대해 궁금할 수 있다. (딱 나다! ㅋㅋ)
supervised learning 혹은 well defined convex optimization들은 항상 converge할 경우에 대해서만 다루기 때문이다. RL에서의 Converge algorithm들은 사실 rare luxury와 같고, 보통 practice에서 사용하는 알고리즘들은 수렴하는 것을 보장하지 않는다. 그 이유는 많은 RL 알고리즘은 pure gradient descent/ascent가 아니고, 사실 매우 단순한 tabular discrete dataset에서만 수렴하는 것이 보장된 fixed-point algorithm 이어서 실전에서 동일하게 동작하지 않는다. 이론에서는 많은 RL의 수렴, Q-learning과 같은, 사실 open problem이다.
- 많은 RL 알고리즘들이 하는 one common assumption은 full observability이다. Observation말고 state에 대해 접근할 수 있다는 것이다. (O를 무시할 수 있다.)
- 그 다음 policy gradient method에서 보통 하는 assumption은 episodic learning이다. 오른쪽 로봇을 보면, trial 한 후에 reset하고 또다른 trial을 한다. Reset하고 다시 try하는 이러한 능력을 의미한다. 보통 policy-gradient method에 의해 assume된다, 보통 value-based method에 의해서 assume되지는 않는다.
- Continuity or smoothness는 Model based method에서 특히 많이 assume된다.
Deep RL algorithm의 예시를 간단하게 훑어보자!. 이후 수업들에서 훨씬 자세하게 다룰 것이다.
Q-learning is value based method. NN을 이용해서 $Q(s,a)$를 estimate하는 것을 학습한다. Atari game은 discrete-action environment이고, each small discrete set of action에 대해 Q value를 estimate한다. 그리고 이러한 Q values들에 대해 argmax를 적용하여 best action을 정하게 된다.
Guided policy search라고 불리는 model based RL-algorithm이다. 다양한 robotic skill을 수행하기 위해Dynamics model과 image-based CNN model을 결합한 모델이다.
policy-gradient로부터 유도된 actor-critic algorithm이다.
