[RL] MDP, Value Iteration, Policy Evaluation, Maximum Entropy Formulation

📌프로그래머스 인공지능 데브코스 6기 강화학습 스터디

Foundations of Deep RL Series by Pieter Abbeel 1강을 정리한 글입니다.

---

목차

1. Markov Decision Processes(MDPs)

2. Exact Solution Methods

• 2.1 Value Iteration
• 2.2 Policy Evaluation

3. Maximum Entropy Formulation

L1: MDPs and Exact Solution Methods

강화학습은 2013년 Atari 게임부터 시작해 알파고, 로봇 조종, 알파스타 등 발전해왔다.

1. Markov Decision Processes(MDPs)

에이전트는 action을 하고, 그로 인해 environment는 변하고, 그 때마다 reward를 받는다. 에이전트는 이 reward를 최대화하는 action을 선택한다.

discount factor 감마: 크면 미래 가치도 신경 씀, 작으면 현재 가치가 훨씬 더 중요함

2. Exact Solution Methods

2-1. Value Iteration

1) Optimal Value Function V*

: state s에서 시작해서 optimal하게 act했을 때 discounted reward의 sum

→ transition probability가 생기면 이렇게 recursive하게 된다.

2) Value iteration

3) Value Iteration Convergence

Theorem) Value iteration은 수렴하고, 그 때 optimal value function V*로 수렴한다.

Exercise 1: Effect of Discount and Noise

optimal policy에 environment가 미치는 영향: 환경에 따라 optimal $\pi$는 달라진다.

• $\gamma$: 크면 미래도 생각 → 멀지만 큰 보상 +10 선택
• noise: 작으면 내가 가고자 하는대로 갈 수 있으므로 -10 cliff도 risk 가능 → punishment와 가까워도 짧은 루트 선택

4) Q values

Q: state s에서 action a를 한 후, optimal하게 act했을 때의 예측되는 utility

2-2. Policy Evaluation

value iteration에서는 모든 action을 해보고 $\underset{a}{max}$를 수행하지만, 이건 policy가 정해져있다.

• stochastic policy

  

1) policy iteration

policy 평가 후 개선시키는 두 단계로 진행된다.

3. Maximum Entropy Formulation

하나의 optimal policy를 찾는 게 아닌, near-optimal solution의 distribution을 찾는다면?

• 더 robust한 policy를 찾을 수 있다: 환경이 변하더라도 near-optimal한 다른 policy를 고를 수 있다.
• 더 robust한 학습을 할 수 있다: data collection을 할 때 maximum entropy approach를 통해 data를 얻는 방법(exploration)을 다양하게 할 수 있다.

3-1. Entropy

• 확률변수 X의 불확실성(uncertainty)에 대한 measure
• X를 인코딩하는 데 필요한 비트 수

X=1 일 확률이 0 또는 1일 때는 엔트로피가 낮지만, 0.5로 어느 쪽이 나올지 모를 때는 엔트로피가 높다.

1) Maximum Entropy MDP

편의를 위해 discount factor $\gamma$를 제외하고 보자.

일반적인 MDP에서는 sum of reward의 기댓값을 최대화하는 policy를 찾고자 한다.

그러나 entropy를 고려하게 되면 뒤에 policy의 entropy term을 더해줘서 policy의 entropy도 함께 최대화하고자 한다.

($\beta$: trade-off factor)

• $\beta$가 크면: entropy를 더 다양하게 만들고자 함 → 보상은 적음
• $\beta$가 작으면: entropy를 신경쓰지 않고 optimal한 행동만 하고자 함 → 많은 보상

→ 이런 trade-off가 있는데 왜 entropy를 고려 해야하나?

entropy를 고려하면 (현재) policy를 더 비판적으로 보는 것. 따라서 exploration을 다양하게 하면서 data collection을 할 수 있고, 이를 통해 더 나은 trial and error learning을 할 수 있다.

2) Max-ent Value Iteration

그렇다면 이렇게 entropy를 고려하는 MDP는 어떻게 풀 수 있나?

→ constrained optimization 수행 by 라그랑주 승수법

3) Max-ent for 1-step problem

높은 엔트로피를 가지며 보상을 최대화하고자한다.

우리의 objective function은 다음과 같다.

이 때 $\pi(a)$는 확률이기 때문에 다 더했을 때 1이 되어야 한다. 이를 라그랑주 승수법으로 푼다.

이를 풀면 optimal max-ent policy가 나온다.

어떤 행동을 할 확률($\pi(a)$)은 그 행동과 관련된 지수화된 보상($exp(r(a))$)이다: 보상이 높은 action을 할 확률은 높고, 보상이 낮은 action을 할 확률은 낮다.

이를 어느정도 extent로 할 것인지를 정하는 것은 엔트로피와 보상 사이의 trade-off를 조절하는 인자 $\beta$에 달렸다.

• $\beta$가 크면 → 보상 작음 → 모든 action이 비슷한 확률
• $\beta$가 작으면 → 보상 큼 → action 별 확률 차이 큼

이 때 Z는 확률로 만들어주기 위한 normalization factor이다.

이 때 optimal value 를 계산해보면 다음과 같은데, 이는 결국 softmax함수이다.

그 말은 기존 MDP에서처럼 바로 maximum을 뽑는 게 아니라 value에 softmax를 취한다는 것이다. 또한 여기서 $\beta$의 역할은 softmax의 sharpness를 결정하는 것이다.

• $\beta$가 크면 → 부드러운 softmax
• $\beta$가 작으면 → 날카로운softmax

4) Max-ent Value Iteration

Max-ent에서의 새 벨만 방정식은 아래의 첫번째 식과 같으며, 이 때 Q value로 묶으면 두번째 식으로 쓸 수 있다.

정리하자면 Max-ent의 V와 policy는 다음과 같이 softmax로 나타낼 수 있다.