4 votes
Accepted

Why is update rule of the value function different in policy evaluation and policy iteration?

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 ...
user avatar
  • 23.1k
4 votes
Accepted

Why is my implementation of Q-learning not converging to the right values in the FrozenLake environment?

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 ...
user avatar
  • 181
4 votes
Accepted

Why doesn't value iteration use $\pi(a \mid s)$ while policy evaluation does?

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 ...
user avatar
  • 23.1k
4 votes

Why are the Bellman operators contractions?

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 ...
user avatar
  • 32.9k
3 votes
Accepted

Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?

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 ...
user avatar
  • 23.1k
3 votes

Why do we need to go back to policy evaluation after policy improvement if the policy is not stable?

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 ...
user avatar
  • 23.1k
3 votes

Why are policy iteration and value iteration studied as separate algorithms?

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 ...
user avatar
3 votes

Does the policy iteration convergence hold for finite-horizon MDP?

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 ...
user avatar
  • 1,763
2 votes
Accepted

Can policy iteration use only the immediate reward for updates?

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 ...
user avatar
  • 23.1k
2 votes
Accepted

Understanding the update rule for the policy in the policy iteration algorithm

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 ...
user avatar
  • 32.9k
2 votes

What is generalized policy iteration?

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,...
user avatar
  • 32.9k
2 votes
Accepted

Why do value iteration and policy iteration obtain similar policies even though they have different value functions?

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 ...
user avatar
  • 32.9k
2 votes
Accepted

How can the policy iteration algorithm be model-free if it uses the transition probabilities?

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 ...
user avatar
  • 32.9k
2 votes

Would you categorize policy iteration as an actor-critic reinforcement learning approach?

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 ...
user avatar
  • 23.1k
2 votes
Accepted

Converging to a wrong optimal policy if the agent is given more choices

Reinforcement Learning is really fun because the agent will find any bug in your implementation and will exploit it. ...
user avatar
  • 1,763
2 votes
Accepted

Why and how can the policy and value iteration methods converge to the OPTIMAL point?

These two algorithms converge to the optimal value function because they are instances of the generalization policy iteration, so they iteratively perform one policy evaluation (PE) step followed by ...
user avatar
  • 32.9k
2 votes
Accepted

Are policy and value iteration used only in grid world like scenarios?

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 ...
user avatar
  • 961
1 vote
Accepted

How is policy iteration capable of improving on a deterministic policy?

These statements are not true for policy iteration and dynamic programming: Since the policy is stochastic and the initial state is the same, we'll always take the same path and evaluate the same ...
user avatar
  • 23.1k
1 vote

Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?

I think you have constructed a bad case for the algorithm as given. You have created an infinite loop and set starting values such that there is no chance for the loop to break out. You have also ...
user avatar
  • 23.1k
1 vote
Accepted

How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?

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 ...
user avatar
  • 221
1 vote

Bellman Expectation Equation leading to results where value iteration would not converge to the optimal policy

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 ...
user avatar
  • 23.1k
1 vote

Why are policy iteration and value iteration studied as separate algorithms?

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 ...
user avatar
  • 231
1 vote
Accepted

Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?

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 ...
user avatar
1 vote
Accepted

In tic-tac-toe, what is the effect of the starting state on the state and action value function?

My understanding - from comments on the question - is that you are looking to train a Reinforcement Learning agent on the game of Tic Tac Toe (perhaps just in theory), where the agent should learn to ...
user avatar
  • 23.1k

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