Markov Decision Process Model 의 목표는 expected total reward를 최대화 하는것이다.
- 이러한 문제는 바로 해결되야하지만, reward는 미래의 일이기 때문에 어떤 action이 state에서 취해질지 policy를 통해서결정된다. 동일한 MDP 문제에서 어떻게 possible policies를 quantitatively 비교할수 있는가?
- 시작되는 state가 다르면 다른 total rewards가 나올수 있다.
- 이러한 환경들을 고려한 total cumulative reward 를 value function 이라고 부른다.
$V_0^\pi = E[R_0(s0, a0) + \gamma R_1 (s_1, a_1) + ... | s_0] = E[\sum_n \gamma^n R_n(s_n, a_n) | s_0 = s, \pi]$
- 첫번째 부분을 따로 정리하면
$V_0^\pi = R_0(s_0, a_0 = \pi(s_0)) + E[\sum_{n=1} \gamma^n R_n (s_n, a_n) | s_0 = s, \pi] \to R_0(s) + E_{s'}[\gamma V_1^\pi (s')]$
The Bellman equation for value function
- 위의 식에서 expectation sign 을 probabilities of transitions to all possible next states from the current state의 explicit sum 으로 바꾼다.
- 이는 value function의 recursive relation을 만드는데, Bellman equation이라고 불린다.
$V_t^\pi (s) = R_t (s_t) + \gamma \sum_{s_{t+1} \in S} p(s_{t+1} | s_t, a_t = \pi(s_t))V_{t+1}^\pi(s_{t+1})$
- Reward가 다음 상태인 S' 에 의해 결정될때 Bellman equation for vlaue function은 다음과 같다.
$V_t^\pi (s) = R_t (s_t) + \gamma \sum_{s_{t+1} \in S} p(s_{t+1} | s_t, a_t = \pi(s_t))V_{t+1}^\pi(s_{t+1})$
Bellman Equation for Time-Homogeneous MDPs
- 특이 케이스로, time-homogeneous MDPs의 경우, transition probabilities 와 rewards는 time에 의존적이지 않고, time horizion은 infinite하다. 그러한 경우, value function은 time에 의존적이지 않는다.
$V_t^\pi(s) \to V^\pi(s)$
- Bellman equation for a time-independent value function은 N linear equations의 system과 동일하다. (N은 discrete states를 의미)
$V_t^\pi(s) = R_t(s_t) + \gamma \sum{s_{t+1} \in S} p(s_{t+1} | s_t, a_t = \pi(s_t))V_t+1^\pi(s_{t+1})$
- tranisition probabilities를 알고 있다면, linear algebra를 통해서 이런 linear system을 풀수 있다.
V-star
- optimal value function을 v-star 라고 부르고,
- 가능한 모든 폴리시에서 highest value of function for the state 한것이 optimal value function이다.
$V_t^*(s_t) = max_\pi V_t^\pi (s_t)$
- 최적합은 $V^*(s) = V^pi^*(s) \geq V^\pi(s), \forall \pi \neq \pi^*$ 를 의미하고
- optimal policy v-star는 시스템의 모든 states에서 optimal하다.
- V-star는 다른 policy보다 같거나 더 크다.
- Bellman optimality quation for optimal value function V*(s)
$V_t^*(s_t) = R_t(s_t) + max_{a_t \to A} \gamma \sum_{s_{t+1} \in S} p(s_{t+1}|s_t, a_t)V_{t+1}^*(s_{t+1})$
* Bellman's principle of optimality는 현재의 state에 대한 optimal action을 취하고, 미래에도 optimal policy를 follow해야 optimal cumulative reward에 도달할수 있다.
- optimal value function을 알때, optimal policy를 구하려면,
$\pi_t(s_t) = argmax_{a_t \in A} \sum_{s_{t+1} \in S} p(s_{t+1}|s_t, a_t)V_t^*(s_{t+1}) $
QUIZ: Select all correct answers
1. The value function depends on the current state and the policy used to collect rewards.
2. The Bellman optimality equation is a system of linear equations.
3. The Bellman optimality equation is a non-linear equation that generally needs to be solved numerically.
4. The optimal value function is a maximum of all possible value functions for different policies among all possible policies.
5. The optimal value function is a value function that has the lowest complexity among all value function, to prevent overfitting.
6. The value function depends on the whole history of state transitions.
Answer: 1,3,4
The value function depends on the whole history of state transitions.
This is a translated note for the coursera course (linked below).
https://www.coursera.org/learn/reinforcement-learning-in-finance/lecture/PZbAt/introduction-to-markov-decision-processes-and-reinforcement-learning-in-finance
