MDP 개념 다시 훑어보자.
MDP는 순차적 의사결정 문제를 수학적으로 모델링하는 프레임워크입니다. 강화학습의 기본이 되는 개념으로, 에이전트가 환경과 상호작용하며 최적의 결정을 내리는 방법을 공부할 때 사용됩니다.
MDP의 핵심 요소
MDP는 다음 요소들로 구성됩니다:
- 상태(State, S): 환경의 현재 상황
- 행동(Action, A): 에이전트가 취할 수 있는 행동
- 상태 전이 확률(Transition Probability, P): 현재 상태와 행동이 주어졌을 때 다음 상태로 전이할 확률
- 보상(Reward, R): 특정 상태에서 특정 행동을 취했을 때 받는 즉각적인 보상
- 할인율(Discount Factor, γ): 미래 보상의 현재 가치를 계산하는 파라미터(0~1 사이)
중요 함수들
1. 정책(Policy, π)
- 각 상태에서 어떤 행동을 선택할지 결정하는 전략
- π(a|s): 상태 s에서 행동 a를 선택할 확률
2. 상태 가치 함수(State Value Function, V^π(s))
- 정책 π를 따를 때, 상태 s에서 시작하여 얻을 수 있는 기대 누적 보상
- 수식: V^π(s) = E_π[∑(γ^t * R_t) | S_0 = s]
- 현재 상태에서 정책을 따랐을 때 앞으로 받을 수 있는 보상의 총합(할인율 적용)
3. 행동 가치 함수(Action Value Function, Q^π(s,a))
- 정책 π를 따를 때, 상태 s에서 행동 a를 취한 후 얻을 수 있는 기대 누적 보상
- 수식: Q^π(s,a) = E_π[∑(γ^t * R_t) | S_0 = s, A_0 = a]
- 현재 상태와 행동이 주어졌을 때 앞으로 받을 수 있는 보상의 총합
벨만 방정식(Bellman Equation)
벨만 방정식은 가치 함수 간의 재귀적 관계를 표현합니다:
상태 가치 함수의 벨만 방정식
V^π(s) = ∑_a π(a|s) * [R(s,a) + γ * ∑_s' P(s'|s,a) * V^π(s')]
행동 가치 함수의 벨만 방정식
Q^π(s,a) = R(s,a) + γ * ∑_s' P(s'|s,a) * ∑_a' π(a'|s') * Q^π(s',a')
최적 정책과 최적 가치 함수
목표는 기대 보상을 최대화하는 최적 정책 π*를 찾는 것입니다:
- 최적 상태 가치 함수: V*(s) = max_π V^π(s)
- 최적 행동 가치 함수: Q*(s,a) = max_π Q^π(s,a)
- 최적 정책: π*(a|s) = 1 if a = argmax_a Q*(s,a), 0 otherwise
동적 프로그래밍의 핵심 원리
- 문제 분해 - 전체 큰 문제(전체 기대 보상 계산)를 작은 문제(각 상태에서의 가치 계산)로 분해합니다.
- 재귀적 관계 활용 - 현재 상태의 가치는 다음 상태의 가치를 이용해 계산합니다. 이것이 벨만 방정식의 핵심입니다:
동적 프로그래밍 알고리즘의 작동 방식
동적 프로그래밍을 MDP에 적용할 때:
- 정책 평가(Policy Evaluation):
- 모든 상태의 초기 가치를 0으로 설정
- 반복적으로 각 상태의 가치를 업데이트: V_new(s) ← R(s) + γ * ∑ P(s'|s) * V_old(s')
- 수렴할 때까지 반복
- 정책 개선(Policy Improvement):
- 현재 가치 함수를 기반으로 더 좋은 행동을 선택
- π_new(s) ← argmax_a [R(s,a) + γ * ∑ P(s'|s,a) * V(s')]
이렇게 작은 문제(각 상태의 가치)를 먼저 해결하고, 이를 조합하여 전체 문제(최적 정책)를 해결하는 것이 동적 프로그래밍의 접근 방식입니다. 이런 방식으로 문제를 해결하면 계산 효율성이 크게 향상됩니다.
슬라이드에서 설명하는 핵심 개념은 다음과 같습니다:
- 최적 상태 가치 함수(Optimal State-Value Function, V):
- 모든 가능한 정책(π) 중에서 각 상태(s)에 대한 가치를 최대화하는 정책을 찾은 것입니다.
- V*(s) = max_π V_π(s)
- 즉, 어떤 상태에서 시작했을 때 가장 많은 누적 보상을 얻을 수 있는 정책을 따르는 것입니다.
- 최적 행동 가치 함수(Optimal Action-Value Function, Q):
- 모든 가능한 정책(π) 중에서 각 상태(s)와 행동(a) 쌍에 대한 가치를 최대화하는 정책을 찾은 것입니다.
- Q*(s,a) = max_π Q_π(s,a)
- 특정 상태에서 특정 행동을 취했을 때, 그 이후로 가장 많은 누적 보상을 얻을 수 있는 정책을 따르는 것입니다.
이 두 개념의 중요한 점은:
- 최적 정책은 최적 가치 함수와 연결되어 있습니다:
- 최적 정책(π*)을 따르면 최적 가치 함수(V* 또는 Q*)를 얻게 됩니다.
- 반대로, 최적 가치 함수가 있으면 최적 정책을 쉽게 도출할 수 있습니다.
- 최적 행동 선택:
- 최적 행동 가치 함수(Q*)를 알고 있다면, 각 상태에서 Q*(s,a)를 최대화하는 행동을 선택하면 됩니다.
- 이것이 최적 정책(π*)입니다: π*(s) = argmax_a Q*(s,a)
결론적으로, MDP 문제를 해결한다는 것은 이 최적 가치 함수(V* 또는 Q*)를 찾는 것이며, 이를 통해 에이전트는 각 상태에서 어떤 행동을 취해야 최대 보상을 얻을 수 있는지 알 수 있게 됩니다.
과정 설명
- 초기 상태(k=0):
- 모든 상태의 가치를 0으로 초기화
- 랜덤 정책: 모든 상태에서 네 방향(a1~a4)으로 균등하게 25%씩 움직임
- 회색 칸은 터미널 상태(목표)
- 반복 과정:
- 각 반복(k)마다 벨만 기대 방정식을 사용해 가치 함수 업데이트
- 슬라이드 우측 공식은 가치 업데이트 방식을 보여줌: V(s) = 0.25(-1 + γV(s1)) + 0.25(-1 + γV(s2)) + ...
- 그리디 정책:
- 각 반복 후 현재 가치 함수를 기반으로 그리디 정책 생성
- 화살표: 각 상태에서 가장 높은 가치의 이웃 상태로 이동하는 방향
- 수렴(k=∞):
- 충분히 많은 반복 후, 가치 함수가 수렴
- 최종 그리디 정책이 최적 정책이 됨
수렴 보장과 필요한 반복 횟수
- 수렴 보장:
- 정책 반복은 유한한 MDP(유한한 상태와 행동 공간)에서는 항상 수렴이 보장됩니다.
- 이론적으로 정책의 개수가 유한하고(|A|^|S|), 각 정책 평가 단계에서 가치 함수가 항상 개선되거나 유지되기 때문입니다.
- 필요한 반복 횟수:
- 필요한 반복 횟수는 문제 크기와 복잡도에 따라 달라집니다.
- 작은 그리드월드(예: 4x4)는 10-20회 정도 반복으로 충분할 수 있습니다.
- 큰 상태 공간에서는 더 많은 반복이 필요할 수 있습니다.
- 수렴 조건:
- 실제로는 완전한 수렴까지 기다리지 않고, 가치 함수나 정책의 변화가 매우 작아질 때(예: ε-수렴) 알고리즘을 종료합니다.
- 일반적으로 사용되는 조건: max|V_k+1(s) - V_k(s)| < ε (ε은 작은 양수, 예: 0.001)
- 수렴 속도에 영향을 주는 요소:
- 할인율(γ): γ가 1에 가까울수록 수렴이 느립니다.
- 초기화 방법: 좋은 초기 추정치로 시작하면 더 빨리 수렴할 수 있습니다.
- 상태 공간의 크기: 상태가 많을수록 수렴이 느립니다.
- 환경의 구조: 복잡한 보상 구조나 확률적 전이는 수렴을 느리게 만듭니다.
- 계산적 고려사항:
- 정책 평가 단계에서 완전한 수렴까지 기다리지 않고, 몇 번의 스윕(sweep)만 수행한 후 정책 개선으로 넘어가는 방법도 있습니다.
- 이를 "수정된 정책 반복(Modified Policy Iteration)"이라고 하며, 실용적으로 많이 사용됩니다.
정리하자면, 유한한 MDP에서는 정책 반복의 수렴이 항상 보장되지만, 실제 필요한 반복 횟수는 문제의 특성에 따라 달라집니다. 일반적으로는 가치 함수의 변화가 충분히 작아지는 시점(ε-수렴)을 기준으로 알고리즘을 종료합니다.
영화추천시스템을 적용해본다고 해보자. 실제 구현에서는 더 많은 사용자 특성과 콘텐츠 특성을 고려할 수 있겠다. 보상 신호는 이 예제에서는 시청 완료율로 정의했지만, 실제 시스템에서는 클릭, 평점, 구매 등 다양한 지표를 조합하여 정의할수 있다.
보상 : 영화를 끝까지 다 시청한 경우를 보상으로 정의하자.
- 여기서 보상은 사용자가 추천받은 영화를 얼마나 완료해서 시청했는지의 비율
- 예: 액션 선호 사용자가 액션 영화를 80% 완료하고, 코미디 영화는 30% 완료
# 보상 행렬 정의 (사용자 유형별 장르 선호도에 따른 보상)
# 행: 사용자 유형, 열: 영화 장르, 값: 평균 시청 완료율(%)
rewards = np.array([
[0.3, 0.3, 0.3], # 신규 사용자: 모든 장르에 대해 낮은 시청률
[0.8, 0.3, 0.2], # 액션 선호: 액션 영화 시청률 높음
[0.2, 0.9, 0.3], # 코미디 선호: 코미디 영화 시청률 높음
[0.1, 0.2, 0.8], # 드라마 선호: 드라마 영화 시청률 높음
[0.5, 0.6, 0.7] # 다양한 장르 선호: 모든 장르 시청률 높지만 드라마 약간 높음
])가치함수 : 밸류펑션
self.gamma는 할인계수로 미래 보상의 중요도를 결정(0.9로 설정) 한다. 각 반복에서 상태 가치의 변화를 측정하고 변화가 작을때 delta < theta 수렴으로 판단한다.
def value_iteration(self, theta=0.001, max_iterations=100):
for i in range(max_iterations):
delta = 0
old_values = self.values.copy()
for s in range(self.num_states):
# 각 행동에 대한 가치 계산
action_values = []
for a in range(self.num_actions):
immediate_reward = self.rewards[s, a]
expected_future_value = 0
for next_s in range(self.num_states):
expected_future_value += self.transitions[s, a, next_s] * old_values[next_s]
# Q(s,a) = R(s,a) + γ * Σ P(s'|s,a) * V(s')
action_values.append(immediate_reward + self.gamma * expected_future_value)
# 최대 가치를 선택
self.values[s] = max(action_values)
delta = max(delta, abs(old_values[s] - self.values[s]))행동가치함수 : 액션밸류펑션
행동가치함수는 명시적으로 Q-값형태로 계산한다.
- 이것은 상태 s에서 행동 a를 취했을 때의 기대 가치(Q-값)를 계산
- 즉시 보상과 기대 미래 가치의 합으로 구성됨
# Q(s,a) = R(s,a) + γ * Σ P(s'|s,a) * V(s')
action_values.append(immediate_reward + self.gamma * expected_future_value)정책
- 각 상태에서 최대 Q-값을 가지는 행동을 정책으로 선택
- 이 정책이 바로 각 사용자 유형에게 어떤 장르를 추천할지를 결정
def _extract_policy(self):
for s in range(self.num_states):
action_values = []
for a in range(self.num_actions):
immediate_reward = self.rewards[s, a]
expected_future_value = 0
for next_s in range(self.num_states):
expected_future_value += self.transitions[s, a, next_s] * self.values[next_s]
action_values.append(immediate_reward + self.gamma * expected_future_value)
# 가장 높은 가치를 주는 행동 선택
self.policy[s] = np.argmax(action_values)
Discounted Return개념
# Q(s,a) = R(s,a) + γ * Σ P(s'|s,a) * V(s')
# 위 수식은 할인된 누적 보상을 계산하는 방식
gamma(할인 계수)는 미래 보상의 현재 가치를 조정
즉각적인 보상(R(s,a))과 할인된 미래 보상(γ * 기대 미래 가치)의 합
0.9의 할인 계수는 미래MDP(Markov Decision Process), 다이내믹 프로그래밍, 그리고 모델 기반 접근법은 강화학습과 순차적 의사결정 문제를 이해하는 데 중요한 기반이 됩니다.
MDP는 상태(state), 행동(action), 전이 확률(transition probability), 보상(reward), 그리고 할인 계수(discount factor)로 구성된 수학적 프레임워크로, 불확실성 하에서의 순차적 의사결정 문제를 모델링하는 방법입니다. 영화 추천 시스템 예제에서 보았듯이, MDP는 사용자의 상태 변화와 장기적인 만족도를 함께 고려할 수 있습니다.
다이내믹 프로그래밍은 MDP를 해결하는 핵심 방법론으로, 가치 반복법(value iteration)과 정책 반복법(policy iteration)을 통해 최적 정책을 찾습니다. 이는 벨만 방정식을 반복적으로 풀어나가는 과정으로, 복잡한 문제를 하위 문제로 나누어 해결하는 접근법입니다.
또한 오늘 살펴본 방식은 모델 기반(Model-Based) 접근법으로, 환경의 동역학(전이 확률과 보상 함수)이 명시적으로 주어진 상태에서 최적 정책을 계산합니다. 실제 환경에서는 이러한 모델을 알지 못하는 경우가 많아, 모델 없는(Model-Free) 방법인 Q-learning이나 SARSA 같은 알고리즘을 활용하기도 합니다.