Model-based Reinforcement Learning

Model-based & Model-free Reinforcement Learning

---

강화학습 알고리즘은 아주 크게 2가지가 있다. 하나는 Model-based고 하나는 Model-free.
(강화학습 알고리즘의 종류는 계층적으로 딱 나눌 수 없는데, Model-based면서 Model-free인 것도 있고 뭐 그렇다...)
Sutton 책 기준에서 Model-based RL이라고 하면 주로 "Planning"하는 것을 말하고 Model-free는 주로 "Learning"하는 것을 말한다.
Planning은 Environment의 Model을 어느정도 알거나 주어진 상태에서 문제를 푸는 것을 말한다. 즉 어떤 action에 있어 좋은 reward를 받게 끔 policy를 improve한다.
Learning은 Environment의 Model은 모르지만 interaction을 통해 문제를 푸는 것을 말한다.

Dynamic Programming은 Planning에 속하는데, Environment의 Model, 즉 Reward와 State Transition Matrix(Dynamics)에 대해 안다는 전제로 Bellman Equation을 사용해 문제를 풀게된다. 좀 더 현실적으로 설명해보자면 Model-based는 System(Model)을 미리 안다면 강화학습 문제를 Control 문제로 바꿀 수 있다는데서 착안한다.
강화학습은 Dynamic Programming을 기반에 두고 발전하긴 했지만 최근 좋은 성능을 내는 RL은 주로 Model-free 알고리즘들이다.(그렇다고 해서 Model-free가 모든 상황에서 무조건 좋은 것은 아니다.)

 

If, after learning, the agent can make predictions about what the next state and reward will be before it takes each action, it's a model-based RL algorithm.

단순하게 생각하면, train이 끝난 후 agent가 action을 취하기 전 다음  state 와 reward를 예측할 수 있다면 model-based algorithm이라 할 수 있다.

 

Learning(model-free)

• The environment is initially unknown, ignore model(environment, inner working system)
• Depend on sampling and simulation
• The modeling step is bypassed altogether in favor of learning a control policy directly
• The agent interacts with the envrionment
• The agent improves its policy

 

Planning(model-based)

• A model of the environment is known
• Build own representation of the reality or the environment agent are in
  • we call own representation of the environment : Predictive Model, World Model, M Model, Learned Dynamics Function
• The agent performs computations with its model(without any external interaction)
• The agent improves its policy
  a.k.a deliberation, reasoning, introspection, pondering thought, search
  
  
  

Just because there is a model of the environment implemented, does not mean that a RL agent is "model-based". To qualify as "model-based", the learning algorithms have to explicitly reference the model:

- Algorithms that purely sample from experience such as Monte Carlo Control, SARSA, Q-learning, Actor-Critic are "model free" RL algorithms. They rely on real samples from the environment and never use generated predictions of next state and next reward to alter behaviour (although they might sample from experience memory, which is close to being a model).

- The archetypical model-based algorithms are Dynamic Programming (Policy Iteration and Value Iteration) these all use the model's predictions or distributions of next state and reward in order to calculate optimal actions. Specifically in Dynamic Programming, the model must provide state transition probabilities, and expected reward from any state, action pair. Note this is rarely a learned model.

- Basic TD learning, using state values only, must also be model-based in order to work as a control system and pick actions. In order to pick the best action, it needs to query a model that predicts what will happen on each action, and implement a policy like 𝜋(𝑠)=argmax𝑎∑𝑠′,𝑟𝑝(𝑠′,𝑟|𝑠,𝑎)(𝑟+𝑣(𝑠′)) where 𝑝(𝑠′,𝑟|𝑠,𝑎) is the probability of receiving reward 𝑟 and next state 𝑠′ when taking action 𝑎 in state 𝑠. That function 𝑝(𝑠′,𝑟|𝑠,𝑎) is essentially the model.

Kinds of Model-based RL

 

• Learn the Model : mainly focuses on how to build the environment model.
• Given the Model : cares about how to utilize the learned model.

그리고 Model-based RL은 또 크게 Learn the Model, Given the Model로 나뉘는데 Learn the Model은 base plicy를 운영(랜덤이거나 이미 학습된 policy)하고, trajectory를 관측한다. 이 때 샘플링 된 데이터를 사용해 모델에 적합하여 단순화된 환경 모델을 추가로 학습하게 된다.

 

그리고 Model-based는 Model-free와 다르게 무엇을 learn 할 것인지 정의하기 어렵다.

What to learn

• Background:Pure Planning - MBMF
• Expert Iteration - Exlt, AlphaZero
• Data Augumentation for Model-free Methods - MBVE, World Model
• Embedding Planning into Polices - I2A

 

 

Component of Model-based RL

---

Model

• Model : mimic environment
• Controller : optimize policy

Model-based에서 'Model'은 Environment의 behavior을 mimic하는 것을 말한다. 더 general하게는 어떻게 환경이 behave 할 것인지에 관해 inference하는 것을 말한다. 그리고 Controller는 policy를 optimize하는 것을 말한다.

behavor of environment의 모든 것(pure environment)까지는 다 일지 못하더라도 Simulator에 의해 생성된 experience(Simulated Experience)를 얻어 model로 사용할 수 있다. 그리고 Model은 experience를 통해 reward function과 state transition을 통해 현재 state에서 다음 state에 대한 transition과 이때 받은 action에 대한 reward를 Agent에게 전달하게 된다.

스타크래프트를 생각해보면, 우리는 게임의 action consequence를 이미 안다. 예를 들어 (까만화면에서 유닛으로 움직임 -> Scout map), (적공격 -> 적죽임), (모든 적 죽임 -> 승리), (많은 미네랄을 얻음 -> more units -> 승리할 확률 높아짐) 등등.. 이처럼 model의 experience가 존재한다는 것은 (state, action)으로 이루어진 trajectory들이 있고 이를 사용해 기존의 value function을 업데이트한다는 것을 말한다.

 

planning은, experience의 trajectory를 통해 value function을 업데이트하고, update된 value function을 바탕으로 현재 policy π  를 improve하는 것이다. planning은 모델이 준 experience를 통해 학습을 하기 때문에 Sample efficient하고 빠르다. 그에 비해 Model-free는 아주 많은 interaction을 통해 학습해야 하기 때문에 많은 시간이 걸린다.

Strength and Weakenss

Strength

• Reduce number of interaction with the real envrionment
• High efficiency, learning speed up

Weakness

• final scores are lower than model-free algorithm(in SimPLe)
• cumulative error will occur in extrapolated envrionment during controller's new policy
• hard to approximate real world(failed to produce useful information)(in SimPLe)
• effective model learning method is needed
• if training is seperated at all, model dosen't care controller during model traning

Sample Model & Distribution Model

그리고 Model은 크게 두가지로 나눌 수 있다.
Sample Model은 experience에서 주어진 확률을 가진 데이터를 샘플링하면서 결과를 내는 모델이고
Distribution Model은 experience에서 주어진 확률을 가지고 조건부 확률 계산 등을 통해 data의 분포를 수치적으로 계산하는 모델이다.
예를 들어서 주사위를 던져서 나온 수를 결과로 갖는 문제가 있다고 할 때, 주사위를 직접 던져서 랜덤하게 나온 수를 가져오는 것은 Sample Model이고, 각 수가 나올 확률을 가지고 원하는 조건에 대한 확률을 계산하면 Distribution Model이다.

Distribution Model은 모든 경우의 수에 대한 확률 정보를 저장하기 때문에 Sample Model에서 얻을 수 없는 전체 distributuion에 대한 expectation이나 variance를 구할 수 있고 event가 많으면 이 값은 실제 값과 근사하게 된다. 때문에 Sample Model에 비해 더 많은 정보를 inference가 가능하지만 모델에 크기에 따라 연산량이 많아진다. Sample Model은 Environment 정보를 가지고 데이터를 샘플링 하기 때문에 모든 State에 대한 정보를 가지고 있을 필요가 없어 필요한 메모리도 적다.

Sample Model 방식은 Model-free 방식과도 비슷하다. Model-free 알고리즘들은 주로 environment에서 나온 real sample들에 의존하며 다음 state와 reward를 예측하거나 behavior를 변경하지 않는다. 이때 model에 가까운 experience memory에서 sample을 추출할 수도 있다. 단 model-free는 policy를 업데이트할 때 model의 dynamics(transition, reward function)을 사용하지 않는다.

 

Q-Planning

---

Q-learning은 model-free 알고리즘이다.

𝑄(𝑆𝑡,𝐴𝑡)←𝑄(𝑆𝑡,𝐴𝑡)+𝛼(𝑅𝑡+1+𝛾max𝑎𝑄(𝑆𝑡+1,𝑎)−𝑄(𝑆𝑡,𝐴𝑡))

Model-free 알고리즘은 dynamics(transition, reward function)을 사용하지 않고, optimal policy를 estimate 한다. 때문에 value-function과 policy를 둘 다 estimate한다. 위 Q-learning 식을 보면 transition과 reward function을 사용하지 않음을 알 수 있다. model-free인지 model-based인지 구분하는 방법은 알고리즘에서 dynamcis가 쓰였는지를 보면 된다. Q-learning식의 Rt+1은 action을 취한 후 가게된 다음 state의 리워드일 뿐 미리 알 수 있는 것은 아니다.

 

Model이 있다면 Planning이 가능해지고 이를 통해 simulated된 experience를 생성할 수 있게 된다. 이를 Q-learning에 접목시킨 것이 Q-planning이다. 매 step마다 table로 저장된 Q value를 sampling해서 그 값을 이용해 update한다. model에 random sampling된 state와 action을 전해주면 이에 따른 next state와 reward는 모델에서 내보내주고 이를 사용해 update한다.

이렇게 되면 environment와 interaction 없이도 policy를 improve할 수 있게 된다. 실제 environment 상에서 action을 취한 결과로 policy를 업데이터 하지 않더라도 action이 발생할 주기 내에 기존의 experienc를 가지고 Q value를 업데이트할 수 있는 것이다. 실제 행동하지 않더라도 머릿속으로 상상하면서 배우는것과 같은 과정이라고 한다.

 

---

사람의 지능도 마냥 Model-free 알고리즘대로 동작하지 않는다. 실세계의 환경은 매우 복잡하고 지속적으로 변하기 때문에 Model-free 알고리즘만으로는 Target에 빠르게 도착하는 것은 어려울 것이다. Underlying Transition Mechanism을 더 잘 이해하는 species가 생존 경쟁에 유리한 것이다. 때문에 완전 Model-based 알고리즘만을 가지고는 좋은 성능을 내지 못할지라도 Model-free와 Model-based의 knowledge를 잘 조합하면 좋을 수 있다. 2017년도에 I2A논문을 시작으로 Model-based와 Model-free 네트워크를 arbitration한 모델들이 나왔고 그에 관련한 논문들을 읽어보려고 한다.

 

 

 

 

References

 

https://www.slideshare.net/DongMinLee32/planning-and-learning-with-tabular-methods
https://people.cs.umass.edu/~barto/courses/cs687/Chapter%209.pdf
https://ai.stackexchange.com/questions/4456/whats-the-difference-between-model-free-and-model-based-reinforcement-learning
https://bair.berkeley.edu/blog/2019/12/12/mbpo/
https://talkingaboutme.tistory.com/entry/RL-Model-Planning