[Reinforcement Learning in Finance] MDP & RL: Value Iteration and Policy Iteration

Time homogeneous market decision process에서 value function은 시간과 독립적이다.

- 이러한 경우에 bellman optimality ㄷquation은 numerical methods를 이용하여 계산하는single function에 대한 non-linear equation이다. 

- 이러한 방법은 value iteration이라고 하는데, state action space가 discrete 하고 작은 경우에, 간단하고 빠른 솔루션을 제공한다. 

Bellman Equation for optimal value function

$V^*(s) = R(s) + max_{a \in A} \gamma \sum_{s' \in S} p(s'|s,a)V^*(s')$

Value Iteration Algorithm (for discrete state-action space):

$V(s) = V^{(0)}(s)$

- 모든 상태에 대한 value function의 어떤 initial values로 초기화한다. (보통 initialization at zero for all states 으로 설정)

- 그리고 bellman equation으로 convergence할때까지 계속 value function을 반복 계산한다.

$V^{(k+1)}(s) = R(s) + max_{a \in A} \gamma \sum_{s' \in S} p(s'|s,a)V^{(k)}(s')$

- 각 반복단계에서는, 이전단계의 결과를 사용하여, 위식의 오른쪽을 계산한다. 

- value iteration에서 value function 을 업데이트 하기 위해서는

1. synchronous updates: iteration이 끝날때까지 기다리고 모든 states의 value function을 한번에 업데이트

2. Asynchronous updates: iteration 도중에 업데이트

- optimal policy: $\pi^*(s) = argmax_{a \in A} \sum_{s' \in S} p(s'|s,a)V^*(s')$

- policy iteration algorithm:

1. initialize policy randomly $\pi(s) = \pi^{(0)}(s)$

2. repeat the update of the value function until convergence.

- policy evaluation: bellman equation 에서 value function으로 $V^\pi (s)$를 계산

- iterate policy $\pi^{(k+1)}(s) = argmax_{a \in A} \sum_{s' \in S} p(s'|s,a)V^{(\pi)}(s')$

- Policy iteration step은 기본 optimization software로 이뤄질수 있지만, policy evaluation은 bellman equation을 여러번 풀어야하는등 critical하고 large state spaces가 소모된다. 

QUIZ: Select all correct answers

1. The optimal policy is a policy for which the Bellman equation is fastest to solve.

2. Optimal policy calculation in Value Iteration is computationally the same as a policy iteration step in Policy Iteration method.

3. The policy evaluation step can be done using standard optimization software.

Answer: 2

Large state-action spaces 나 continuous state-action spaces의 경우는 value iteration이나 policy iteration등의 dynammic programming과 알고리즘으로 충분히 해결할수 없다. 

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