Pragmatic Romantist

Off-policy Monte CarloOff-policy strategyOff-policy 에서는, Exploratory policy와 Target policy를 분리하고 각각 다른 policies를 사용한다. Exploratory policy ($b(a|s)$): Exploratory policy는 Task를 수행하면서 State, Action, Reward를 포함한 Experience(tarjectory)를 수집한다. Experience들은 Target policy를 학습시키는데 사용된다.$$ S_0, A_0, R_1, S_1, A_1, ..., R_T $$ Target policy ($\pi(a|s)$): Optimal policy를 찾기 위해서 실질적으로 개선되는 Policy이다. Explora..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };On-policy Monte CarloExploration of the environment를 maintain하기 위한 method 중 하나$\epsilon$-greedy policy: Exploration of environment를 maintain하기 위해 낮은 확률로 random action을 수행하도록 만드는 Policy이다. 모든 Action의 확률은 0보다 크며, $\epsilon$ 의 확률로 random action이 선택되고 $1-\epsilon$ 의 확률로 가장 높은 $Q(s, a)$를 가진 Action이 선택된다. 이 Policy는 시간이 지날수록 모든 action을..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };Generalized Policy Iteration (GPI)Monte Carlo methods를 사용하여 control tasks를 풀기위해서 GPI를 사용한다. 초기에는 임의의 Policy로 시작한다. Agent는 첫 episode의 처음부터 끝까지 초기 Policy를 사용하면서 trajectory를 생성한다. 이후 각 시간에서의 return이 rewards의 discounted sum으로 계산된다.$$ S_0, A_0, R_1, S_1, A_1, R_2, ..., R_T $$$$ G_t = R_{t+1} + \gamma R_{t+2}+\gamma^2 R_{t+3} + ... + \..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };Monte Carlo methodsMonte Carlo mehods는 경험에 기반한 알고리즘들 중 하나이다. 경험에 기반한 알고리즘들은 Agent가 환경과 상호작용하면서 모은 samples of experience를 기반으로 $v_*(s)$(optimal state-value)혹은 $q_*(s,a)$(optimal q-value)를 학습한다. 학습 초기에, Agent는 임의의 Policy를 따른다. Agent는 trace of experience(trajectory)를 생성하면서 episode가 끝날 때 까지 현재 Policy를 따라 task를 수행한다.$$ S_0, A_0, R_1..

Generalized Policy Iteration (GPI) GPI는 대부분의 강화학습 알고리즘의 general template 이다. Monte Carlo methods는 model of the environment가 정의되지 않은 상태의 알고리즘이지만, environment에서 수집된 experience로 value를 update한다는 차이점만 있고 큰 형식은 GPI를 따른다. 많은 강화 학습 알고리즘들은 GPI를 개념적으로 차용하지만 DP를 사용하지는 않는다. 왜냐하면, DP의 단점들 때문이다. Disadvantages of dynamic programming DP는 High computational cost가 발생한다. 왜냐하면, 매 Iteration 에서 우리는 모든 states를 update..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };Policy IterationPolicy Iteration은 optimal policy와 이의 value function을 alternating하면서 서로를 개선한다. 이렇게 현재의 policy으로 value를 계산하고 해당 value를 통해서 policy을 개선하는 반복적인 과정은 많은 강화학습 알고리즘에 영향을 끼쳤다. 이 점에서 Policy Iteration은 강화학습에서 매우 중요한 의의를 가진다.Algorithm$\pi(a|s)$(Policy)와 $V(s)$ (각 State에 대한 State Value)를 임의의 값으로 initialize한다.[Policy Evalua..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };Value Iteration $$ \pi_*(s)=\arg\max_a\sum p(s',r|s,a)[r+\gamma v_*(s')] $$ 우리는 매 State마다 return을 maximize하는 Action을 택하는 Optimal policy($\pi_*$)를 찾고싶다. 하지만, 위 식에서 보여지듯이 그러기 위해서는 매 State 마다의 optimal value($v_*$)를 알아야한다. 이에 우리는 각 State의 optimal state value($v_*$)를 찾기위해서 iterative process를 통해 estimate할 것이다. 아래와 같은 Update rule을 사..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };Dynamic Programming: Problem을 더 쉽고, 작은 Problems로 나누어 solution을 찾는 방법이다. 우리가 풀어야하는 Problem은 Optimal Policy $\pi_*$를 찾는 것Property: Dynamic Programming이 되기 위해서는 2가지 properties를 반드시 가져야한다.1. Optimal substructure: 나누어진 subproblems들의 optimal solution들을 구해서 합치면, original problem의 optimal solution이 되는 구조이다. 이는 즉, 각각의 state의 optimal so..

MathJax = { tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]} };State value and Q-valueState value($v_\pi(s)$): State value function는 해당 State에서 end of episode(종료 조건 만족) 까지 가는데 얻어지는 Expected return이다. $$ v_\pi(s) = \mathbb{E}[G_t|S_t = s] $$$$ v_\pi(s) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+2} + ... + \gamma^{T-t-1}R_\gamma|S_t = s] $$ Q-value(=Action value)($q_\pi(s, a)$)..

Finite vs Infinite Finite Markov decision process : State / Action / Rewards 가 모두 유한하다. ex : 5x5 미로 - 위치 state가 25개 / 4개(상하좌우)의 action / single reward Infinite Markov decision process : State / Action / Rewards 중 하나라도 무한하다면 Infinite Markove decision process 이다. 연속적 값의 경우 가능한 값이 무한하다. ex : 자동차 운전 - state : 자동차의 위치, 속력(infinite) Episodic vs Continuing Episodic Markov decision process : 특정 조건에서 종료되..