Questions tagged [value-iteration]

For questions related to the value iteration algorithm, which is a dynamic programming (DP) algorithm used to solve an MDP, that is, it is used to find a policy given the transition and reward functions of the MDP. Value iteration is related to another DP algorithm called policy iteration.

Filter by
Sorted by
Tagged with
1 vote
1 answer
53 views

How to derive "value iteration" from "policy iteration"?

This is the equation for "value iteration" from Sutton-Barto: \begin{align} v_{k+1}(s)=& \max_{a \in \mathcal{A}}\mathbb{E} \Big(R_{t+1}+\gamma v_k(S_{t+1}) \big|S_t=s, A_t=a\Big) \\ =&...
DSPinfinity's user avatar
2 votes
1 answer
173 views

What are the similarities between Q-learning and Value Iteration?

This is the explanation of value iteration in our notes where you keep applying bellman optimality equation till it stops changing and then acting greedily wrt the value function gives the optimal ...
ace239's user avatar
  • 23
2 votes
0 answers
140 views

Why solely a one-step-lookahead in value/policy-iteration?

In value iteration and policy iteration we solely consider a one-step-lookahead where the lookahead is from the previous iteraiton and therefore need to sweep over all states and iterate this ...
hugh's user avatar
  • 53
1 vote
0 answers
37 views

Can we use Low rank approximation in Markov decision process problem?

I am newbie in MDP.I have started reading Ronald Howard Dynamic Programming and MDP book as well as Sutton and Barto An Introduction to Reinforcement Learning. To my understanding MDP is a model based ...
Homer Jay Simpson's user avatar
1 vote
1 answer
205 views

How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?

I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards: $$V_0(s)=R(s)$$ $$V_{t}(s)=R(s)+\gamma\cdot\underset{a}{max}\underset{s'}{\...
Daniel's user avatar
  • 131
0 votes
0 answers
370 views

Convergence of Value Iteration for Discount factor of 1

Given this pseudo code for value iteration: In the case of gamma=1, under what conditions on the MDP will we still be able to find the optimal policy?
Toffe1369's user avatar
1 vote
0 answers
45 views

Would the optimal policy remain same, if I replace R with V*?

In the context of RL, say I'm performing Value Iteration on a reward function R1. And the converged optimal policy is P1 and values are V1. Then, let's say I set rewards to be R2=V1 and perform value ...
famishedrover's user avatar
5 votes
0 answers
74 views

What exactly is non-delusional Q-learning?

Problems occur when we combine Q-learning with a function approximator. What exactly is the delusional-bias and non-delusional Q-learning? I am talking about the neurIPS 18 best paper Non-delusional Q-...
wrek's user avatar
  • 183
7 votes
2 answers
2k views

In Value Iteration, why can we initialize the value function arbitrarily?

I have not been able to find a good explanation of this, other than statements that the algorithm is guaranteed to converge with arbitrary choices for initial values in each state. Is this something ...
Arham's user avatar
  • 73
1 vote
0 answers
15 views

Value iteration algorithm converge to max reward with discount of 1? [duplicate]

I'm running the value iteration algorithm of a gridworld of 4*3, with two terminal nodes with -50 reward and one with +20 reward like so: ...
JeanMi's user avatar
  • 165
4 votes
1 answer
594 views

What should the discount factor for the non-slippery version of the FrozenLake environment be?

I was working with FrozenLake 4x4 from open AI gym. In the slippery case, using a discounting factor of 1, my value iteration implementation was giving a success rate of around 75 percent. It was much ...
ketan dhanuka's user avatar
2 votes
1 answer
878 views

Factors that affect the number of iterations of value iteration

I had an assumption that value iteration will take more iterations to converge if the map size increases/environment's complexity increases. I tried to verify this idea by running value iteration on ...
john li's user avatar
  • 23
2 votes
1 answer
463 views

calculating the value of a state in an optimal policy analytically and iteratively

I am watching the lecture by Abbeel on MDPs and Reinforcement Learning. The setup of the problem is the classic gridworld with optimal policy (and corresponding values of states) pictured below. The ...
cgo's user avatar
  • 185
1 vote
2 answers
2k views

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

I am reading Reinforcement Learning: An Introduction by Sutton & Barto. According to this textbook, as far as I understood, the authors claim that the policy and value iteration methods converge ...
Danny_Kim's user avatar
  • 113
1 vote
0 answers
63 views

Can we combine policy evaluation and value iteration steps for solving model-based MDP?

In Sutton & Barto (2nd edition), at the very end on page 83, the following is mentioned: In general, the entire class of truncated policy iteration algorithms can be thought of as sequences of ...
user529295's user avatar
1 vote
1 answer
127 views

In value iteration, what happens if we try to obtain the greedy policy while looping through the states?

I am referring to the Value Iteration (VI) algorithm as mentioned in Sutton's book below. Rather than getting the greedy deterministic policy after VI converges, what happens if we try to obtain the ...
user529295's user avatar
1 vote
1 answer
303 views

Is it possible to have values of the states equal to $0$ at the end of the value iteration?

I am new to Reinforcement Learning and I am trying to self learn it. I have already posted some quesiton here and your answershave been really useful to me, so here I am posting another one. I am ...
dcr's user avatar
  • 57
1 vote
2 answers
1k views

What is the difference between a reward and a value for a given state?

I am trying to learn reinforcement learning and I am focusing on the value iteration. I am looking at the example of grid world, and I am trying to implement it in python. While doing this, I ...
dcr's user avatar
  • 57
3 votes
1 answer
195 views

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

I am trying to self learn reinforcement learning. At the moment I am focusing on policy and value iteration, and I am finding several problems and doubts. One of the main doubts is given by the fact ...
dcr's user avatar
  • 57
1 vote
1 answer
633 views

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

When applying the bellman expectation equation: $$v(s)=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s\right]$$ to the MRP below, states further away from the terminal state will ...
Paternostro's user avatar
1 vote
0 answers
21 views

Are the relative magnitudes of the learned and optimal state value function the same?

I have been reading recently about value and policy iteration. I tried to code the algorithms to understand them better and in the process I discovered something and I am not sure why is the case (or ...
Ralphns's user avatar
  • 11
2 votes
1 answer
570 views

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

Above is the algorithm for Policy Iteration from Sutton's RL book. So, step 2 actually looks like value iteration, and then, at step 3 (policy improvement), if the policy isn't stable it goes back to ...
user8714896's user avatar
1 vote
1 answer
1k views

Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem

In Example 4.3:Gambler's Problem of Sutton and Barto's book whose code is given here. In this code the value function array is initialized as np.zeros(states) where ...
ZERO NULLS's user avatar
4 votes
1 answer
171 views

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

I was looking at the Bellman equation, and I noticed a difference between the equations used in policy evaluation and value iteration. In policy evaluation, there was the presence of $\pi(a \mid s)$, ...
Chukwudi Ogbonna's user avatar
2 votes
1 answer
371 views

Is value iteration stopped after one update of each state?

In section 4.4 Value Iteration, the authors write One important special case is when policy evaluation is stopped after just one sweep (one update of each state). This algorithm is called value ...
Alex's user avatar
  • 23
5 votes
2 answers
667 views

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

In Sutton and Barto's book about reinforcement learning, policy iteration and value iterations are presented as separate/different algorithms. This is very confusing because policy iteration includes ...
User007's user avatar
  • 51
3 votes
2 answers
257 views

What is the value of a state when there is a certain probability that agent will die after each step?

We assume infinite horizon and discount factor $\gamma = 1$. At each step, after the agent takes an action and gets its reward, there is a probability $\alpha = 0.2$, that agent will die. The assumed ...
Milan Mitterko's user avatar
0 votes
0 answers
115 views

Problem in understanding equation given for convergence of TD(n) algorithm

Given equation 7.3 of Sutton and Barto's book for convergence of TD(n): $\max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)| \leqslant \gamma^n \max_s|V_{t+n-1}(s) - v_\pi(s)|$ $\textbf{PROBLEM ...
ZERO NULLS's user avatar
2 votes
1 answer
108 views

Is the PyTorch official tutorial really about Q-learning?

I read Q-learning algorithm and also I know value iteration (when you update action values). I think the PyTorch example is value iteration rather than Q-learning. Here is the link: https://pytorch....
dato nefaridze's user avatar
4 votes
2 answers
933 views

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

One way of understanding the difference between value function approaches, policy approaches and actor-critic approaches in reinforcement learning is the following: A critic explicitly models a value ...
dan888's user avatar
  • 91
3 votes
1 answer
2k views

What is generalized policy iteration?

I am reading Sutton and Barto's material now. I know value iteration, which is an iterative algorithm taking the maximum value of adjacent states, and policy iteration. But what is generalized policy ...
dato nefaridze's user avatar
3 votes
2 answers
2k views

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

I am trying to implement value and policy iteration algorithms. My value function from policy iteration looks vastly different from the values from value iteration, but the policy obtained from both ...
r4bb1t's user avatar
  • 335
2 votes
1 answer
221 views

Why do I need an initial arbitrary policy to implement value iteration algorithm

I've been recently given an assignment based on Reinforcement Learning and I'm supposed to implement the value iteration algorithm in a grid environment. The assignment: My doubt is why do I even ...
Carrick's user avatar
  • 121
0 votes
1 answer
153 views

Unable to understand V* at infinite time horizon using Bellman equation for solving MDP

I've been following the Berkeley cs188's assignment (I'm not taking the course). Currently, they don't show the solution in the gradescope unless I get it correct. My reasoning was $V^*(a)$ = 10 ...
libphy's user avatar
  • 111
5 votes
1 answer
3k views

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

I am trying to learn tabular Q learning by using a table of states and actions (i.e. no neural networks). I was trying it out on the FrozenLake environment. It's a very simple environment, where the ...
abkds's user avatar
  • 191
1 vote
0 answers
462 views

Is Value Iteration better than Policy Iteration for first few iterations?

In Policy Iteration (PI), the action generated by the policy, whether it's optimal or not w.r.t the current value function $v(s)$. Whereas, in Value Iteration, the action is greedily generated w.r.t ...
qiang li's user avatar
3 votes
1 answer
86 views

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?
qiang li's user avatar
3 votes
1 answer
261 views

Can I have different rewards for a single action based on which state it transitions to?

I am working on an MDP where there are four states and ten actions. I am supposed to derive the optimal policy to reach the desired state. At any state, a particular action can take you to any of the ...
Bhavana's user avatar
  • 83
4 votes
1 answer
1k views

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

Consider the grid world problem in RL. Formally, policy in RL is defined as $\pi(a|s)$. If we are solving grid world by policy iteration then the following pseudocode is used: My question is related ...
user avatar
1 vote
1 answer
837 views

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

I am simulating a Tic-Tac-Toe game with a human opponent. The way the RL trains is through policy/value iterations for a fixed number of iterations all specified by the user. Now, whether the human ...
user avatar
1 vote
1 answer
1k views

Unable to understand the second iteration update in value iteration algorithm for solving MDP

I am trying to understand the value iteration method for Markov Decision Process(MDP) and I was referring to UC Berkeley's slides titled Markov Decision Processes and Exact Solution Methods On slide ...
Devendra Vyas's user avatar
4 votes
1 answer
519 views

A few questions regarding the difference between policy iteration and value iteration [closed]

The question already has some answer. But I am still finding it quite unclear (also does $\pi(s)$ here mean $q(s,a)$ ?): The few things I do not understand are: Why the difference between 2 ...
user avatar
1 vote
1 answer
606 views

How do I apply the value iteration algorithm when there are two goal states?

I am working through the famous RL textbook by Sutton & Barto. Currently, I am on the value iteration chapter. To gain better understanding, I coded up a small example, inspired by this article. ...
cmplx96's user avatar
  • 113
3 votes
1 answer
8k views

What is the time complexity of the value iteration algorithm?

Recently, I have come across the information (lecture 8 and 9 about MDPs of this UC Berkeley AI course) that the time complexity for each iteration of the value iteration algorithm is $\mathcal{O}(|S|^...
Shifat E Arman's user avatar
5 votes
1 answer
3k views

Should the reward or the Q value be clipped for reinforcement learning

When extending reinforcement learning to the continuous states, continuous action case, we must use function approximators (linear or non-linear) to approximate the Q-value. It is well known that non-...
Rui Nian's user avatar
  • 433
5 votes
1 answer
496 views

How is the fitted Q-iteration algorithm related to $Q^*(s, a)$, and how can we use function approximation with this algorithm?

I hope to get some clarifications on Fitted Q-Iteration (FQI). My Research So Far I've read Sutton's book (specifically, ch 6 to 10), Ernst et al and this paper. I know that $Q^*(s, a)$ expresses the ...
NoviceProg's user avatar
2 votes
1 answer
2k views

Value iteration algorithm from pseudo-code to C++ [closed]

I am having a difficult time translating this pseudocode into functional C++ code. At line 10: The value function is represented as V[s], which has bracket notation-like arrays. Is this a separate ...
ALostBegginer's user avatar
4 votes
1 answer
756 views

Why can't we apply value iteration when we do not know the reward and transition functions, and how does Q-learning solve this issue?

I don't understand why we can't apply value iteration when don't know the reward and transition probabilities. In this lecture, the lecturer says it has to do with not being able to take max with ...
Abhishek Bhatia's user avatar