*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<마코프 의사결정 과정(MDP)에서의 벨만 방정식 정리>
기본 정의
- 벨만 방정식: 현재 상태의 가치와 미래 상태의 가치 사이의 재귀적 관계를 표현하는 방정식
- MDP 문제를 해결하기 위한 핵심 방정식으로, 동적 프로그래밍의 기반
종류
- 상태 가치 함수(State Value Function)에 대한 벨만 방정식
- 정의: V(s) = ∑_a π(a|s) ∑_s' P(s'|s,a)[R(s,a,s') + γV(s')]
- 의미: 정책 π를 따를 때 상태 s의 가치는 가능한 모든 행동과 다음 상태에 대한 즉각적 보상과 할인된 미래 가치의 기대값
- 행동 가치 함수(Action Value Function)에 대한 벨만 방정식
- 정의: Q(s,a) = ∑_s' P(s'|s,a)[R(s,a,s') + γ ∑_a' π(a'|s')Q(s',a')]
- 의미: 상태 s에서 행동 a를 취하고 이후 정책 π를 따를 때의 가치
- 최적 상태 가치 함수에 대한 벨만 최적 방정식
- 정의: V*(s) = max_a ∑_s' P(s'|s,a)[R(s,a,s') + γV*(s')]
- 의미: 최적 정책을 따를 때 얻을 수 있는 상태 s의 최대 가치
- 최적 행동 가치 함수에 대한 벨만 최적 방정식
- 정의: Q*(s,a) = ∑_s' P(s'|s,a)[R(s,a,s') + γ max_a' Q*(s',a')]
- 의미: 상태 s에서 행동 a를 취하고 이후 최적 정책을 따를 때의 최대 가치
특성
- 재귀적 구조: 현재 가치가 미래 가치에 의존하는 재귀적 관계
- 기대값 기반: 환경의 확률적 특성을 반영한 기대값 계산
- 최적성 원리: 최적 정책의 일부는 그 자체로 최적 정책임을 보장
응용
- 가치 반복(Value Iteration): 벨만 최적 방정식을 반복적으로 적용하여 최적 가치 함수 계산
- 정책 반복(Policy Iteration): 정책 평가와 정책 개선을 번갈아 수행하여 최적 정책 도출
- 강화학습 알고리즘: Q-학습, SARSA 등 다양한 강화학습 알고리즘의 이론적 기반
|후기 및 확장|
벨만 방정식의 핵심은 "현재 상태의 가치는 즉각적인 보상과 다음 상태의 할인된 가치의 합의 기대값"이라는 점이다. 이 재귀적 관계를 통해 최적 의사결정을 위한 가치 함수를 계산할 수 있다. 다음은 벨만 방정식이다.
- V(s)는 상태 s의 가치.
- E는 기대값을 의미.
- R_t는 시간 t에서의 보상입.
- γ(감마)는 0과 1 사이의 할인 인자로, 미래 보상의 현재 가치를 조정.
- S_t는 시간 t에서의 상태.
-> 벨만 방정식을 통해 이 가치함수는 재귀적 형태로 표현
이제 코드로 알아보자.
<초기화>
- 상태 공간(State Space): 에이전트가 처할 수 있는 모든 상황의 집합
- 코드에서: self.states = [(x, y) for x in range(width) for y in range(height)]
- 행동 공간(Action Space): 에이전트가 취할 수 있는 모든 행동의 집합
- 코드에서: self.actions = [(-1, 0), (1, 0), (0, -1), (0, 1)] (위, 아래, 왼쪽, 오른쪽)
- 전이 확률(Transition Probabilities): 상태와 행동이 주어졌을 때 다음 상태로 전이할 확률
- 코드에서: get_transition_prob 메서드로 정의
- 보상 함수(Reward Function): 특정 상태 전이에 따른 즉각적인 보상
- 코드에서: self.rewards와 get_reward 메서드로 정의
- 할인 인자(Discount Factor): 미래 보상의 현재 가치 반영 비율
- 코드에서: self.gamma
- 초기 가치 함수(Initial Value Function): 알고리즘 시작점으로서의 각 상태 가치 초기값
- 코드에서: self.values = {state: 0 for state in self.states}
- 종료 상태(Terminal States): 에피소드가 끝나는 상태들
- 코드에서: self.terminal_states = [(width-1, height-1), (0, height-1)]
핵심 흐름
- 환경 설정: GridWorld 클래스 초기화에서 그리드 세계를 정의.
- 상태 공간, 행동 공간, 보상 함수, 종료 상태 등 MDP의 요소들이 설정.
- 가치 반복 알고리즘: value_iteration 메서드에서는 다음과 같은 과정이 반복.
- 모든 상태에 대해 벨만 업데이트(Bellman update)를 수행
- 가치 함수의 변화량을 측정하여 수렴 여부 확인
- 수렴하거나 최대 반복 횟수에 도달할 때까지 반복
- 벨만 업데이트: bellman_update 메서드에서 각 상태의 가치를 계산.
- 모든 가능한 행동에 대해 기대 가치를 계산
- 각 행동에 대한 전이 확률, 보상, 미래 가치를 고려
- 가장 높은 기대 가치를 반환 (최적 행동 선택)
----
|인증|
-------
패스트캠퍼스 링크