Skip to main content
6 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 ...
nbro's user avatar
  • 40.9k
4 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 ...
nbro's user avatar
  • 40.9k
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 ...
abkds's user avatar
  • 191
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
Neil Slater's user avatar
  • 32.7k
3 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 ...
nbro's user avatar
  • 40.9k
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
Kostya's user avatar
  • 2,534
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
David's user avatar
  • 4,920
3 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 ...
Neil Slater's user avatar
  • 32.7k
3 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,...
nbro's user avatar
  • 40.9k
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
nbro's user avatar
  • 40.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 ...
nbro's user avatar
  • 40.9k
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. ...
Kostya's user avatar
  • 2,534
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 ...
harwiltz's user avatar
  • 1,136
1 vote
Accepted

What is the right DRL algorithm to use when the goal in an environment is not fixed?

There is a possibility that the agent can generalize to land in an arbitrary goal region if the goal region is varied at the start of each training episode. If the locations of the goal region and ...
DeepQZero's user avatar
  • 1,424
1 vote
Accepted

In reinforcement learning policy evaluation, which reward is received?

The reward likely should be based on the dynamics of the environment not the intention of the agent. Imagine if $r_2$ was a large negative reward and $p_2 > p_1$. This should be captured in the ...
foreverska's user avatar
  • 1,298
1 vote
Accepted

Do I really need to do policy evaluation until convergence in policy iteration?

I don't understand why policy evaluation needs to be done until convergence It doesn't need to be, although the resulting algorithm if you cut short of convergence is not strictly policy iteration as ...
Neil Slater's user avatar
  • 32.7k
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
Neil Slater's user avatar
  • 32.7k
1 vote
Accepted

When to use Value Iteration vs. Policy Iteration

Value Iteration Vs Policy Iteration Below is the list of differences & similarities between value iteration and policy iteration Differences Value Iteration Policy Iteration Architecture VI ...
Archana David's user avatar
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 ...
James's user avatar
  • 241
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 ...
Neil Slater's user avatar
  • 32.7k
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 ...
present's user avatar
  • 241
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 ...
Swakshar Deb's 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 ...
Neil Slater's user avatar
  • 32.7k

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