강화학습/용어

1. 개요

---

강화학습의 용어를 정리한 문서이다.

2. 용어

---

• Agent : 주인공, 학습하는 대상,환경속에서 행동하는 개체.ex.강아지,로봇,게임플레이어

• Environment : Agent와 상호작용하는 환경. agent를 제외한 모든것. 세계. 강화학습은 결국 Agent와 Environment간의 상호작용간에 일어나는 과정이다.

• State : Agent의 상태에 대한 모든 정보를 숫자로 표현한 것(ex. 위치, 속도). agent가 action을 하면, 그에따라 환경이 agent의 상태를 변화시킴. s로 표현. 즉, agent가 a_t를 하면, 환경이 에이전트의 다음상태 s_t+1와 보상 r_t+1을 agent에게 전달. : 이 하나의 loop을 틱(tick) or 타임스텝(time step)이라고 한다.

• Observation : 대개의 경우 Agent가 State 그 자체를 아는 것은 불가능하다. 그렇기 때문에 가능한 모든 정보를 담아 Agent에게 전해주어야 하는데, Agent가 실제로 받는 정보들을 Observation이라 한다.

• Policy : Agent가 움직이는 행동방향. 정책으로도 불리며, 크게 deterministic policy와 stochastic policy로 나뉜다. 가령 동·서·남·북 각각의 방향으로 한 방향을 정하여 움직이는 것을 deterministic policy로 a = ㅠ(s,세타), 각각의 방향으로 1/4 확률로 움직이는 것을 stochastic policy ㅠ(a|s,세타)로 볼 수 있다. 세타는 policy를 정의하는 파라미터 벡터. 수학 파이기호를 주로 사용함. 파이(a|s)로 표현. 강화학습의 목적은 결국 optimal policy( accumulative reward = retrun을 최대화하는 policy)를 찾는 것이다. 또한 input s. output a로 보는 점에서 regression이나 classification과 비슷하다고 볼 수 있다.

• Action : Agent가 실제 행동한 내용을 말함. Policy에 의해 도출되고. a로 표현한다.

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

• Return : G_t로 표현되고, agent가 time step t로부터 앞(t+1)으로 받게될 discounted Reward의 누적 합이다. 예. G_t = R_(t+1) + r*R_(t+2) + r^2*R_(t+3)+ ...r^(T-1)*R(T). T = Terminal state

또한 중요한것은 Return의 expectaion이 state-value function v(s)=E[G_t|S_t=s]이라고 한다.
여기서 agent의 행동방식 policy 파이(ㅠ)를 고려한다면 v_ㅠ(s)=E_ㅠ[G_t|S_t=s]

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

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

• Value : state의 가치를 말함. 가치란 해당 state에 도달했을때의 reward와 그 state이후에 얻게되는 reward를 모두 반영해서 계산됨. v(s)로 표현. agent가 value를 greedy하게 Action을 선택한다고 했을때, Agent는 이동가능한 State중 제일 높은 V(s)로 이동함.

이것이 근시안적인 선택으로 보이지만, Value의 정의 자체가 장기적인 가치를 나타내기 때문에, Greedy하게 학습해도 장기적인 보상을 따르는 Agent로 학습이 됨. 보통 v(s)로 표기하면
state-value function이고, q(s,a)로 표기하면 action-value function

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

• Action value : state s에서 특정 action a를 한 후 policy ㅠ를 따랐을때 얻을 수 있는 Return의 기대값. Quality의 Q(s,a)로 표현됨. value function을 state에 대해 보지 말고, action에 대해 본다면, 그것이 바로

action value function이다. s에서 a를 한 후 임의의 정책 ㅠ를 따르는 action value funtion q는 q_ㅠ(s,a) = E_ㅠ[G_t|S_t=s, A_t=a]로 정의된다.Q-value로도 불림.

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

• MDP(Markov Decision Process) : 1.처음 어떠한 상태로부터 시작해서 현재 상태까지 올 확률

2. 바로 전 상태에서 현재 상태까지 올 확률. 1,2가 같을때 상태(state)가 Markov하다고 일컬어진다. 식으로 나타내면 결국 바로 전 상태라는 것은 처음부터의 모든 상황에 대한 정보를 포함하고 있다고 보는 것이다. 예를들어, 바둑의 게임 중간의 바둑판 상황(state)는 이전까지의 모든 정보를 포함하고 있다라고 가정하는 것. 그래서 어떤 문제가 MDP라는 것은
가 정의된 문제라고 본다.(단, S,A는 finite)

• Bellman equation : value를 구하는 것이 RL에서 중요한데, 이것을 재귀적 혹은 Dynamic Programming적 관점에서 바라봄으로써, 현재 state의 value와 다음 state의 value의 관계를 식으로 표현한 것. v(s)는 두 파트의 합의 기대값으로 표현됨. 1. S_t = s에서 받는 즉각적 보상 R_t+1. 2. S_t+1의 value에 discounted factor(r)가 곱해진 r*v(S_t+1). 이를 식으로 표현하면, v(s) = E[R_t+1 + r*v(S_t+1) | S_t = s] 마찬가지로 action-value function을 Bellman equation으로 나타내면, q(s,a)=E[R_t+1 + r*q(S_t+1,A_t+1) | S_t=s, A_t=a]

자세한 내용은 이웅원님의 깃북 참조. Bellman expectation equation과 동일.

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

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

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

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

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

• Control : 현재의 value function을 토대로 더 나은 policy를 구하는 것. input으로 MDP를 주면, output으로 optimal value function v_*와 optimal policy ㅠ_*를 도출.

• Actor-Critic :

• Rollout : 주로 Trajectory의 일부? 혹은 전체를 얻어내기 위해 시뮬레이션 해보는 것을 뜻한다. 에이전트가 상호작용하며 만든 (s,a,r,s',a'... )와 같은 경로. Trajectory는 단순 경로를 의미한다면 Rollout는 리워드가 포함된 개념으로 많이 쓰이는 듯 하나, 구분 없이 쓰일 때도 있다.

• 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 k가 1씩 증가됨. next state를 결정하는데 있어 policy가 사용되기에 policy가 얼마나 좋은가를 판단하는 evaluation이 됨.

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)를 통해얻은 경험을 통해 배워나가는 것. 어떤 시행착오(S,A,R,S')를 sampling하면서 학습하는 방법엔 다음 두가지가 있다. 1) Monte-Carlo, 2) Temporal Difference .

• Monte-Carlo : episode 즉, 처음state부터 마지막 state까지 진행하면서 얻은 리턴 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가 될 확률이 큼. 그래서 variance가 높음. 반면 random인 만큼 치우쳐지는것은 없어서 bias는 없다. 이는 다시말하면 Return이 value의 unbiased estimate이기 때문에(v(s) = E[G_t|s_t=s]) bias가 없다. 또한 MC에서는 policy를 update할때 즉, contol과정에서는 v대신 q를 사용하는데, v를 쓰면 reward(s,a)와 p(s'|s,a)를 알아야 하기 때문에, 이건 Model-free과정에서는 모르기 때문에 q를 씀. 즉, 단순히 q를 최대화 하는 a를 선택.

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

• On Policy : On Policy과 Off Policy를 구별하는 방법은 데이터를 어떻게 얻느냐 이다. 현재 상황에서 현재 best policy로 행동 했을때 얻는 정보는 On Policy data라고 할 수 있다. 당연하게도 남의 경험보단 내경험이 중요하듯이

Off Policy data보다 중요하다. 하지만 Off Policy data가 얻기가 쉽다.(남의 경험은 많이 있다..)

• Off Policy : 데이터를 자신이 아닌 다른곳으로 부터 얻는 곳이다. 다른곳이란 예를들어, 시뮬레이션 프로그램이다. 예를들어, 인생에서 남의 경험에 대한 이야기를 듣고 우리 삶에 반영하는 것도 Off Policy라고 할 수 있을 것같다. 또한 나의 예전 Policy로 얻은 데이터들 즉, 이제까지 쌓인 데이터들이 전부 Off Policy data가 된다.

그래서 Off Policy 데이터는 믿을 수가 없는 놈이기도 하다. 그래서 쓸때는 신뢰도를 측정하기 위한 방법도 고려해야 한다. 그 신뢰도를 바탕으로 현재 Policy를 수정할 것인지 아닌지를 고려해야함.

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