Stanford CS229: Machine Learning | Lecture 17 강의 정리

Stanford에서 2018년 가을학기에 열린 Andrew Ng 교수의 CS229 머신러닝 강의의 대부분의 내용을 번역 정리한 글입니다.

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018
Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.
강의 제목 : Lecture 17 - MDPs & Value/Policy Iteration | Stanford CS229: Machine Learning Andrew Ng (Autumn2018)
강의 영상: https://youtu.be/d5gaWTo6kDM?si=x8kd7qvgDO6Uji6x
강의 자료 (복원): https://github.com/maxim5/cs229-2018-autumn
강의 syllabus : http://cs229.stanford.edu/syllabus-autumn2018.html
강의를 듣기 전에 알고 있어야 하는 내용
선형대수학 : https://cs229.stanford.edu/notes2022fall/cs229-linear_algebra_review.pdf
확률이론 : https://cs229.stanford.edu/notes2022fall/cs229-probability_review.pdf

---

Outline

• MDPs (recap)
• Value function
• Value iteration / Policy iteration
• Learning $P_{sa}$

P

$$
\left(S,A,{P_{sa}},\gamma,R\right)
$$

$S$: set of state
$A$: set of Action
${P_{sa}}$: state transition probabilities ($\sum\limits_{s'}P_{sa}(s')=1$)
$\gamma$: discount factor ($r\in[0,1]$)
$R$: reward function

$s_{0}$, $a_{0}=\pi(s_{0})$, $s_{1}\sim P_{s_{0}a_{0}}$ $a_{1}$, $s_{2}\sim P_{s_{1}a_{1}}$

Policy $\pi: S \mapsto A$ (maximize expected value $R(s_{0})+\gamma R(s_{1})+\gamma^{2} R(s_{2})+ \cdots$)

Value Function

Define : $V^{\pi},\ V^{},\ \pi^{}$
For a policy $\pi$, $V^{\pi}: S \mapsto R$ is s.t. $V^{\pi}(s)$ is the expected total payoff for starting in state s and expecting $\pi$

$$
V^{\pi}(s)=E(R(s_{0})+\gamma R(s_{1})+\gamma^{2}R(s_{2})+\cdots|\pi,s_{0} = s)
$$

"Value function for policy $\pi$ "

Bellman's Equation

$$
V^{\pi}(s)=R(s)+\gamma \sum\limits_{s^{\prime}}P_{s\pi(s)}(s^{\prime})V^{\pi}(s^{\prime})
$$

위 식은 아래와 같이 유도할 수 있다.

$$
V^{\pi}(s)=E[R(s_{0})+\gamma R(s_{1})+\gamma^{2}R(s_{2})+\cdots|\pi,s_{0}=s] \
$$

$$
\gamma (R(s_{1})+\gamma R(s_{2})+\cdots) = \gamma V^{\pi}(s_{1})
$$

$V^{\pi}(s_{1})$는 expected future value로 해석할 수 있다.

$$
V^{\pi}(s)=E[r(s)+\gamma V^{\pi}(s^{\prime})]
$$

$$
V^{\pi}(s)=R(s)+\gamma \sum\limits_{s^{\prime}}P_{s\pi(s)}(s^{\prime})V^{\pi}(s^{\prime})
$$

주어진 $\pi$에 대해 $V^{\pi}(s)$항에 대해 linear system of equation을 얻을 수 있다.
state가 11개 이므로 11개의 eqaution과 11개의 unknowns인 linear system을 선형 대수를 이용해 풀면 된다.

$$
\begin{bmatrix}
V^{\pi}((1,1))\V^{\pi}((1,2))\ \vdots\V^{\pi}((4,3))
\end{bmatrix} \in \mathbb{R}^{11}
$$

$V^{}$는 *optimal value function**이다.

$$
V^{*}(s) = \max_{\pi}V^{\pi}(s)
$$

$$
V^{}(s) = R(s)+\max_{a}\left(\gamma \sum\limits_{s^{\prime}}P_{sa}(s^{\prime})V^{}(s^{\prime}) \right)
$$

optimal policy

$$
\pi^{}(s)=\arg \max_{a} \sum\limits_{s^{\prime}}P_{sa}(s^{\prime})V^{}(s^{\prime})
$$

$V^{}(s)=V^{\pi^{}}(s)\geq V^{\pi}(s)$ for every $\pi$, s

strategy

1. Find $V^{*}$
2. use argmax equation for find $\pi^{*}$

Value Iteration

Initialize $V(s):=0$ for every $s$
For every $s$, update:
    $V(s):=R(s)+\max_{a}\gamma \sum\limits_{s^{\prime}}P_{sa}(s^{\prime})V(s^{\prime})$
    ($V(s)$ : new estimates value, $V(s^{\prime})$: old estimates value)
$V:=B(V)$

• Synchronous update : 모두 동시에 업데이트
• Value itertaion cause V to converge to $V^{*}$

Policy Iteration

pollicy iteration은 $\pi$를 랜덤하게 정하고 그것을 바탕으로 $V$를 업데이트 한다.

Initialize $\pi$ randomly

• Set $V:=V^{\pi}$ (i.e. solve Bellman's equations to get $V^{\pi}$)
• Set $\pi(s)=\arg\max_{a}\sum\limits_{s^{\prime}}P_{sa}(s^{\prime})V(s^{\prime})$

value iteration은 정확한 값을 구하지 못하는 반면 policy iteration은 $\pi$의 optimal value를 구할 수 있다.

Learning $P_{sa}$

만약 $P_{sa}$를 모른다면?

$$
P_{sa}(s^{\prime})=\frac{#\text{times took acction "a" in state} s \text{and got to }s^{\prime}}{# \text{times took action "a" in state}s}
$$

만약 위 식의 값이 $\frac{0}{0}$이라면 $\frac{1}{|S|}$를 사용한다.
naive bayes처럼 0에 sensetive하지 않기 때문에 laplace smoothing을 해주지 않아도 된다

putting it together:

• Repeat
  • Take actions with respect to $\pi$ to get experience in MDP
    • $0.1\approx \epsilon\text{-greedy}$ : random하게 action할 확률을 정해줌 (exploration p)
    • $0.9$ : respect to $\pi$
    • $0.1$ : randomly
  • Update estimates of $P_{sa}$ (and possible R)
  • Solve Bellman's equation using value equation to get $V$
  • Update $\pi(s):=\arg\max_{a}\sum\limits_{s^{\prime}}P_{sa}(s^{\prime})V(s^{\prime})$

Exploration Vs Exploitation

Exploration vs Exploitation 즉 얼마나 greedy하게 움질일 것인가에 대한 선택을 해야한다. 얻어낸 policy 대로만 움직인다면 멀리 있는 +100의 reward를 발견할 수 없어 optimal 하지 못한 결과를 얻게 된다.