# reinforcement learning
5.1 2013 DQN paper review
Q-learning review $$\begin{aligned} Q(st,at) = \int\limits{s{t+1},a{t+1}} (Rt + \gamma Q(s{t+1}, a{t+1}))p(a{t+1}|s{t+1}) p(s{t+1}|st,at)ds{t+1},a_{t+1} \end{aligned}$$ The action value function has target policy and transition pdf. We sample N samples from two variables($$s{t+1}, a{t+1}$$) and then divide by N. As N increases, due to the law of large numbers, we approach the converging Q value, and this process is Q-learning. Target policy is the policy maximizing next Q($$
4.4 n-step TD vs n-step Q-learning
2-step TD recall equation for $$G_t$$(expected reward) $$\begin{aligned} Gt &= Rt + \gamma R{t+1} + \gamma^2 R{t+2}…\\ &= Rt + \gamma R{t+1} + \gamma^2 G_{t+2} \end{aligned}$$ We will use this equation form to make 2-step TD. Let’s apply Bellman equation to action value function. $$\begin{aligned} Q(st,at) &= \int\limits{s{t+1},a{t+1}} (Rt + \gamma Q(s{t+1}, a{t+1}))p(a{t+1}|s{t+1}) p(s{t+1}|st,at)ds{t+1},a_{t+1}\\ & = \int\limits{s{t+1},a{t+1},s{t+2}, a{t+2}} (Rt +
4.3 SARSA vs Q-learning
Let’s compare two methods with a following example: I will denote row 2 column 3 as r2c3(in this figure). What sarsa do is getting TD-target corresponding to current action and next action. After first episode, r2c3 will be updated. Then, in the second episode, the agent will update r2c2 only negative te
4.2 Q-learning(advanced)
Q-learning We use off-policy in the Q-learning. We apply greedy action for target policy, and $$\epsilon$$-greedy action for behavior policy. equation for policies target policy Since we use greedy action for target policy, we need the best action for every future action(we use delta function!!) $$\mathrm{target} : p(a{t+1}|s{t+1}) = \delta(a{t+1} - a{t+1}^), \\a_{t+1}^ = \argmax\limits{a{t+1}} Q(s{t+1}, a{t+1})$$ We have learn this idea(delta function) at **3.1 - optimal
4.1 On-policy vs Off-policy
Relationship between on-policy & off-policy If a behavior policy equals to target policy, we call the policy On-policy. And if they are not equal, then we call the policy Off-policy. What is behavior policy & target policy? Recall action value function and TD approximation. $$\begin{aligned} Q(st,at) &= \int\limits{s{t+1},a{t+1}} (Rt + \gamma Q(s{t+1}, a{t+1}))\colorbox{ligh
3.4 MC vs TD
Temporal difference has a problem. Let’s review SARSA(from Bellman equation) and MC. SARSA: $$\begin{aligned} Q(st,at) &= \int\limits{s{t+1}:a\infin} Gt p( s{t+1}, a{t+1},… | st,at) ds{t+1}:a\infin \\ &=\int\limits{s{t+1},a{t+1}}(Rt + \gamma Q(s{t+1}, a{t+1}))p(s{t+1},a{t+1}|st,at)ds{t+1},a_{t+1}\\ &\approx \frac {1}{N} \sum\limits{i=1}^N (Rt^{(i)} + \gamma Q(s{t+1}^{(i)}, a{t+1}^{(i)}))\\ \end{aligned}$$ Monte Carlo: $$Q(st, at) \approx \frac {1}{N} \s
Markov Decision Processes (MDP) - 2
**Markov Deicision Processes에서 중요한 4가지 토픽은 다음과 같으며, 지난 시간에 이어 이번 시간에는 3) Markov Decision Processes 4) Extensions to MDPs를 다뤄보도록 하겠다.** 1) Markov Processes 2) Markov Reward Processes **3) Markov Decision Processes 4) Extensions to MDPs** 이전 포스팅은 Markov Decision Processes - 1 에서 확인이 가능하다. Recap을 위해 MDP의 구성요소를 다시 확인해본다면 다음과 같다. Definition Agent: > 앞으로 실험 상황에서 연속된 행동을 하게 될 주체, 대리인 State($s_{t}$): > t 시간에서의 Agent의 상황과
3.3 Temporal difference(TD) & SARSA
Temporal difference Recall the Bellman equation : $$\begin{aligned} Q(st,at) &= \int\limits{s{t+1}:a\infin} Gt p( s{t+1}, a{t+1},… | st,at) ds{t+1}:a\infin \\ &=\int\limits{s{t+1},a{t+1}}(Rt + \gamma Q(s{t+1}, a{t+1}))p(s{t+1},a{t+1}|st,at)ds{t+1},a_{t+1}\\ &\approx \frac {1}{N} \sum\limits{i=1}^N (Rt^{(i)} + \gamma Q(s{t+1}^{(i)}, a{t+1}^{(i)}))\\ & \mathrm{let’s\ say\ this\ equation\ } \overline{Q}_N \end{aligned}$$ The differnce between temporal difference and
3.2 Monte Carlo(MC)
How can we get $$Q^*$$? We have learned how to calculate maximum value of state value function by optimal policy. If the $$Q^$$ is given, what we need to do is just find the policy maximizing $$Q^$$. But, how can we get $$Q^*$$? Actually, we cannot get $$Q^$$ directly. We believe that if we train the agent with $$\epsilon$$-greedy, its action value function will get closer to $$Q^$$. It may not be the best policy. But we believe it’s performance may be good enough. After training, we te
Markov Decision Processes (MDP) - 1
강화학습에 자주 등장하는 개념인 MDP에 대한 깊이 있는 이해를 위해 정리를 해보려고 한다. 출처 자료로 딥마인드의 수석 연구 과학자이자 University College London의 교수를 역임하셨던 David Silver의 Lecture note를 사용하였다. 내용을 이해하기 위해서는 5가지 MDP의 구성요소를 이해하고 넘어가는 것이 좋다. Definition Agent: > 앞으로 실험 상황에서 연속된 행동을 하게 될 주체, 대리인 State($s_{t}$): > t 시간에서의 Agent의 상황과 상태 Action($a_{t}$): > State $s_{t}$에서 Agent가 취할 수 있는 행동들 Reward($R$): > Agent가 움직이면서(= Action $a_{t}$를 진행하면서) 발생하는 보상 점수 Transitio
3.1 Optimal policy - more details
Optimal policy(derivation) As we have learned, the optimal policy is a function that maximizes the state value function. The state value function focuses on maximizing the reward from the current state. But, how can we maximize the state value function? let's dive into equation. $$\begin{aligned} V(st) &\triangleq \int\limits{at:a\infin} Gt p(at:a\infin | st)dat:a\infin\\ & = \int\limits{at}Q(st,at)p(at|st)da_t\ \mathrm{(by\ Bellman\ equation)}\\ \end{aligned}$$ In the equat
2.3 Bellman equation
Bellman equation is about method of representing state value function and action value function. Bellman equation for value state function Let’s change the form of state value function(using bayesian rule). Recall Bayesian rule: $$p(x,y) = p(x|y)p(y)$$ $$p(x,y|z) = p(x|y,z)p(y|z)$$ The state value function becomes: $$\begin{aligned} V(st) &= \int\limits{at:a\infin} Gt p(at, s{t+1}, a{t+1},… | st) dat:a_\infin \\ &=\int\limits{at} \colorbox{aqua}{$\int\limits{s{t+1}:
2.2 State value function, Action value function & Optimal policy
In this chapter, we will focus more on expected return. State Value Function is a function for the return expected from now on. This function evaluate the value of the present state. If the agent is given a random state, the goal of state value function is to maximize the return from the given state. Action Value Function is a function for the return expected from current action. We have learned about function $$Q(st, at)$$ at the previous chapter. This function Q is the action
2-1. Markov Decision Process(MDP)
What is MDP? Decision means, the agent decides what action to take in each state. Every action($$at$$) leads to next state($$st$$). The first important properties of MDP is that every action is done randomly. This means state and action has (discrete) probability distribution. $$p(a1 | s0, a0, s1)$$ The arrows shown in the figure represent the information needed to find the probability dist
1-1. Q-learning
An agent can move up, down, right, left. It moves randomly until it reaches the goal. This journey is called 'the episode'. The episode is repeated until the agent finds the shortest path between start and the goal. In the Q-learning algorithm, we use greedy action. We give scores to the agent for every movement. The greedy action is that the agent moves to the highest scored direction. At the
DQN 알고리즘
심층 Q 네트워크(DQN, Deep Q Network)는 SARSA와 마찬가지로 Q 함수를 근사하는 가치 기반 시간차 알고리즘으로 현재 정책에 대한 Q 함수를 학습하는 SARSA와는 다르게 최적 Q 함수를 학습한다. 앞선 글에서 각 알고리즘의 타겟 Q 함수를 다음과 같이 구하였다. $$ \begin{aligned} SARSA &: Q^\pi (s,a) \approx r + \gamma Q^\pi (s',a') = Q^{\pi}_{tar:SARSA}(s,a) \\ DQN &: Q^\pi (s,a) \approx r + \gamma \max{a'i} Q^\pi (s',a'i) = Q^{\pi}{tar:DQN}(s,a) \end{aligned} $$ 여기서 DQN과 SARSA의 가장 큰 차이점을 알 수 있는데, 이는 DQN이 SARSA와 달리 비활성정책 알고리즘이라는 것이다. 비활성정책 알고리즘은 향상시키고자 하는 목표 정책과 데이터를 수집하기위한 정책을 분리할 수 있으며, 이
강화학습 주요 개념
주요 개념 1. 강화학습의 개념 : "어떤 환경에서 어떤 행동을 했을 때 그것이 잘된 행동인지 잘못된 행동인지를 판단하고 보상/벌칙을 주는 과정을 반복해서 스스로 학습하게 하는 분야" 환경: 에이전트가 관측할 수 있는 정보 에이전트: 환경에서의 행동주체. 에이전트는 환경에 대해 여러가지 행동을 반복하면서 최적의 행동을 학습 2. 강화학습의 목표 : 환경과 상호작용하는 에이전트를 학습시키는 것. 에이전트는 상태(State)라고하는 다양한 상황 안에서 행동(Action)을 취하며, 학습을 진행한다. 에이전트의 행동에 대한 응답으로 보상(Reward)를 돌려받는다. )과는 달리 가치 함수를 학습하는 알고리즘이다. SARSA 알고리즘에서는 $Q^\pi(s,a)$를 학습하며, 심층신경망을 사용할 경우에는 신경망이 이를 근사하게 된다. 가치함수 중에서도 상태 가치 함수가 아닌 상태-행동 가치 함수를 근사하는 이유는 추후에 가치 함수에서 정책을 추출할 때 더 용이하기 때문이다. 만약 $V(s)$를 근사하게 되면, 가능한 모든 행동 $a$에 대해서 이후에 나올 상태 $s'$을 추론하고, 이에 대해서 $V(s')$을 모두 계산하여 최대값을 찾아야 하는데, 이러한 과정이 상태-행동 가치함수를 사용할 경우 매우 간소화된다. 하지만 상태-행동 쌍에 대해서 학습을 진행하기 때문에 상태 데이터에 대해서만 학습을 진행하는 $V(s)$보다 데이터가 더 많이 필요하고 학습이 어렵다는 단점이 있다. SARSA 등의 가치 기반 알고리즘에서는 시간차 학습(Temporal Difference, T
REINFORCE 알고리즘
이번 포스트에서는 REINFORCE 알고리즘을 학습한다. REINFORCE은 목적함수를 따라 정책 경사를 계산하여 정책을 결정하는 파라미터를 최적화하는 방법으로 먼저 목적함수는 다음과 같이 궤적에 대한 이득의 기댓값으로 정의한다. $$ J(\pi\theta) = E{\tau\sim\pi\theta}[R(\tau)] = E{\tau\sim\pi\theta}\left[ \sum^T{t=0}\gamma^t r_t \right] $$ 여기서 $\pi_\theta$는 $\theta$라는 파라미터로 표현되는 정책을 의미하며, 심층신경망을 사용하여 정책망을 구현할 경우 심층신경망의 학습가능한 파라미터들이 $\theta$가 된다. 정책 경사 알고리즘은 이렇게 파라미터 $\theta$로 표현되는 목표함수를 $\theta$에 대해 미분하고, 그 결과를 바탕으로 경사기반 최적화를 수행하여 최적의 파라미터를 찾는 알고리즘을 의미한다. 알고리즘의 목표는 목표함수를 최대화하는 것으로 다음
A3C (Asynchronous Advantage Actor-Critic)
A2C의 장단점 장점 에피소드가 끝날 때까지 기다리지 않아도 된다. Advantage 함수를 도입해 그래디언트 분산을 줄였다. 단점 정책과 가치함수를 학습시킬 때 사용되는 샘플(batch)가 시간적으로 상관되어 있다. 샘플간의 높의 상관관계는 그래디언트를 편향시키고 학습을 불안정하게 만들 수 있다. A3C (Asynchronous Advantage Actor-Critic) 알고리즘 A2C의 데이터의 상관관계 A2C의 목적함수 그래디언트는 다음과 같다. $$\begin{aligned} \nabla\theta J(\theta) = \sum\limits{t=0}^T ({\mathbb E}{xt \sim p\theta(xt), ut \sim \pi\theta(ut|xt)} [\nabla\theta \log \pi\theta (ut|xt) A^{\pi\theta}(xt, u_t)]) \end{aligned}$$ 한 개의 에