중간고사 예상 문제

1. (Finite) Markov Decision Process

1. 강화학습(Reinforcement Learning)의 정의를 서술하고, 지도학습(Supervised Learning)과의 차이점을 예시와 함께 설명하시오

A goal-directed learning from interaction

강화학습은 에이전트가 환경과 상호작용하면서 보상을 최대화하는 방향으로 행동 정책을 학습하는 방법이다.
에이전트는 상태(state)를 관찰하고, 행동(action)을 선택하여 환경에 영향을 주며, 그 결과로 보상(reward)을 받고 다음 상태로 전이된다.
이러한 반복 과정을 통해 최적의 행동 정책(policy)을 학습한다.

지도학습은 입력과 정답(label)이 주어진 데이터를 기반으로 모델을 학습시키는 방식이다.
반면 강화학습에서는 명시적인 정답이 없으며, 보상을 통해 간접적으로 학습된다.

예를 들어, 바둑을 둘 때 지도학습은 프로기사의 기보를 따라 두는 법을 배우는 것이라면,
강화학습은 직접 바둑을 두고 승패를 통해 잘 두는 법을 학습하는 것이다.

2. 강화학습에서의 Agent-Environment Interface를 설명하시오

에이전트는 현재 상태 $S_t$를 관찰하고
정책 $\pi$에 따라 행동 $A_t$를 선택하여 환경에 전달한다.
환경은 그에 대한 결과로 다음 상태 $S_{t+1}$과 보상 $R_{t+1}$을 반환한다.

이 과정을 반복하면서 에이전트는 장기적으로 얻을 보상의 총합을 최대화하도록 정책을 개선한다.

3. MDP의 이론적 정의를 수식과 함께 서술하시오

마르코프 성질(Markov Property)
- 다음 상태는 과거의 모든 이력이 아닌, 현재 상태와 행동에만 의존.
확률적 전이(Probabilistic Transitions)
- 행동을 취했을 때 다음 상태가 확률적으로 결정됨
시간 불변성(Stationarity)
- 전이 확률과 보상 함수는 시간에 따라 변하지 않음.
- $P(s'|s, a)$와 $R(s, a)$는 항상 일정하다.

$$P(s_{t+1} | s_t, a_t, p_{t-1}, a_{t - 1}, ... , s_0, a_0) = P(s_{t+1}|s_t, a_t)$$

다음 상태 $s_{t+1}$의 확률 분포는 오직 현재 상태 $s_t$와 행동 $a_t$에만 의존하고,
그 이전의 상태나 행동들과는 무관하다.

$\mathcal{S}$: 상태 집합 (States)
$\mathcal{A}$: 행동 집합 (Actions)
$P(s'|s, a)$: 상태 전이 확률 (Transition Probability)
$R(s, a)$: 보상 함수 (Reward Function)
$\gamma \in [0, 1]$: 감쇠 계수 (Discount Factor)

4. Reward vs Return

Reward

한 시점에서 에이전트가 받은 즉각적인 보상
$R_{t+1}$
행동의 결과로 환경이 주는 피드백

Return

미래 보상의 누적합
$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...$
에이전트가 한 상태에서 앞으로 받을 전체 보상의 합. (미래 기대값)

5. Episodic Task vs Continuing Task

Episodic Task

시작과 끝이 명확한 에피소드 단위로 학습이 이뤄지는 테스크이다.

$$ v_{\pi} = \mathbb{E}{\pi} [\sum{k=0}^{T-t-1} \gamma^k R_{t+k+1} | S_t = s] $$

Continuing Task

에피소드 없이 무한히 반복되는 환경이다. 이 경우에는 $\gamma < 1$을 사용하여 무한 보상 합이 수렴하게 만든다.

$$ v_{\pi} = \mathbb{E}{\pi} [\sum{k=0}^{\infin} \gamma^k R_{t+k+1} | S_t = s] $$

Unified notation for Episodic and Continuing Tasks

$$ G_t = \sum_{k = 0}^{T-t-1} \gamma^k R_{t+k+1} $$

6. 강화학습에서 정책(policy)과 가치 함수(value function)의 역할을 각각 서술하시오

정책($\pi$): 주어진 상태 s에서 어떤 행동 a를 선택할 확률
가치함수: 정책을 따랐을 때 각 상태가 상태-행동 쌍이 얼마나 좋은지를 측정하는 함수
- 상태 가치 함수: $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t=s]$
- 행동 가치 함수: $Q^{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t=s, A_t=a]$

정책은 가치 함수에 따라 개선될 수 있고, 가치 함수는 주어진 정책을 기준으로 계산된다.
예를 들어, 로봇이 청소를 하는 환경에서 정책은 각 위치에서 움직일 방향을 결정하고, 가치함수는 그 결정이 장기적으로 얼마나 유익한지를 평가한다.

7. Bellman Equation | State Value Function 유도과정

$$ v_{\pi}(s) \triangleq \mathbb{E}{\pi}[G_t|S_t=s] $$ $$ = \mathbb{E}{\pi}[R_{t+1} + \gamma G_{t+1}|S_t=s] $$ $$ = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)[r + \gamma \mathbb{E}{\pi} [G{t+1}|S_{t+1} = s']] $$ $$ = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)[r + \gamma v_{\pi}(s')] $$

8. Bellman Equation | Action Value Function 유도과정

$$ Q^{\pi}(s, a) = \mathbb{E}{\pi}[G_t|S_t=s, A_t = a] = \mathbb{E}{\pi}[\sum_{k=0}^{\infin} \gamma^kR_{t + k + 1} | S_t=s, A_t=a] $$ $$ = \mathbb{E}[R_{t+1} + \gamma G_{t+1}| S_t=s, A_t=a]$$ $$ = \mathbb{E}[R_{t+1} + \gamma V^{\pi}(S_{t+1})| S_t=s, A_t=a]$$ $$ = \sum_{s'} P(s'|s, a)[R(s, a, s') + \gamma V^{\pi}(s')]$$

상태 가치함수와 행동 가치함수 $$ V^{\pi}(s) = \sum_{a \in A} \pi(a|s)Q^{\pi}(s, a) $$

Dynamic Programming

$$ \pi^* = \text{argmax}{\pi}V{\pi} \quad \text{ subject to MDP}$$

1. Dynamic Programming의 정의

DP는 환경의 모델(전이 확률과 보상 함수)이 주어졌을 때, 가치 함수와 최적 정책을 계산하는 알고리즘이다.

환경의 완전한 모델을 알고 있어야 한다.
상태와 행동 공간이 충분히 작아야 한다.

2. 선형대수로 가치함수 구하기

$$V^{\pi} = R^{\pi} + \gamma P^{\pi} V^{\pi}$$ $$\to (I - \gamma P^{\pi})V^{\pi} = R^{\pi}$$ $$\to V^{\pi} = (I - \gamma P^{\pi})^{-1}R^{\pi}$$

환경의 상태공간이 작아야 한다.
$\gamma < 1$ 이면 가역 행렬이 된다.

3. Policy Evaluation

Policy Evaluation이란 주어진 정책 ${\pi}$에 따라 각 상태의 가치 함수 $V^{\pi}(s)$를 계산하는 과정.

$$ V^{\pi} = \sum_a \pi(a|s)\sum_{s', r}p(s', r|s, a)[r + \gamma V^{\pi}(s')$$ 벨만 기대 방정식을 반복적으로 계산하여 $V^{\pi}$를 점근적으로 수렴시킬 수 있다. 이때 $\gamma \in [0, 1)$이면 수렴이 보장된다. 정책 평가 결과는 이후 정책 개선 단계에서 사용되어 최적 정책을 찾는데 기여한다.

Two array implementation

In-place implementation

4. Policy Improvement - 가치 또는 행동-가치 함수를 이용해 어떻게 새로운 정책을 만드는지 설명하시오

$$ \pi'(s) = \text{argmax}{a} q{\pi}(s, a)$$ $$ = \text{argmax}{a} \mathbb{E}[R{t+1} + \gamma v_{\pi}(S_{t+1})|S_t=s, A_t=a]$$ $$ = \text{argmax}{a} \sum{s'} p(s'|s,a)[r(s,a,s') + \gamma v_{\pi}(s')] $$

정책 개선이란 주어진 정책 $\pi$에 대해 평가된 가치 함수 $V^{\pi}(s)$ 또는 행동-가치 함수 $Q^{\pi}(s, a)$를 기반으로 더 나은 정책을 만드는 과정이다.

대표적인 개선 방법은 greedy 정책을 사용하는 것이다. 각 상태에서 가장 높은 기대 Return을 주는 행동을 선택한다. 이 과정을 반복하면 Policy Iteration이 되고, 정책이 더 이상 개선되지 않으면 최적 정책에 도달하게 된다.

이 과정은 Policy Improvement Theorem에 의해 보장된다.

5. Policy Improvement Theorem

가정 $$ v_{\pi}(s) \leq q_{\pi}(s, \pi'(s))$$
증명

$$ v_{\pi}(s) \leq q_{\pi}(s, \pi'(s)) = \mathbb{E}{\pi'}[R{t+1} + \gamma v_{\pi}(S_{t+1})|S_t=s] $$ $$ \leq \mathbb{E}{\pi'}[R{t+1} + \gamma q_{\pi}(S_{t+1}, \pi'(S_{t+1}))|S_t=s] $$ $$ = \mathbb{E}{\pi'}[R{t+1} + \gamma \mathbb{E}{\pi'}[R{t+2} + \gamma v_{\pi}(S_{t+2})|S_t=s]|S_t=s] $$ $$ = \mathbb{E}{\pi'}[R{t+1} + \gamma R_{t+2} + \gamma^2 v_{\pi}(S_{t+2}) |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}) |S_t=s] $$ $$ = v_{\pi'}(s)$$

znxkznxk1030/mid-term-001.md