[RL] Model-based Planning

Bard·2025년 6월 10일
RL

Reinforcement Learning

목록 보기
8/10

Planning and Learning

Planing: 환경의 model을 아는 상태에서, 그 모델과만 상호작용하며 policy를 개선하는 것

Requirements for Dynamic Programming

다이나믹 프로그래밍을 위해 두가지 특징이 필요하다.

  • Optimal substructure
    • Principle of optimality가 적용되어야 함
    • Optimal solution이 subproblem들로 나누어질 수 있음
  • Overlapping subproblems
    • subproblem들은 여러번 다시 발생함
    • solution들이 캐시되고, 재사용될 수 있음.

Markov decision process들은 이 두 속성을 모두 만족함

  • bellman equation은 재귀적 분할을 가능하게 함
  • value function은 solution을 저장하고 재사용함

Planning by DP

MDP의 모든 정보를 알고 있다고 가정함

prediction에서:

  • input: MDP ⟨S,A,P,R,γ⟩\lang S,A,P,R,\gamma\rang와 정책 π\pi
  • output: value function vπv_\pi

control에서:

  • input: MDP ⟨S,A,P,R,γ⟩\lang S,A,P,R,\gamma\rang
  • output: optimal value function v∗v_*와 optimal policy π∗\pi_*

Iterative Policy Evaluation

주어진 policy π\pi를 평가하는 법:

  • bellman expectation의 반복적인 계산으로 할 수 있다!

각 k+1k+1 번째 반복마다,
모든 상태 s∈Ss \in S에 대해
vk+1(s)v_{k+1}(s)를 vk(s′)v_k(s')로부터 업데이트함.

vk+1(s)≐Eπ[Rt+1+γvk(St+1)∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γvk(s′)]\begin{aligned} v_{k+1}(s) &\doteq \mathbb{E}_{\pi}[R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s]\\ &= \sum_{a} \pi(a|s) \sum_{s',r} p(s', r \mid s, a) [r + \gamma v_k(s')] \end{aligned}

kk가 ∞\infin으로 커짐에 까라 vkv_k는 vπv_\pi로 수렴할 수 있다.

Algorithm: Iterative Policy Evaluation

  1. 입력 π\pi에 대해
  2. estimation 정확도를 결정하는 작은 역치값 θ>0\theta>0와 함께
  3. V(s)V(s)를 모든 s∈S+s \in \mathcal{S}^+에 대해 초기화하고,
  4. 다음을 Δ<θ\Delta < \theta까지 반복한다.
    1. Δ←0\Delta \larr 0
    2. 모든 s∈Ss\in \mathcal{S}에 대해 반복:
      1. v←V(s)v\larr V(s)
      2. V(s)←∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γV(s′)]V(s) \larr \sum_a \pi(a|s) \sum_{s',r}p(s',r|s,a)[r + \gamma V(s')]
      3. Δ←max⁡(Δ,∣v−V(s)∣)\Delta \larr \max(\Delta, |v - V(s)|)

Policy Iteration

  • Policy π\pi가 주어졌을 때,
    • π\pi를 평가하고
      vπ(s)=E[Rt+1+γRt+2+…∣St=s]v_\pi(s) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \dots | S_t = s]
    • vπv_\pi에 따라 그리디하게 행동하도록 정책을 업데이트한다.
      π′=greedy⁡(vπ)\pi' = \operatorname{greedy}(v_\pi)
  • policy iteration은 항상 최적의 정책 π∗\pi^*로 수렴함.


Policy Improvement

  • 결정론적인 정책 a=π(s)a = \pi(s)가 주어졌을 떄,
  • 우리는 그리디하게 행동함으로써 정책을 업데이트할 수 있다.
    π′(s)=greedy(vπ)=argmaxa∈Aqπ(s,a)\pi'(s) = \text{greedy}(v_\pi) = \underset{a \in A}{\text{argmax}} q_\pi(s, a)
  • 이는 매 스텝마다 모든 상태 S에 대한 value들을 개선한다.
    qπ(s,π′(s))=max⁡a∈Aqπ(s,a)≥qπ(s,π(s))=vπ(s)q_\pi(s, \pi'(s)) = \max_{a \in A} q_\pi(s, a) \geq q_\pi(s, \pi(s)) = v_\pi(s)
  • 그러면 이 부등식이 만족할까?
    vπ′(s)≥vπ(s)v_{\pi'}(s) \geq v_{\pi}(s)

Proof

qπ(s,a)≐E[Rt+1+γvπ(St+1)∣St=s,At=a]=∑s′,rp(s′,r∣s,a)[r+γvπ(s′)].(4.6)\begin{aligned} q_\pi(s, a) &\doteq \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s, A_t=a] \\ &= \sum_{s',r} p(s',r \mid s, a)[r + \gamma v_\pi(s')]. \end{aligned} \tag{4.6}
qπ(s,π′(s))≥vπ(s).(4.7)q_\pi(s, \pi'(s)) \geq v_\pi(s). \tag{4.7}
vπ(s)≤qπ(s,π′(s))=E[Rt+1+γvπ(St+1)∣St=s,At=π′(s)]=Eπ′[Rt+1+γvπ(St+1)∣St=s]≤Eπ′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=Eπ′[Rt+1+γEπ′[Rt+2+γvπ(St+2)∣St+1,At+1=π′(St+1)]∣St=s]=Eπ′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]≤Eπ′[Rt+1+γRt+2+γ2Rt+3+γ3vπ(St+3)∣St=s]⋮≤Eπ′[Rt+1+γRt+2+γ2Rt+3+γ3Rt+4+⋯∣St=s]=vπ′(s).\begin{aligned} v_{\pi}(s) &\leq q_{\pi}(s, \pi'(s)) \\ &= \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s, A_t = \pi'(s)] \\ &= \mathbb{E}_{\pi'}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s] \\ &\leq \mathbb{E}_{\pi'}[R_{t+1} + \gamma q_{\pi}(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s] \\ &= \mathbb{E}_{\pi'}[R_{t+1} + \gamma \mathbb{E}_{\pi'}[R_{t+2} + \gamma v_{\pi}(S_{t+2}) \mid S_{t+1}, A_{t+1} = \pi'(S_{t+1})] \mid S_t = s] \\ &= \mathbb{E}_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_{\pi}(S_{t+2}) \mid S_t = s] \\ &\leq \mathbb{E}_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 v_{\pi}(S_{t+3}) \mid S_t = s]\\ &\vdots\\ &\leq \mathbb{E}_{\pi'} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \dots \mid S_t = s \right] \\ &= v_{\pi'}(s). \end{aligned}

만약 개선이 멈춘다면,

qπ(s,π′(s))=max⁡a∈Aqπ(s,a)=qπ(s,π(s))=vπ(s)q_{\pi}(s, \pi'(s)) = \max_{a \in A} q_{\pi}(s, a) = q_{\pi}(s, \pi(s)) = v_{\pi}(s)

를 만족하고, Bellman optimality equation또한 만족한다.

vπ(s)=max⁡a∈Aqπ(s,a)v_{\pi}(s) = \max_{a \in A} q_{\pi}(s, a)

따라서 모든 s∈Ss \in \mathcal{S}에 대해 vπ(s)=v∗(s)v_\pi(s) = v_*(s)가 만족한다.

따라서 π\pi가 optimal poilicy이다.

Algorithm: Policy Iteration

Modified Policy Iteration

  • policy evaluation이 매번 vπv_\pi로 수렴해야 할까?
  • 아니면 우리가 정지조건을 만들 수 있을까?
  • kk번 반복 후 policy evaluation을 해도 되지 않을까?
  • 아니면 그냥 매 반복마다 policy를 업데이트 해도 되지 않을까? == value iteration

Value Iteration

Optimal policy를 찾기 위해

  • 각 k+1k+1번째 반복마다
  • 모든 상태 s∈Ss \in \mathcal{S}에 대해
  • vk(s′)v_k(s')로부터 vk+1(s)v_{k+1}(s)를 업데이트한다.
vk+1(s)≐max⁡aE[Rt+1+γvk(St+1∣St=s,At=a]=max⁡a∑s′,rp(s′,r∣s,a)[r+γvk(s′)]\begin{aligned} v_{k+1}(s) &\doteq \max_a \mathbb{E}[R_{t+1} + \gamma v_k (S_{t+1} | S_t = s, A_t = a] \\ &= \max_a \sum_{s', r}p(s',r|s,a)[r+\gamma v_k(s')] \end{aligned}

vk+1(s)=max⁡a∈A(Rsa+γ∑s′∈SPss′avk(s′))vk+1=max⁡a∈ARa+γPavk\begin{aligned} v_{k+1}(s) &= \max_{a \in \mathcal{A}} \left( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_k(s') \right) \\ \mathbf{v}_{k+1} &= \max_{a \in \mathcal{A}} \mathcal{R}^a + \gamma \mathcal{P}^a \mathbf{v}_k \end{aligned}

요약

알고리즘들은 state-value function을 기반으로 하고 있으며, mm개의 action과 nn개의 상태에 대해 iteration당 O(mn2)O(mn^2)가 필요하다.

action-state-value function에 대해서는 반복당 O(m2n2)O(m^2n^2)가 필요하다.

profile
Bard
돈 되는 건 다 공부합니다.
이전 포스트

[RL] Markov Decision Process

다음 포스트

[RL] Model-free Prediction

0개의 댓글