기록: UCL Course on RL 요약 및 정리 (Lecture 2: Markov Decision Processes)

This post covers not only Lecture 2: Markov Decision Processes (davidsilver.uk). but also:


Lecture Goal
  • Learn about state-value and action-value functions
  • Learn about Bellman equations that describe the relationship between those two functions
    • Bellman expectation equation
    • Bellman optimality equation (a.k.a. Bellman equation)
Dr. Richard Bellman | via breves-de-maths.fr

Def. Bellman Equation for MRPs

  • The value function of a state (a.k.a. state-value function) is decomposed into two parts:
    • Immediate reward
    • Discounted value of successor state
  • \(V(s) = R(s) + \sum_{s' \in S}(\gamma V(s')T(s'|s)) = \mathbb{E}[R_{t+1} + \gamma V(S_{t+1}) | S_t = s]\)
  • Note: Conditional expectation
    • \(\mathbb{E}[A|B=b] = \sum_{a \in A}{a Pr(A=a|B=b)}\)

Bellman Equation in Matrix Form & Its Solution

  • \(V(1) = R(1) + \sum_{i=1}^{n}\gamma V(i)T(i|1)\)
  • \(\begin{bmatrix}V(1)\\ \vdots \\ V(n)\end{bmatrix} = \begin{bmatrix}R(1)\\ \vdots \\ R(n)\end{bmatrix} + \gamma \begin{bmatrix} T(1|1) \ \cdots \ T(n|1) \\ \vdots\;\;\;\;\;  \ \ddots\;\;\;\;\; \ \vdots \\ T(1|n) \ \cdots \ T(n|n) \end{bmatrix} \begin{bmatrix}V(1)\\ \vdots \\ V(n)\end{bmatrix}\)
  • \(v = c + \gamma\, Tv\), where c is the constant vector if all rewards and transition probabilities are given.
  • \(\therefore v = (I-\gamma\, T)^{-1}c\)
  • Note: Solving a linear system has a known time complexity of \(O(n^3)\) for \(n\) states. The direct solution is only possible for a small MRP system. There are many iterative methods for large MRPs:
    • Jacobi method, Gauss-Seidel method, SOR method, etc.
    • Dynamic programming
    • Monte Carlo evaluation
    • Temporal-difference learning

Def. Policy Equations for MDPs

  • Assumption:
    • Given an MDP \((S, A, T, R, \gamma)\) and a policy \(\pi\),
    • The policy depends on the current state, not the history. Thus, a policy is stationary (time-independent).
  • MDPs reduce to MRPs:
    • \(T(s'|s) := \sum_{a \in A}(T(s'|s,a)\pi(a|s))\)
    • \(R(s) := \sum_{a \in A}(R(s,a)\pi(a|s))\)

Def. Action-Value Function for MDPs

  • Revisit: state-value function
    • 어떤 state에 도착하므로써 (미래도 고려하여) 얼마나 많은 return을 얻을 수 있을지
    • The state-value function of an MDP is the expected return starting from the current state \(s\), and then following policy \(pi\):
      • \(v_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t=s]\)
  • Action-value function \(q_{\pi}(s,a)\)
    • 어떤 액션을 취했을 때 얼마나 많은 return을 얻을 수 있을지
    • The action-value function is the expected return starting from the current state \(s\), taking action \(a\), and then following policy \(pi\):
      • \(q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t|S_t=s, A_t=a]\)
    • Note: \(s\) and \(a\) are constants whereas \(S_t\) and \(A_t\) are random variables.

Bellman Expectation Equation for State-Value
  • \(v_{\pi}(s) = \mathbb{E}_{a \sim \pi(s)}[R_{t+1} + \gamma\, v_{\pi}(S_{t+1}) | S_t = s]\)
    \(v_{\pi}(s) = \sum_{a \in A}\pi(a|s)\left (  R(s,a) + \gamma \sum_{s' \in S} T(s'|s,a) v_{\pi}(s') \right )\)
  • 어떤 상태가 얼마나 많은 가치를 지녔는지 재귀적으로 표현
  • Return의 재귀적인 정의에서 바로 유도됨

Bellman Expectation Equation for Action-Value
  • \(q_{\pi}(s,a) = \mathbb{E}_{a \sim \pi(s)}[R_{t+1} + \gamma\, q_{\pi}(S_{t+1},A_{t+1}) |S_t=s, A_t=a] \)
    \(q_{\pi}(s,a) = R(s,a) + \gamma \sum_{s' \in S}T(s'|s,a) \sum_{a' \in A}{\pi(a'|s')q_{\pi}(s',a')}\)

State-Action Relationship
  • Action-to-state
    • 어떤 상태의 가치는 그 상태에서 취할 수 있는 액션들의 가치의 총합
    • \(v_{\pi}(s) = \sum_{a \in A}{\pi(a|s)q_{\pi}(s,a)}\)
  • State-to-action
    • 어떤 액션의 가치는 그 액션으로 인한 리워드와 액션으로 갈 수 있는 상태들의 가치의 총합 (액션으로 어떤 상태에 도달할 지는 환경의 transition probabilities가 정함)
    • \(q_{\pi}(s,a) = R(s,a) + \gamma \sum_{s' \in S}T(s'|s,a) v_{\pi}(s')\)

Bellman Equations in Matrix Form (2)
  • The above Bellman equations for a fixed policy \(\pi\) are nothing but linear systems if all rewards, transition probabilities, and the policy are given.
  • Note: If the policy changes, solutions (state- and action-value) change. How to define a good policy? What would be the best (optimal) policy?

Def. Optimal Value Function
  • The optimal state-value function is the maximum value function over all policies: \(v_{*}(s) = \underset{\pi}{\max}v_{\pi}(s) \forall s\).
  • The optimal action-value function is the maximum action-value function over all policies \(q_{*}(s,a) = \underset{\pi}{\max}q_{\pi}(s,a) \forall s,a\).
    • 따라서 직관적으로, \(q_{*}\)가 주어졌다면, 당연히 \(q_{*}(s,a)\)가 큰 action을 취하는 게 optimal policy다. 

Thm. Optimal Policy
  • Define a partial ordering over policies: \(\pi \ge \pi'\) if \(v_{\pi}(s) \ge v_{\pi'}(s) \forall v\).
  • For any Markov Decision Process,
    • Existence of an optimal policy: \( \exists \pi_{*} | \forall \pi\; \pi_{*} \ge \pi \)
    • All optimal policies achieve the optimal state-value function, \(v_{\pi_{*}}(s)=v_{*}(s)\).
      • (partial ordering과 optimal value function의 정의에 따르면 당연)
    • All optimal policies achieve the optimal action-value function, \(q_{\pi_{*}}(s,a)=q_{*}(s,a)\).
  • An optimal policy can be found by maximizing over \(q_{*}\),
    • \(\pi_{*}(a|s) = \left\{\begin{matrix}1 \;\;\; \mathrm{if} \; a=\underset{a \in A}{\mathrm{argmax}}\;  q_{*}(s,a) \\ 0 \;\;\; otherwise \hfill \end{matrix}\right.\)
    • Note: 즉, optimal action-value를 갖는 action 중 최고의 action 하나만 선택하는 policy는 optimal policy다. 따라서 optimal action-value function을 구했다면 optimal policy를 결정하여 MDP를 풀 수 있다.
    • There is always a deterministic optimal policy for any MDP.

State-Action Relationship at Optimality
  • Action-to-state
    • \(v_{*}(s) = \underset{a \in A}{\max}q_{*}(s,a)\)
    • Proof)
      • From the state-action relationship, \(v_{\pi}(s) = \sum_{a \in A}{q_{\pi}(s,a)\pi(a|s)}\)
      • From the theorem of the optimal policy, \(v_{*}(s) = v_{\pi_{*}}(s) \\ = \sum_{a \in A}{q_{\pi_{*}}(s,a)\pi_{*}(a|s)} \\ = \sum_{a \in A}{q_{*}(s,a)\pi_{*}(a|s)} \\ = 1 \cdot \underset{a \in A}{\max}q_{*}(s,a) + 0 \cdot (otherwise)\)
      • \(\therefore v_{*}(s) = \underset{a \in A}{\max}q_{*}(s,a)\)
    • Note: 사실 굳이 수학적으로 엄밀하게 증명하지 않더라도, 직관적으로 state의 value는 해당 state에서 고를 수 있는 action들의 value의 평균 (policy를 고려한). Optimal policy는 optimal actions 중에서도 오직 최고의 액션 하나만 고르므로, optimal state-value = maximum optimal action-value.
  • State-to-action
    • \(q_{*}(s,a) = R(s,a) + \gamma \sum_{s' \in S}T(s'|s,a) v_{*}(s')\)
    • Proof)
      • \(q_{\pi}(s,a) = R(s,a) + \gamma \sum_{s' \in S}T(s'|s,a) v_{\pi}(s')\)
      • \(q_{\pi*}(s,a) = R(s,a) + \gamma \sum_{s' \in S}T(s'|s,a) v_{\pi*}(s')\)
      • 직관적으로, 어떤 액션의 가치는 그 액션으로 인한 리워드와 액션으로 갈 수 있는 상태들의 가치의 총합이고, 액션으로 어떤 상태에 도달할 지는 환경이 정하는데, policy는 환경을 바꾸지 못하므로 어쨌든 가능한 모든 다음 state에 관해 expectation을 구해야 한다.

Bellman Optimality Equation for State-Value
  • \(v_{*}(s) = \underset{a \in A}{\max}\left(R(s,a) + \gamma \sum_{s' \in S}{T(s'|s,a)v_{*}(s')} \right)\)
  • Note: Bellman equation for MRPs와 꼴이 비슷하지만 최대화의 개념을 포함함에 유의하라.

Bellman Optimality Equation for Action-Value
  • \(q_{*}(s,a) = R(s,a) + \gamma \sum_{s' \in S}{T(s'|s,a)\underset{a' \in A}{\max}q_{*}(s',a')}\)
  • Note: 위 Bellman equation과 꼴은 흡사하지만 최대화하는 액션이 현재 액션이 아니라 다음 액션 \(a'\)임에 유의하라.

Solving the Bellman Optimality Equation
  • Non-linear (due to the \(\max\) operators)
  • No closed-form solution in general
  • Iterative solution methods
    • Value iteration
    • Policy iteration
    • Q-learning
    • SARSA

Extensions to MDPs
  • Infinite and continuous MDPs
  • Partially observable MDPs
  • Undiscounted, average reward MDPs

댓글

댓글 쓰기

이 블로그의 인기 게시물

시작: 블로그의 방향성

이미지
블로그를 시작하는 이유💬 최근 몇 년 간 기록 의 중요성을 체감했습니다. 2019년 여름, 한 스타트업에서 딥러닝 연구 인턴으로 근무했을 때 매일 업무 내용을 Done/To-do 형식으로 나눠서 연구 일지를 작성해야 하는 소업무가 있었습니다. 그것이 습관이 되어 인턴 이후 대학원 석사 과정에 들어가서도 매일 빠짐없이 일지를 작성했고 학위를 마친 지금도 쭉 이어지고 있습니다.  특히나 제가 속했던 연구실에서는 Done/To-do를 격주에 한 번 발표하는 랩 미팅 시간과, 약 6개월마다 한 번은 연구실 구성원 전체 앞에서 반기 리뷰를 하는 그룹 미팅 시간이 있었기 때문에, 매일 일지를 작성하는 습관은 대학원 생활 내내 큰 도움이 됐습니다. 수업 과제를 할 때도, 보고서를 쓸 때도, 발표 자료를 만들 때도, 과제 제안서를 쓸 때도, 논문을 쓸 때도.... 매일 1분씩 투자해서 개인 슬랙(Slack) 채널에 남겨뒀던 기록들은 항상 큰 힘을 발휘했습니다. 이에 관한 구체적인 경험도 곧 글로 옮길 예정입니다. 본 블로그에서는 제 삶을 개인적으로만 기록했던 것에서 한발짝 더 나아가려 합니다. 석사 학위 과정 중 1년 간 학부생을 대상으로 상담 조교 (counselling assistant) 역할을 맡았었는데, 카톡이나 메일 등 매체의 한계도 있었고 상담 시간도 현실적으로 1시간 정도로 제한적이었기 때문에 도움이 필요한 분들에게 충분히 이야기를 들려드리지 못한 게 아쉬웠습니다. 특히 많은 분들이 '학부 생활을 어떻게 했는지', '어떻게 공부하는지', '대학원 생활은 어땠는지', '교환 학생 때의 경험은 어떤지' 등 몇 마디 말로 다 표현하기 어려운 스토리들을 공통적으로 궁금해해주셨습니다. 그래서 블로그라는 매체를 통해 매일을 기록하면서 저라는 사람의 과거, 현재, 미래를 불특정 다수의 사람들과 나누고자 합니다. 그렇게 쌓인 글들은 제게 희미한 기억에만 의존해서 회상하는 게 아니라 체계적으로 과거를 반추하며 미래를 대...
자세한 내용 보기

CS 285 (Deep Reinforcement Learning) 요약 및 정리 (Lecture 2: Supervised Learning of Behaviors)

이미지
  * UC Berkeley CS 285 강의는 David Silver의  UCL Course on RL  강의로 대부분 커버 가능하다. 본 요약 정리 노트에서는 UCL Course on RL에서 다루지 않는 부분만 정리하는 데에 집중한다. This post covers Lecture 2: Supervised Learning of Behaviors . Terminology DL 맥락의 classification 문제는 \(\mathbf{a}_t\)가 단순히 데이터의 ground truth label이고, \(\mathbf{a}_t\)가 \(\mathbf{o}_{t+1}\)에 영향을 안준다는 차이점이 있다. 이에 반해, RL 문제나 기타 sequential decision making 문제는, 현재의 액션이 다음 관측에 영향을 준다. Imitation Learning Nothing but supervised learning Good example만 training dataset에 넣는다면, policy network의 오차 등으로 완벽히 좋은 state paths를 따라갈 수 없고, good example에 나오지 않는 새로운 케이스에 대응하는 법을 배우지 못해 goal을 달성하지 못하게 된다. DAgger: dataset aggregation Learned policy가 실제로 도달한 state 혹은 observation에서 인간이 손수 바람직한 action을 labeling 한다. 다만, 이 방법은 (3) labeling cost가 너무 크고, 자율주행차를 이렇게 훈련시켰다간 (2) 실제로 차량이 몇 번이고 박살 나야 한다. 사람이 운전하는 것과 매우 다른 observation을 줄 때 사람이 제대로 labeling하기 힘든 점도 있다. Why might we fail to fit the expert? Non-Markovian behavior History 전체를 저장하고 모델 트레이닝에 사용하는 건 cost가 너무 크다. Causa...
자세한 내용 보기

기록: 강화학습 독학을 위한 자료들 (Materials for Studying Reinforcement Learning from Scratch)

Classic RL UCL Course on RL (YouTube, David Silver) UCL Course on RL (slide note, David Silver) UCL Course on RL 2021 (YouTube, Hado van Hasselt, DeepMind) RL Basic (GitHub, Chris Ohk) RL Intermediate (GitHub, Chris Ohk) Reinforcement Learning: An Introduction (PDF, Sutton and Barto) Algorithms for Reinforcement Learning (PDF, Szepesvari) UCL Course on RL 강의의 GridWorld 관련 웹 시각화 예제 (Andrej Karpathy) Advanced Topics on RL Deep Reinforcement Learning (YouTube, Sergey Lavine, UC Berkeley) Deep Reinforcement Learning (slide note, Sergey Lavine, UC Berkeley) RL Paper Study (GitHub, Chris Ohk and Hyecheol Jang) CS885 Lecture 10: Bayesian RL (YouTube, Pascal Poupart) Bayesian Reinforcement Learning: A Survey (ArXiv, Mohammad Ghavamzadeh) Research Paper Archives Key Papers in Deep RL (Spinning Up) Deep Reinforcement Learning Papers (GitHub) Deep RL Papers (RLLAB, Seoul National University) Classic ML Mathematics for Machine Learning  (PDF, Deisenroth, Faisal, and Ong, KAIST AI501 textbook) ...
자세한 내용 보기