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.
47
questions
1
vote
0
answers
28
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 ...
- 23
1
vote
0
answers
24
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 ...
1
vote
1
answer
136
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'}{\...
- 131
0
votes
0
answers
21
views
Under which conditions does value iteration and policy iteration will give us the optimal solution if gamma equals 1
I’m learning about policy iteration and value iteration, and I’m wondering under which conditions does both algorithms will give us the optimal solution, if our discount factor (gamma) equals 1.
Note: ...
0
votes
0
answers
161
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?
1
vote
0
answers
42
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 ...
5
votes
0
answers
63
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-...
- 183
7
votes
2
answers
1k
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 ...
- 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:
...
- 155
4
votes
1
answer
411
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 ...
2
votes
1
answer
624
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 ...
- 23
2
votes
1
answer
308
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 ...
- 175
1
vote
2
answers
1k
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 ...
- 113
1
vote
0
answers
50
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 ...
- 359
1
vote
1
answer
111
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 ...
- 359
1
vote
1
answer
220
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 ...
- 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 ...
- 57
3
votes
1
answer
128
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 ...
- 57
1
vote
1
answer
520
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 ...
- 19
1
vote
0
answers
18
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 ...
- 11
2
votes
1
answer
437
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 ...
- 717
1
vote
1
answer
807
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 ...
- 147
4
votes
1
answer
134
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)$, ...
- 125
2
votes
1
answer
329
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 ...
- 23
5
votes
2
answers
584
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 ...
- 51
3
votes
2
answers
232
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 ...
0
votes
0
answers
111
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 ...
- 147
2
votes
1
answer
97
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....
- 862
4
votes
2
answers
747
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 ...
- 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 ...
- 862
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 ...
- 305
2
votes
1
answer
171
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 ...
- 121
0
votes
1
answer
134
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 ...
- 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 ...
- 191
1
vote
0
answers
435
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 ...
- 83
3
votes
1
answer
81
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?
- 83
3
votes
1
answer
189
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 ...
- 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 ...
user9947
1
vote
1
answer
748
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 ...
user9947
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 ...
4
votes
1
answer
504
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 ...
user9947
1
vote
1
answer
501
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.
...
- 113
3
votes
1
answer
7k
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|^...
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-...
- 423
5
votes
1
answer
425
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 ...
- 153
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 ...
4
votes
1
answer
624
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 ...
- 427