Ssong

반갑습니다 :)

[RL] Lecture 3: Planning by Dynamic Programming

Date:     Updated:

카테고리:

태그:

Planning 이란?
→ Environment(env)에 대한 model이 있을 때(model-based), 더 나은 Policy를 찾아나가는 과정

1. Introduction

1.1 What is Dynamic Programming?

image

  • 복잡한 문제를 바로 해결하기 어려울 때, 여러개의 작은 Sub 문제들로 나누고,
    나눈 문제들의 솔루션을 찾아 그것을 이용해 더 큰 부분 문제를 해결해 나가는 하나의 방법론

1.2 Requirements for Dynamic Programming

  • model-free : env가 어떤지 모르는 상황, 완전한 정보가 없을 때
  • model-based : env에 대한 model이 있고, 어떤 action을 하면 어떤 확률로 어느 State에 도착을 할지 등 모든 상황을 알 경우
    • Planning에서의 DP방식은 model-based 환경에서 진행됨

DP가 문제를 해결하기 위해 필요한 요구 조건

  • Optimal substructure : 하나의 큰 문제에 대한 solution은 여러 개의 작은 부분 문제들의 solution으로 분할할 수 있어야 한다.
  • Overlapping subproblems : 어떤 부분 문제의 solution은 상위의 부분 문제를 해결하기 위하여 재사용(recur) 될 수 있다.
    이를 위해 solution는 저장되고(cahsed), 재사용된다(reused).

⇒ MDP는 두 조건을 충족한다. (DP를 적용할 수 있다)

  • Bellman equation은 재귀적으로 표현될 수 있다.
  • value function이 계산한 value(Solution)은 저장해두었다가 Policy를 평가/갱신하기 위해 재사용된다.

1.3 Planning by Dynamic Programming

  • DP는 MDP에 대한 모든 지식(state transition probability, reward 등)을 알고 있다고 가정한다.
    • ⇒ Model based
  • DP는 MDP에서 planning에 사용된다.

Prediction

  • MDP와 Policy가 주어졌을 때, 그 Policy를 따라 Agent가 수행했을 때의 Value function을 계산하는 문제
    • input : MDP \(<S,A,P,R,γ>\) and Policy \(π\) or MRP \(<S,P^π,R^π,γ>\)
    • output : Value function \(v_π\)

→ 아무리 이상한 Policy를 줘도 상관없이, 그 Policy에서 내가 얻을 수 있는 최대의 Return을 구함

control

  • MDP가 주어졌을 때, optimal value function, policy를 찾는 문제
    • input : MDP \(<S,A,P,R,γ>\)
    • output : optimal value function \(v_*\), optimal policy \(π_*\)

1.4 Other Applications of Dynamic Programming

DP는 다양한 다른 문제의 해결을 위해 사용된다

  • Scheduling algorithms
  • String algorithms (e.g. sequance alignment)
  • Graph algorithms (e.g. shortest path algorithm)
  • Graphical models (e.g. Viterbi algorithm)
  • Bioinformatics (e.g. lattice models)

2. Policy Evaluation

2.1 Iterative Policy Evalutaion

  • Problem : 주어진 Policy \(π\)를 평가하는 것, 즉 Policy를 따랐을 때의 Value function \(v_π(s)\)를 찾는 것을 목적으로 한다. (Prediction)
  • Solution : Bellman expectation equation을 이용하여 iterative한 방법을 적용한다.
    • \(v_1\) → \(v_2\) → \(...\) → \(v_π\)
  • Using Synchronous backups (backup: cashed 잠깐 메모리에 저장)
    1. each iteration K+1
    2. for all states s

    3. update \(v_{k+1}(s)\) from \(v_k(s')\)

      → 전 단계 k에서의 value function을 이용하여 현재 단계 K+1에서의 value를 갱신한다.

      (s’ 은 s에서 갈 수 있는 가능한 모든 state)

    ⇒ 위 과정을 반복하면, \(v_π(s)\)에 수렴하게 된다.

  • Bellman Expectation Equation

image 1

과정 (반복)

  • k+1 단계에서는 k단계에서보다 더 정확한 value 값을 구하고 싶다.
  • evaluate하는 state s에서 갈 수 있는 가능한 모든 state s′에서의 value를 사용하여 갱신한다.

결과

  • next state인 s’의 value일수록 지금까지 policy를 따라 진행하면서 실제로 얻은 정확한 reward r의 값이 더 많이 존재하기 때문에 점점 더 정확한 value를 가지게 된다.
  • 따라서 가장 초기 init 상태일 때의 value function의 값은 모두 정확하지 않더라도 정확한 값인 “reward”가 고려되기 때문에 최종적으로 \(v_π(s)\)에 수렴할 수 있게 된다.

2.2 Evaluating a Random Policy in the Small Gridworld

image 2

현재 MDP와 Policy가 주어졌기 때문에 Prediction Problem이다.

  • Undiscounted episodic MDP (\(γ\) = 1) (미래 지향적)
  • Nonterminal States : 1~14 / Terminal State : 음영부분
  • Grid 밖으로 나가는 Action은 없음 (제자리 유지)
  • Reward : -1 / Policy : N E S W 모두 0.25의 확률

구하려고 하는 것 : Value function \(v_π(s)\) → 주어진 Policy \(π\)를 평가하는 것, 즉 Policy를 따랐을 때의 Value function을 찾는 것

image 3

image 4

image 5

어떤 주어진 (바보같은) random policy로 평가만 했을 뿐인데, 평가한 value function을 가지고 greedy하게 움직이면 optimal policy를 찾는 것이 가능하다. ⇒ Policy Evaluation

무한히 갈 필요가 없이 Greedy 하게만 움직여도 최적 policy를 찾을 수 있음

3. Policy Iteration

3.1 How to Improve a Policy

image 6

주어진 Policy\(π\)로

  • Policy evaluate : Value function을 찾는 것
  • Policy improve : greedy value function을 찾아 움직이는 새로운 policy 생성

⇒ Evaluate와 Improve를 반복해서 수행하면 점점 policy가 optimal policy \(π_∗\)에 수렴하게 된다!

3.2 Policy Iteration

image 7

Policy 개선 과정

  1. 초기 policy \(π\)를 평가 [evaluation]
  2. 계산된 value function에 대하여 greedy하게 선택하는 새로운 policy \(π'\)로 policy를 개선 [improvement]

  3. 개선된 policy \(π'\)를 다시 평가 [evaluation]

    ⋯

⇒ 계속 반복하면 Optimal Value function, \(π\)을 구할 수 있다.

⇒ 어떤 Policy라도 evaluation과 improvement가 가능하다. (optimal policy를 구할 수 있다.)

3.3 Policy Improvement

Q1. greedy하게 선택하는 새로운 policy는 무조건 기존 policy보다 좋다고 할 수 있는가?

  • 어떤 deterministic 한 policy, a = \(π(s)\)가 있다고 하자
  • 우리는 greedily하게 행동하는 새로운 policy를 정의하면서 policy를 improve시킬수 있다.

image 8

여기서 \(q_π(s,a)\)는 \(π\)를 따랐을 때 상태 s에서 행동 a를 했을 때의 action-value

\(π'(s)\)는 현재 상태 s에서 가장 높은 \(q_π(s,a)\)를 가지는 행동을 선택하는 정책

새로운 정책 \(π'(s)\)는 상태 s의 가치(value)를 향상시킨다.

image 9

즉, 새로운 정책 \(π'(s)\)는 greedy하게 행동하여 \(π(s)\)보다 더 나은 정책이 된다.

image 10

따라서, 새로운 정책의 가치 \(v_{π'}(s)\)는 기존 정책의 가치 \(v_π(s)\)보다 크거나 같다

image 11

⇒ 따라서 모든 state에서 \(π'\)를 따랐을 때의 value가 \(π\)를 따랐을 때의 value보다 높기 때문에 policy는 항상 improvement 된다는 것을 보일 수 있다.

Q2. 개선된 policy는 최종적으로 optimal에 수렴하는가?

만약 개선이 멈췄을 때

image 12

위 등식이 성립을 한다면

image 13

Bellman optimality equation이 만족한다.

그러므로 모든 s에 대해서 \(v_π(s)\) = \(v_*(s)\) 이므로

\(π\)는 optimal policy이다.

3.4 Modified Policy Iteration

Q. Policy iteration을 수행할 때, evaluation단계에서 \(v_π\)가 수렴할 때까지 반드시 진행해야 하는가?

Idea.

  • k=∞보다 조금 더 일찍 종료할 수는 없을까?
  • iteration 횟수 K를 정해두고 수행하면 안될까?
    • small gridworld에서는 K=3은 optimal policy를 구하기에 충분했다

A. \(v_π\)가 수렴할 때 까지 진행하지 않아도 된다. (Perfectly reasonable algorithm이다.)

극단적인 경우, 단 한번만 policy evaluation을 진행하고 바로 policy improvement 단계로 넘어가도 된다.

정확히 수렴하지는 않았지만 달라진 policy에 대한 value가 업데이트 되었기 때문

4. Value Iteration

4.1 Principle of Optimality

image 10

  • Optimal Policy는 2개의 요소로 나눌 수 있다.
    • optimal first action \(A_*\)
    • 다음 State 인 S’부터는 optimal policy를 따라서 이동한다.

⇒ 첫번째 action인 optimal action, 그 이후 상태에서도 optimal policy를 따르는 구조

Policy \(π\)가 state s로부터 optimal value를 얻는다면, \(v_π(s)\) = \(v_*(s)\)이다.
↔ S 로부터 도달가능한 모든 S’에 대해 \(π\)가 S’로부터 optimal value를 얻으면, \(v_π(s')\) = \(v_*(s')\)

⇒ S에서 구한게 optimal value이면, 다음 state인 S’에서 구한것도 optimal value 이다.

Principle of Optimality

  • 어떤 큰 문제를 sub problems으로 나눌 수 있다.
  • 각 sub problem에서 최적 값을 계산하면, 전체 문제에서도 최적 값을 가지게 된다.

⇒ 즉 현재의 최적값을 보장하려면 도착지점 이후의 값들도 항상 최적이어야 한다

4.2 Deterministic Value Iteration

  • \(v_∗(s')\)를 구하는 문제는 여러개의 sub problem들로 표현할 수 있다.
  • Sub problems의 \(v_*(s')\)의 solution을 알면 one-step lookahead를 통해 \(v_*(s)\)해결이 가능

image 11

  • Bellman Optimality Equation

  • Intuition : goal부터 시작하여 직전 step을 알아나가는 과정을 통해 minimum거리 계산이 가능
  • Loopy, Stochastic MDPs에서도 적용 가능

Policy Iteration: policy Evaluation, Improvement를 반복하였고, policy가 존재 / bellman expectation equation 사용(policy를 따랐을 때의 value fn이 어떻게 되나)

Value Iteration: 명시적인 policy없이 value만 사용해서 iterative하게 update(policy evaluation이 없다) / bellman optimality equation 사용

4.3 Example: Shortest Path

image 12

policy가 없이 랜덤한 값으로 주어지고, 한 step은 bellman optimality equation이 적용

small problem 경우 Goal 부터 해나가도 되지만, 현실에서는 terminal state 주변에 어떤게 있는지 알기 조차 어렵다.

모든 state를 step마다 synchronize하게 Update를 하고 다음으로 넘어간다.

image 11

  • Bellman Optimality Equation

\(V_1\) : 임의의 값 0으로 모든 state 채워 넣는다.

\(V_2\) : \(V_1\)의 \(v_*(s')\)이 0이고 \(R_s^a\) = -1 이므로 모든 state = -1

\(V_3\) : \(V_2\)의 \(v_*(s')\)이 -1이고 \(R_s^a\) = -1 인데 Goal은 0이므로 계산해보면 -1

가까운 값부터 확정이 되는 모습 관찰이 가능하다.

모든 state의 value를 구할 수 있고, policy 또한 계산 가능하다.

4.4 Value Iteration

  • problem : optimal policy \(π\)를 찾는 것을 목적으로 한다.
  • solution : Bellman optimality equation을 이용하여 iterative한 방법을 적용한다.
  • \(v_1\) → \(v_2\) → ⋯ → \(v_∗\)
  • synchronous backup을 사용한다.
    1. each iteration K+1
    2. all states \(s∈S\)
    3. update \(v_{k+1}(s)\) from \(v_k(s')\) → 전 단계 k에서의 value function을 이용하여 현재 단계 K+1에서의 value를 갱신한다. (s’ 은 s에서 갈 수 있는 가능한 모든 state)

    ⇒ 위 과정을 반복하면, \(v_π(s)\)에 수렴하게 된다.

  • Policy iteration과 다르게 explicit한 policy가 주어지지 않는다.
  • 중간 Value function은 어떤 policy의 value도 아니다

image 13

4.5 Synchronous Dynamic Programming Algorithms

image 14

Synchronous DP ⇒ 시간복잡도가 큰 문제가 있다.
Synchronous : 한 time에 모든 State를 Update

5. Extensions to Dynamic Programming

기본적인 DP 방법을 적용하여 RL문제를 해결하는 것은 Computation 적으로 비효울이 너무 크기 때문에 여러가지 방식을 활용한다.

  • DP는 모든 States가 Parallel하게 backup 되는 synchronous 방식을 사용한다.
  • 어떤 States만 backup하거나, 순서를 다르게 하는 asynchronous DP도 존재한다.
  • asynchronous 방식을 사용하면 computation 시간을 줄일 수 있고, 모든 State가 언젠가 모두 선택된다는 가정 하에 converging함을 보장 가능하다.

5.1 Asynchronous Dynamic Programming

  • In-Place DP

    • 기존 방법 (synchronous) : k번째의 value function에 대한 정보와 k+1번째의 value function에 대한 정보를 따로 저장해야하기 때문에 2배의 저장공간을 필요로 한다.

      image 15

    • In-Place : 갱신된 값과 갱신되지 않은 값을 저장하기 위한 공간을 따로 할당하지 않고 바로 덮어씌워서 업데이트 한다.

      image 16

      • 다른 state에 대해 value를 계산할 때는 이제 바로 직전에 갱신된 값을 사용하게된다.
      • 이렇게 구현하더라도 문제를 풀 수 있다는 것은 증명되어있다.
  • Prioritised Sweeping
    • state에 우선순위(priority)를 두어, value를 업데이트할 때 중요한 state를 먼저 갱신한다.

    • 중요한 state? → Bellman error가 큰 state (두 Table의 값 차이가 큰 것)

      image 17

    • Priority Queue를 통해 쉽게 구현 가능
  • Real-Time DP

    • state의 공간은 매우 큰데 실제로 agent가 유의미하게 자주 방문하는 state는 그리 많지 않을 때,
      Agent가 실제로 방문한 state를 먼저 업데이트한다.

      image 18

5.2 Full-width and sample backups

image 19

  • Full-width backup
    • DP에서 사용되는 방법론
    • sync or async 상관없이 모든 state와 action이 고려된다.
  • Advantage
    • DP는 midium-sized problems에서 효과적이다.
  • Disadvantage
    • 큰 문제에서는 너무 많은 state를 고려해야하므로 불가능하다. (모든 state, action 고려)
    • state의 개수가 늘어날 수록 expotentially하게 시간 복잡도가 커지므로, one backup이 너무 비싸진다.

⇒ 결론: 비효율적인 full-width backups

image 20

  • Sample backup
    • large MDP에서는 Full-width backup으로 구현하기 매우 어렵다.
      (state수가 늘어날 수록 계산량이 exponential하게 변화함)
  • Advantage
    • state가 많아지더라도 고정된 sample의 수만 확인하기 때문에 cost가 일정하다.
    • Model-free인 문제에서도 수행할 수 있다.
      • 어디 도착할지 몰라도 backup을 할 수 있다.
    • break the curse of dimensionality

    맨 위로 이동하기

RL 카테고리 내 다른 글 보러가기

댓글남기기

최근 글 10 개 :)