강화학습/용어

1. 개요

2. 용어

• Agent : 주인공, 학습하는 대상으로, 환경속에서 행동하는 개체를 말한다. (ex. 개, 로봇, 플레이어)

• Environment : Agent와 상호작용하는 환경. 강화학습은 Agent와 Environment간의 상호작용간에 일어나는 과정이다.

• State : True configuration of system. Agent가 필요한 구체적 정보(ex. 위치, 속도)를 말한다. Agent가 action을 하면, 그에따라 환경이 agent의 상태를 변화시킴. 흔히 [math(s)]로 표현된다. 또한 일반적으로 markov 가정을 따를 때 쓰인다.

• Observation : 대개의 경우 Agent가 state 전부를 아는 것은 불가능하다.(가능한 경우를 fully observable)이라고 함. Agent가 state 중 일부를 받는데 이 정보를 Observation이라 한다.

-observation vs state-

버클리강의의 5:10 참고

- observation이 이미지라면, state는 해당 이미지의 정보

• Policy : Agent가 움직이는 행동 방향. 정책으로도 불리며, 크게 deterministic policy와 stochastic policy로 나뉜다. deterministic policy는 해당 state에 따라 100% 확률로 action이 mapping되는 [math(a=\pi(s))], stochastic policy는 state가 주어졌을 때, action이 확률적으로 선택된다. [math(a=\pi(a|s))]. 파이를 주로 사용함. 강화학습의 목적은 결국 optimal policy (accumulative reward = return을 최대화하는 policy)를 찾는 것이다.
  
• Action : Agent가 실제 행동한 내용을 말함. Policy에 의해 도출되고. [math(a)]로 표현한다.

• Reward : Agent가 행동을 했을 때 받게 되는 보상(scalar)으로서, 특정 행동을 유발시키기 위해 positive reward를, 특정 행동을 금지시키기 위해 negative reward를 취할 수 있다. 이때 agent가 어떻게 해야 높은 보상을 받게 되는지 알려주면 안 된다.(에이전트 입장에서 '어라? 이런 시도를 하니까 많이 주네?'로 느껴지게 해야 함). 또한 행동 1번에 꼭 1번 보상이 주어지지 않거나(sparse) 현재 행동이 미래의 보상에 영향을 끼칠 수도 있다.(delayed, ex. 바둑) 미래에 받게 되는 reward에 대해서는 discount을 적용하고, 보상들을 전부 더해 return [math(G_t)]를 얻을 수 있다.

• Return : [math(G_t)]로 표현되고, agent가 time step [math(t)]로부터 앞([math(t+1)])으로 받게 될 discounted Reward의 누적 합이다. 예. [math(G_t=R_{t+1}+rR_{t+2}+r^2R_{t+3}+\cdots+r^{T-1}R_T)]. [math(T)] = Terminal state
  또한 중요한 것은 Return의 expectaion이 state-value function [math(v(s)=E[G_t|S_t=s])]이라고 한다.
  여기서 agent의 행동 방식 policy [math(\pi)]를 고려한다면 [math(v_\pi(s)=E_\pi[G_t|S_t=s])]

• Exploration : 탐험. 도박. Agent가 현재 알고 있는 지식으로 행동을 하지 않고, 모르는 분야로 나아가서 정보를 얻기 위해 행동하는 것을 말한다. 예를 들어, 음식점에 갔을 때, 내가 항상 먹던 것을 먹을 것이냐, 안 먹어봤던 신메뉴를 먹어볼 것이냐가 대표적인 예이다. [math(\epsilon)]-greedy에서 [math(\epsilon)]이 모험을 할 확률을 말하며, [math(Q)]가 높은 action을 하는 것이 아닌 모든 action 중 랜덤하게 골라서 action함. model-free한 상황에서 local optimality에 빠지는 걸 방지.

• Exploitation : 활용. exploration의 반대. Agent가 아는 지식으로 행동함. Exploration과 상호 대립되는 개념. 강화학습은 Exploration과 Exploitation의 정도를 조절하는 게 중요함. [math(\epsilon)]-greedy에서 greedy하게 action을 선택하는 경우이다.

• Value : state의 가치를 말함. 가치란 해당 state에 도달했을 때의 reward와 그 state 이후에 얻게 되는 reward를 모두 반영해서 계산됨. [math(v(s))]로 표현. agent가 value를 greedy하게 Action을 선택한다고 했을 때, Agent는 이동 가능한 State 중 제일 높은 [math(v(s))]로 이동함.
  이것이 근시안적인 선택으로 보이지만, Value의 정의 자체가 장기적인 가치를 나타내기 때문에, Greedy하게 학습해도 장기적인 보상을 따르는 Agent로 학습이 됨. 보통 [math(v(s))]로 표기하면 state-value function이고, [math(q(s,a))]로 표기하면 action-value function.

• State value : 어떤 state [math(s)]에서 보상을 받고 특정 policy [math(\pi)]를 따랐을 때 받게 되는 Return의 기대값. [math(v_\pi(s)=E_\pi[G_t|S_t=s])] (note:Return은 discounted reward)

• Action value : state [math(s)]에서 특정 action [math(a)]를 한 후 policy [math(\pi)]를 따랐을 때 얻을 수 있는 Return의 기댓값. Quality의 [math(Q(s,a))]로 표현됨. value function을 state에 대해 보지 말고, action에 대해 본다면, 그것이 바로 action value function이다. [math(s)]에서 [math(a)]를 한 후 임의의 정책 [math(\pi)]를 따르는 action value funtion [math(q)]는 [math(q_\pi(s,a)=E_\pi[G_t|S_t=s, A_t=a])]로 정의된다. Q-value로도 불림.

• Discount rate(factor) ; 할인율, 감쇄율. 감마로 표현. [math(0\leq\gamma\leq1)] 지금 100만원을 받거나 1달 뒤에 100만원을 받는 두 가지 경우 중 하나를 고른다고 하면, 당연히 전자를 고를 것이다. 이처럼 Agent가 미래에 받는 보상은 할인율을 적용하여 학습하여야 최단경로를 학습해 나갈수 있음. 예를 들어, 매번 움직일 때마다 reward를 +1씩 해준다면, Reward는 무한이 될수 있으나, 감쇄율을 한 step씩 이동할 때마다 reward에 곱해줘서, 두 스텝뒤의 보상은 할인율의 제곱이 곱해진 reward가 됨.

• MDP(Markov Decision Process) : 1. 처음 어떠한 상태로부터 시작해서 현재 상태까지 올 확률
  2. 바로 전 상태에서 현재 상태까지 올 확률. 1, 2가 같을때 상태(state)가 Markov property를 만족한다고 한다. 다른 말로 하면 현재 state [math(s_t)]는 전전 state [math(s_{t-2})]와는 상관이 없다. 다른말로 현재 state의 바로 전 상태는 처음부터 바로 전까지 모든 상황에 대한 정보를 포함하고 있다고 보는 것이다. 예를들어, 바둑의 게임 중간의 바둑판 상황(state)는 이전까지의 모든 정보를 포함하고 있다라고 가정하는 것. 그래서 어떤 문제가 MDP라는 것은 state가 Markov할때
  <state Set([math(S)]), action Set([math(A)]), state transition probability matrix([math(P)]), reward function([math(R)]), discount factor>가 정의된 문제라고 본다.(단, [math(S), [math(A)]는 finite)
• Markov property가 중요한 이유 : optimal policy를 formulate할 수 없다.(entire history가 있어야 하는데, 이것을 통해 optimal policy를 formulate하기는 매우 어려움)

• Bellman equation : value를 구하는 것이 RL에서 중요한데, 이것을 재귀적 혹은 Dynamic Programming적 관점에서 바라봄으로써, 현재 state의 value와 다음 state의 value의 관계를 식으로 표현한 것. [math(v(s))]는 두 파트의 합의 기대값으로 표현됨. 1. [math(S_t=s)]에서 받는 즉각적 보상 [math(R_{t+1})]. 2. [math(S_{t+1})]의 value에 discounted factor([math(\gamma)])가 곱해진 [math(rv(S_t+1))]. 이를 식으로 표현하면, [math(v(s)=E[R_t+1+\gamma v(S_{t+1})|S_t=s])] 마찬가지로 action-value function을 Bellman equation으로 나타내면, [math(q(s,a)=E[R_{t+1}+\gamma q(S_{t+1},A_{t+1})|S_t=s,A_t=a])]
  자세한 내용은 이웅원의 깃북 참조. Bellman expectation equation과 동일.

• Bellman Optimality equation : optimal value function의 관계를 나타내주는 식. 먼저 optimal(*로 표기)에 대해 이해할 필요가 있는데, 정답부터 말하자면 [math(v_*(s))] or [math(q_*(s,a))]는 모든 policy [math(\pi)]에서 [math(v(s))] or [math(q(s,a))]중 가장 큰 값. 즉, 반대로 말하면, [math(v(s))] or [math(q(s,a))]중 가장 큰 값을 갖는 policy [math(\pi)]는 optimal policy [math(\pi_*)]라고 할 수 있다. optimal policy는 단순히 [math(q(s,a))]를 최대화하는 action을 할 확률이 100%라는 것이다. [math(v_*(s)=\max_aq_*(s,a))] 혹은 [math(q_*(s,a)=R_{s,a}+\gamma\sum_{s'}P(s'|s,a)v_*(s'))]. 여기서 [math(v)]의 [math(q)]를 뒤의 식으로 대입 가능.

• Backup : Bellman equation에서 [math(v(s))]와 [math(q(s,a))]간의 연관성을 추가한 개념으로서, 현재의 value function을 미래의 value function으로 구하는 개념. 이는 [math(v)]와 [math(q)]를 Tree 구조로 나열이 가능하기 때문에 가능한 것으로서, 얼마나 멀리 미래로 갈 것이냐에 따라 one-step or multi step backup으로 나뉘고, 가능한 모든 미래를 확인할 것이냐 아니면 실제의 경험(하나의 미래)를 통해 확인할 것이냐에 따라 Full-width or sample backup로 나뉘어 진다. Full-width backup은 dynamic programming에 속하고, sample backup은 Reinforcement learning에 속한다. [math(s)]에서 [math(a)]를 했을 경우 deterministic한 환경이 아니라면(stochastic), [math(v(s))]는 가능한 모든 경우의 다음 state [math(s')]의 [math(q(s,a)\pi(a|s))]의 합으로 표현할 수 있다. 마찬가지로 [math(q(s,a))]는 reward [math(r_{s,a})]와 다음 state [math(s')]의 [math(v(s')*P(s'|s,a))]라고 할 수 있다. ([math(P(s'|s,a))]는 MDP의 요소인 state transition probability matrix)

• Episode : Agent가 state들을 돌아다니며 결국 terminal state에 도달했을때, Episode가 끝났다고 한다. 자연적으로 끝나게 되면, Episodic task.

• History : 한 Episode간 Agent의 (state, action, reward, next state)의 sequence.

• Trajectory : 에이전트가 달린 경로. ([math(s,a,s',a',s,a,\cdots)])

• Planning : 환경의 model을 알고서 문제를 푸는 것. 즉, 어디로 가야 뭐가 나오는지에 대한 map을 알고 어디로 갈지 정하는 것.

• [Reinforcement] Learning : 환경의 model을 모르지만 상호작용을 통하여 문제를 푸는 것.

• Prediction : Dynamic Programming에서의 두 step중 하나로 policy evaluation으로 불림. 현재 optimal하지 않은 어떤 policy를 가지고 value function(=어떤 state [math(s)]의 value)을 구하는(예측) 것. input으로 [math(MDP(S,A,P,R,r))]와 policy를 주거나 혹은 [math(MRP(S,P^\pi,R^\pi,r))]을 주면, output [math(v_\pi)]를 도출.

• Control : 현재의 value function을 토대로 더 나은 policy를 구하는 것. input으로 MDP를 주면, output으로 optimal value function [math(v_*)]와 optimal policy [math(\pi_*)]를 도출.

• Actor-Critic : Actor network([math(\pi(s)=a)])와 Critic network([math(Q(s,\pi(s))))]=value)를 업데이트 하는 방식을 일컫는다.
  
• Rollout : 데이터 transition [math((s,a,s',r))]을 얻기 위해 에이전트와 환경이 1번(or n번) 상호작용 하는 것(sample)을 의미한다. trajectory의 경우 한 에피소드 전체를 바라보고, reward가 포함되어 있지 않지만, Rollout은 한번의 상호작용을 하고, reward를 포함한다.

• Multi-Armed Bandit Problem : 일명 슬롯머신, 레버를 내리는 행위를 하면 보상이 나오는 환경. 슬롯머신 여러 개를 가질 때, 어떤 슬롯머신의 승률이 높은지 알아내기 위해 최초로 시작됨.

• Dynamic programming : Bellman equation을 이용하여, 주어진 완전한 MDP환경에서 모든 state의 Value function을 이용하여 간접적으로 optimal policy를 계산하는 방법론. 두 스텝(Prediction(Policy evaluation)), Control)을 반복하면서 optimal policy를 구함. Model based, Full-width backup. Value based 방법론. 만약 동작한다면 sample efficiency. 즉, 필요한 sample의 개수가 적다. 주로 off-policy learning에 쓰이고 exploration이 잘되는 편. 반대말 : policy optimization 혹은 policy based 방법론 혹은 policy gradient 방법론

• Policy evaluation : 모든 state들의 value를 사용하여 next state들의 value function을 통해 업데이트 하는 과정(Bellman expectaion equation 사용). 이렇게 한번 업데이트 하면 iteration [math(k)]가 1씩 증가됨. next state를 결정하는데 있어 policy가 사용되기에 policy가 얼마나 좋은가를 판단하는 evaluation이 됨.
  [math(k)]를 반복하다보면 해당 policy를 따를 때 각 state의 value가 true value로 수렴하게 됨.
  하지만 실제로 무한번 iteration 할 필요는 없고, 몇번하다가 policy iteration 단계로 넘어가면 됨. 왜냐하면, value가 가장 큰 state들은 금방 두각을 드러내기 때문.

• Policy iteration(improvement) : Policy evaluation으로 해당 policy에 대한 true value를 각 state마다 얻었으니, 이제 더 나은 policy로 업데이트 해줘야 함. policy를 업데이트 하는 방법으로 greedy improvement가 있는데, 단지 다음 state들 중 가장 높은 value를 가지는 state들로 이동하는 확률을 1로 설정하는 것.

• Value iteration : Policy evaluation에서 true value를 구하기 위해 다음 state들의 value를 모두 계산했어야 했는데, 이거는 한번만 하면 됨. Bellman Optimality equation을 사용하여 다음 state 중 가장 높은 value를 사용하여 value를 업데이트함. policy evaluation은 다음 state들의 평균을 이용하는 식이었음. 따라서 evaluation + improvement 효과를 둘다 지니게 됨. Q-learning 계열이 value iteration을 사용하는 대표적인 예이다.

• Model base : 환경 모델(ex. MDP)에 대한 정보(ex. dynamic function, Action space, observation space..)를 알고 시작하는 상황을 말함. 예를들어 Dynamic Programming같은 방법. 하지만 환경에 대해 모두 다 안다는 가정은 매우 사치스러운 가정이긴 함.

• Model Free : 환경에 대해 모를 때, 세상과 상호작용(trial and error)를 통해 얻은 경험을 통해 배워나가는 것. 어떤 시행착오([math(S)], [math(A)], [math(R)], [math(S')])를 sampling하면서 학습하는 방법엔 다음 두가지가 있다. 1) Monte-Carlo, 2) Temporal Difference.

• Monte-Carlo : episode 즉, 처음 state부터 마지막 state까지 진행하면서 얻은 리턴 [math(G)]로 value function을 update하는 방법. 즉 backup으로 따지면, sample backup인데, multi-step(이면서 끝까지 가는것). Monte-Carlo(MC)라는 단어는 강화학습 뿐만 아니라 다양한 영역에서 사용하는 단어로 포괄적인 의미는 무언가 추정해야 할 때, sample들의 평균을 통해? 추정해나가는 실제 경험적인 추정방법?이라고 생각함. 한 에피소드 뿐만 아니라 여러 에피소드를 돌면서 각각의 리턴을 평균화하여 state들의 value를 업데이트함. 한개의 state를 여러 번 방문한 경우에는 처음 방문한 state만 인정하는 First-visit MC policy evaluation, 방문할 때마다 인정하는 every-visit으로 나뉨.
  또한 MC는 episode마다 업데이트하기 때문에 처음 시작 state가 어디였냐에 따라 전혀 다른 episode가 될 확률이 큼. 또한, policy가 stochastic하기에 매 step마다 noise가 발생함. 그래서 variance가 높음. 반면 random인 만큼 bias는 없다. 이는 다시 말하면 Return이 value의 unbiased estimate이기 때문에([math(v(s) = E[G_t|s_t=s])]) bias가 없다. 또한 MC에서는 policy를 update할때 즉, control 과정에서는 [math(v)] 대신 [math(q)]를 사용하는데, [math(v)]를 쓰면 [math(reward(s,a))]와 [math(p(s'|s,a))]를 알아야 하기 때문에, 이건 Model-free과정에서는 모르기 때문에 [math(q)]를 씀. 즉, 단순히 [math(q)]를 최대화 하는 [math(a)]를 선택.

• Temporal Difference : agent의 moving time step [math(N)]마다 update하는 방법. 즉 backup으로 따지면, sample backup인데, multi-step(끝까지 가진 않음). MC가 에피소드가 다끝나고 value를 업데이트했다면, TD는 몇 스텝마다 업데이트하기 때문에 variance가 낮은 장점이 있다. TD의 메인 idea는 '내일 예측이 오늘 예측보다 정확하겠지'라는 뜻으로 벨맨기대방정식의 [math(v(s_t)=E[r_t+\gamma V(s_{t+1})]를 이용한다. 하지만 [math(V(s_{t+1}))]이 또한 예측값이기 때문에 bias가 생긴다. 만약 [math(V(s_{t+1}))]대신 true value인 [math(v(s_{t+1}))]이 주어진다면, bias는 존재하지 않는다. [math(r_t+\gamma V(s_{t+1}))]은 TD target이라고 불리며, function approximate 방법론에서 loss를 계산하는 데 주로 쓰인다.

• On Policy : On Policy과 Off Policy를 구별하는 방법은 데이터를 어떻게 얻느냐이다. 현재 상황에서 현재 best policy(or behavior policy)로 행동했을 때 얻는 정보는 On Policy data라고 할 수 있다. 여기서 데이터(transition)란 특정 상태 [math(s)]에서 action [math(a)]를 했을 때, 얻게 되는 reward와 다음 state인 4개의 데이터(transition) = [math((s,a,s',r))]을 말한다. 당연하게도 남의 경험보단 내 경험이 중요하듯이 Off Policy data보다 On Policy 데이터가 일반적으로 배울 점이 많다. 하지만 얻기가 쉽지 않다.(남의 경험은 많이 있다..)
  또한 On policy계열의 알고리즘은 현재 policy를 업데이트하기 위해선, 현재 policy로부터 얻은 데이터만 써야 한다는 단점이 있다.(즉, policy가 업데이트되면, 이전 policy로 얻은 데이터는 필요 없음.)

• Off Policy : 데이터를 자신이 아닌 다른 곳으로 부터 얻는 곳이다. 다른 곳이란 예를들어, 과거의 나(policy)를 포함한다. 예를들어, 남의 경험에 대한 이야기를 듣고 교훈을 얻는 타산지석, 반면교사의 경우를 Off Policy라고 할 수 있다. 또한 과거의 미숙한 나(policy)로부터 얻은 경험(transition)으로 현재의 나(policy)를 강화시키려는 방법이다. 하지만 과거의 경험이 현재는 쓸모 없는 경험일 수 있다.(가령 환경이 변한다든가) 그래서 Off Policy 데이터는 On Policy 데이터에 비하면 가치(신뢰성)이 떨어진다. 여튼 Off-policy data의 경우 (replay) buffer에 저장해둔 후 버퍼에서 데이터를 샘플링해(꺼내)서 policy를 업데이트 하기 때문에, 시뮬레이션 도중에 학습할 필요가 없는 장점도 있다.

• Offline Reinforcement Learning : Off Policy와 비슷한데, 다른점은 rollout을 any policy로 진행하고, training phase에서 policy를 학습시킨 후에 배포(실제 사용, deployment)할 때는 학습을 중단하고, 학습된 policy를 이용해 상호작용만 하는 것을 의미한다.

• T-horizon과 epoch: T-horizon은 주로 on-policy 계열 알고리즘 예) PPO에서 콜렉팅된 n개의 샘플을 몇 번 사용하고 버릴지를 정한다. 혹은 agent가 몇번 step한 경험을 buffer에 넣을 것인지. epoch는 주로 off-policy 계열 알고리즘 예) DDPG에서 한번 업데이트 할 때 리플레이 메모리에서 몇 번 샘플링을 할 것인지를 정할 때 사용된다.

• Credit assignment: 직역하면 '책임 할당'. 10걸음을 갔을 때 reward 10을 받았다. 이때 10번째로 내딛는 걸음이 가장 reward를 받는데 영향력이 크고 첫번째 걸음이 가장 영향력이 적을 것이다. 그렇다고, 첫 번째 걸음이 의미 없진 않다. 즉, credit assignment는 어떤 일련의 action들을 진행해서 reward를 받았을 때, 과연 그중 어떤 action이 reward를 받는데 가장 큰 몫을 했는가 분석하는 것이다. 이는 기본적으로 discount factor와 관련이 있다. 만약 감쇄율이 1에 가깝게 높으면, 더 먼 과거의 action까지 책임을 부여하고, 0에 가까울수록, 최근의 action만 책임을 부여하게 된다. 정확히는 [math(Q(s,a))]값이 높으면 해당 positive reward를 받는데 영향이 큰 action이라고 볼 수 있다.

• variance & bias : value [math(Q)], [math(V)]를 실제 [math(Q_*)], [math(V_*)]와 비슷하게 예측하는 것이 강화학습의 목표 중 하나이다. 이때 100번 [math(Q)] 값을 예측했을 때 평균적으로 [math(Q_*)]에 이르지만, 표준편차 또는 분산이 높으면, bias는 낮고 variance가 높은 것. 평균적으로 [math(Q_*)]와 다르지만, 분산이 낮으면 bias는 높고, variance가 낮은 것.