4

Yes, the two update equations are equivalent. As an aside, technically the equation you give is not the Bellman equation, but the update step re-written as an equation - in the Bellman equation instead of $v_{k+1}(s)$ or $v_{k}(s)$ (showing iterations of approximate value functions), you would have $v_{\pi}(s)$ (representing the true value of a state under ...


3

Your calculations are correct, but you have misinterpreted the equations and the diagram. The index $k$ in $v_k$ for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation $\pi'$ and does not mention $k$). Policy improvement consists of multiple sweeps through states to fully ...


3

There is a difference between accurate value function estimates, and optimal value functions. An optimal value function is more specifically the value function of an optimal policy. Value functions are always specific to some policy, which is why you will often see the subscript $\pi$ in e.g. $v_{\pi}(s)$ when there is a defined policy. The policy evaluation ...


3

Policy iteration is made up of two steps. The first is a full policy evaluation, where a value function is calculated for the current policy. The second is policy improvement, where the policy is made greedy with respect to the value function. Value iteration looks to speed things up by stopping policy evaluation after one iteration, make the policy greedy ...


3

I was able to solve the problem. The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $-0.00005$ on the learning rate lr, and subsequently Q-Learning also converged to the same value as value iteration.


2

Keeping this taxonomy intact for model-based Dynamic programming algorithms, I would argue that value iteration is a Actor only approach, and policy iteration is a Actor-Critic approach. However, not many people discuss the term Actor-Critic when referring to Policy Iteration. How come? Both policy iteration and value iteration are value-based approaches. ...


2

Is it still a policy iteration algorithm if the policy is updated optimizing a function of the immediate reward instead of the value function? Technically yes. The value update step in Policy Iteration is: $$v(s) \leftarrow \sum_{r,s'}p(r,s'|s,\pi(s))(r + \gamma v(s'))$$ The discount factor $\gamma$ can be set to $0$, making the update: $$v(s) \...


2

A policy can be stochastic or deterministic. A deterministic policy is a function of the form $\pi_{\text{deterministic}}: S \rightarrow A$, that is, a function from the set of states to the set of actions. A stochastic policy is a map of the form $\pi_{\text{stochastic}} : S \rightarrow P(A)$, where $P(A)$ is a set of probability distributions ($P(A) = \{ ...


2

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations. Policy iteration In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|...


1

Policy iteration is based on the insight that for a given policy, it is straightforward to compute the value function (the long-run expected discounted value of being in a given stage) exactly -- it is a set of linear equations at that point. So, we update the policy, then calculate the exact values of the states for always following that particular policy, ...


1

I am assuming you are aware of the meaning of the notations. I will provide an informal explanation. From your comment I am guessing you have difficulty in this portion in the 1st equation: \begin{align} {\scriptsize \max_{s} \gamma \sum_{s^{\prime}} \operatorname{Pr} \left( s^{\prime} \mid s, \pi(s) \right) \left| V\left(s^{\prime}\right) - U \left(s^{\...


1

The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} where $U$ and $V$ are two value functions, follows from the definition of Bellman policy operator (at slide 16) \begin{align} T^{\pi} V(s) &\triangleq R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime}...


1

In the standard policy iteration algorithm presented in Sutton and Barto's book, you alternate between a policy evaluation (PE) step and a policy improvement (PI) step (i.e. PE, PI, PE, PI, PE, PI, PE, ...). However, in general, you don't have to follow this alternation strictly in order to converge (in the limit) to the optimal policy. For example, value ...


1

Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged). However, they do this differently. VI can be seen as truncated version of PI. Let me first illustrate the pseudocode of both algorithms (taken from ...


1

Everything you say in your post is correct, apart from the wrong assumption that policy iteration is model-free. PI is a model-based algorithm because of the reasons you're mentioning. See my answer to the question What's the difference between model-free and model-based reinforcement learning?.


Only top voted, non community-wiki answers of a minimum length are eligible