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
0 answers
17 views

Proof that the Policy Iteration Converges?

Let $\mathcal{X}=:\{x_1, x_2, x_3,...,x_n\}$ be the state space. Let $\mathcal{U}:=\{u_1, u_2, u_3,...,u_m\}$ be the set of actions. Let $A^{u_1}, A^{u_2}, A^{u_3},...,A^{u_m}$ be the state transition ...
7 votes
2 answers
646 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
13 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
139 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 ...
0 votes
0 answers
67 views

How do you determine the optimal policy?

I am following some Grid world examples to understand reinforcement learning. I have a deterministic grid (part of which I have reconstructed below). I am trying to understand how the optimal policy ...
  • 1
0 votes
0 answers
13 views

How are previous values updated when performing value iteration?

I have been trying to understand how you determine the value for each square in a grid world and I have seen/watched a few different examples to try and apply it to my own grid and I find myself ...
  • 1
2 votes
1 answer
178 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
87 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
0 votes
1 answer
352 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 ...
  • 103
1 vote
0 answers
42 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 ...
1 vote
1 answer
69 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 ...
1 vote
1 answer
72 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
553 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
99 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
292 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 ...
1 vote
0 answers
14 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
171 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 ...
1 vote
1 answer
400 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 ...
3 votes
1 answer
90 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)$, ...
2 votes
1 answer
180 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
372 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
180 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
97 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 ...
2 votes
1 answer
87 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....
4 votes
1 answer
487 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
1k 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 ...
3 votes
2 answers
1k 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 ...
2 votes
1 answer
121 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
48 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
4 votes
1 answer
2k 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 ...
  • 181
1 vote
0 answers
324 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 ...
3 votes
1 answer
54 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?
3 votes
1 answer
92 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
660 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
521 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
732 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
482 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
363 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
2 votes
1 answer
5k 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
2k 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-...
  • 403
5 votes
1 answer
239 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 ...
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
351 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 ...