# Tag Info

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 ...

4

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.

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

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|... 3 In the discussion about Neil Slater's answer (that he, sadly, deleted) it was pointed out that the policy$\pi$should also depend on the horizon$h$. The decision of action$a$can be influenced by how many steps are left. So, the "policy" in that case is actually a collection of policies$\pi_h(a|s)$indexed by$h$- the distance to horizon. ... 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 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 ... 2 The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} whereU$and$Vare 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}... 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 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 Reinforcement Learning is really fun because the agent will find any bug in your implementation and will exploit it. >>> take_left(0) 0 >>> take_left(1) -4 The agent figured out your bug with negative values and exploits negative indexing to get to the target faster. 2 Policy and value iteration both require you to, for each possible transition and each corresponding possible reward at each state, compute a statistic of r + \gamma V(s'). In order for this to be tractable, you need for there to be at most finitely many states, actions, possible rewards, and possible transitions at each state. You also need to know the ... 1 Wow, that's a really confusing example, if I were you I would check out some other RL resources. I wouldn't consider h being the last step and h-1 being the previous step. In terms of steps of iterations of the dynamic programming algorithm, h is actually the first step, h-1 the next step and so on. Viewing it in these terms it makes sense that the Value of ... 1 What am I missing here? You are not missing anything mathematically. Potentially what you are missing is that the discount factor \gamma, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any ... 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 think this equation answer your question:$$ q_{\pi^{i}}(s,\pi^{i+1}(s)) = \mathbf{E}[q_{\pi^{i}}(s,\pi^{i+1}(s))] = \sum_{a \in A}\pi^{i+1}(a|s)q_{\pi^{i}}(s,a)$$value of the Q while taking action from policy$\pi^{i+1}$and thereafter following the policy$\pi^{i}$is equal to the expected q value while taking action from policy$\pi^{i+1}\$ and ...

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