25 votes
Accepted

What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation?

The first-visit and the every-visit Monte-Carlo (MC) algorithms are both used to solve the prediction problem (or, also called, "evaluation problem"), that is, the problem of estimating the value ...
nbro's user avatar
  • 40.4k
8 votes
Accepted

What is the proof that policy evaluation converges to the optimal solution?

First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. ...
nbro's user avatar
  • 40.4k
5 votes

Why can the Bellman equation be turned into an update rule?

Why are we allowed to convert the Bellman equations into update rules? There is a simple reason for this: convergence. The same chapter 4 of the same book mentions it. For example, in the case of ...
nbro's user avatar
  • 40.4k
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
  • 31.8k
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
  • 31.8k
3 votes
Accepted

Is value iteration stopped after one update of each state?

Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the ...
David's user avatar
  • 4,790
3 votes
Accepted

Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?

In essence, your question is about convergence of infinite series. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "...
Kostya's user avatar
  • 2,515
2 votes
Accepted

Why isn't the implementation of my policy evaluation for a simple MDP converging?

The issue is that in your list comprehension in def V_pi(state) you have ...
Chris Cundy's user avatar
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
  • 31.8k
1 vote

Why does my implementation of TD(0) not work?

It is a very simple example with terminal states s2 and s3 and it is clear that the Value function should converge to: ...
Neil Slater's user avatar
  • 31.8k
1 vote
Accepted

Can we use Q-learning update for policy evaluation (not control)?

For off-policy learning you must have two policies - a behaviour policy and a target policy. If the two policies are the same, then you end up with SARSA, not Q learning. You cannot use Q learning ...
Neil Slater's user avatar
  • 31.8k
1 vote
Accepted

How can I implement policy evaluation when reward is tied to an action outcome?

The renowned book Reinforcement Learning: An Introduction (2nd edition), by Sutton and Barto, provides a different update rule than your first update rule for policy evaluation. Their update rule is ...
nbro's user avatar
  • 40.4k
1 vote

Why can the Bellman equation be turned into an update rule?

To me, Bellman update is simply supervised learning: right hand side (bootstrap) is a sample of the left hand side (conditional expectation).. The Bellman equation simply explains that the right hand ...
kaiwenw's user avatar
  • 151
1 vote
Accepted

How does policy evaluation work for continuous state space model-free approaches?

How does policy evaluation work for continuous state space model-free approaches? ... Let's say you use a DQN to find another policy, how does model-free policy evaluation work then? Policy ...
DeepQZero's user avatar
  • 1,379
1 vote

What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation?

For anyone coming across this question and wants a very intuitive understanding of first and every visit monte-carlo, look at the answer given in the link provided here. https://amp.reddit.com/r/...
Mugumya kevin's user avatar

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