2
$\begingroup$

I wasn't sure whether to post this here or in the ai stack exchange - please let me know if i need to move my post elsewhere)

I have been learning about how dynamic programming can be used as a tool to solve the bellman optimality equations: (only show state value function)

$$ v_{*}(s) = \max\limits_{a\in A(s)}\sum\limits_{s',r} p(s',r|s,a)[r+\gamma v_{*}(s')]$$

I understand how backward induction can be used on the above equation to find the optimal policy and value function.

What I dont understand is how policy iteration and value iteration can be describe as "dynamic programming algorithms" i.e exploiting optimal overlapping substructure. I have provided my attempt at trying to answer this question below

Attempt at trying to answer

  1. In policy iteration do we consider ($v$,$\pi$) to be the "states" of the DP and we go back until we eventually converge on the optimal solution ($v_*$,$\pi_*$) as follows $$ (v_{t+1},\pi_{t+1}) \rightarrow (v_{t},\pi_{t+1}) \rightarrow (v_{t},\pi_{t}) $$

  2. For value iteration

    • in the case of episodic tasks (finite duration) we use the bellman optimality equations directly, initialising the value function for each state to some value (typically 0) at the terminating $t=T$ and backward inducting until we get to $t=0$ so that we can the find the optimal value functions and policy to use from $t=T$ through to $t=0$

    • For continuing tasks we apply the same approach as episodic task but we keep backward inducting until we forget the initial conditions and reach an equilibrium hence the expected returns for each time-step are time invariant

$$ v_{*}(S_{t+1}=s) = v_{*}(S_t=s)$$

Any insight into this would be great, thanks in advance!

$\endgroup$
1
  • $\begingroup$ thanks for the advice, i've rewritten the question to try and be more succinct, if there is anything anymore i should do please let me know $\endgroup$ – quest ions Nov 25 '20 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.