Skip to main content

Questions tagged [bellman-equations]

For questions related to the Bellman equations in the context of reinforcement learning (and other artificial intelligence subfields).

Filter by
Sorted by
Tagged with
2 votes
1 answer
55 views

Proof of existence of optimal policy

I have been trying to prove existence of an optimal policy for RL. I have proved that the Bellman optimality operator, $B: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$ given by $$B(v_\pi)...
mNugget's user avatar
  • 167
2 votes
1 answer
226 views

Proof of bellman optimality equations

I am studying RL and have a hard time proving the existence of an optimal policy. I found some resources online, and I am trying to prove the following theorem: If there exists a policy $\pi$, state $...
mNugget's user avatar
  • 167
1 vote
0 answers
39 views

Solving MDP as linear program: why minimize the sum of the states' values?

This is a follow-up question to the answer to How can we use linear programming to solve an MDP? Quick recap: the $max$ operators that appear in the Bellman optimality equations can be turned into a ...
Celelibi's user avatar
  • 111
0 votes
0 answers
41 views

Direct solving of Bellman optimality equation [duplicate]

I'm reading the Sutton and Barto second edition (the 2020 revision). I'm on chapter 3.6 "Optimal Policies and Optimal Value Functions". It is suggested that the Bellman optimality equations ...
Celelibi's user avatar
  • 111
0 votes
0 answers
73 views

Bellman equation for MRP

Bellman equation for MRP is: And it can be written as or the inverse matrix method, when the transition matrix is known. My question is: how the left $v$ equals to the right $v$ in the second ...
Goldhand's user avatar
2 votes
1 answer
178 views

Bellman equation and inverse matrix method

My problem: why the last formula do not contain information about time $t$? So if $s^{\prime}=s$, do we have $v_{\pi}(s) = v_{\pi}(s^{\prime})$? But this is not right I guess? If I am right, that they ...
Goldhand's user avatar
1 vote
0 answers
66 views

When can we unnest the minimizations/recursions in an value function(bellman optimality equation)?

When reading the following paper(page 4): An Approximate Dynamic Programming Approach for Dual Stochastic Model Predictive Control I could see that they were able to unnest the minimization's in the ...
richard baws's user avatar
2 votes
0 answers
161 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
0 votes
1 answer
191 views

Calculating state value using bellman equation question:

Consider a 4x4 grid world problem where the goal is to reach either the top left or bottom right corner. The agent can choose from four actions up,down,left,right which deterministically cause the ...
ace239's user avatar
  • 23
0 votes
0 answers
18 views

Proof of Difference in Return Between Two Policies

I am attempting to understand why Lemma 6.1 holds in this paper on reinforcement learning. I have two questions. First, when defining the value function V(s), why is there a leading (1-γ) term? In the ...
Nikhil Sridhar's user avatar
3 votes
2 answers
303 views

How do we get the optimal value-function?

In here it says that: (is it correct?) $$V^\pi = \sum_{a \in A}\pi(a|s)*Q^\pi(s,a)$$ And we have: $$ V^*(s) = max_\pi V^\pi(s)$$ Also: $$ V^*(s) = max_a Q^*(s, a) $$ Can someone demonstrate to me step ...
Ness's user avatar
  • 206
4 votes
1 answer
100 views

Could you explain these 2 steps of the derivation of the Bellman equation as a recursive equation in Sutton & Barto?

I am reading the Sutton & Barto (2018) RL textbook. On page 59, it derives the recursive property of the state-value function as below. Could you explain the steps of third and fourth equality? ...
tesio's user avatar
  • 205
0 votes
0 answers
113 views

Bellman optimality equation does not allow random policies?

I'm reading the Sutton & Barto's book "Reinforcement Learning: An Introduction" (2nd Edition). There is something I don't understand (p.63): ...
FluidMechanics Potential Flows's user avatar
0 votes
1 answer
206 views

How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?

The Question I'd like to prove that a function $V$ (like in reinforcement learning) is optimal iff it satisfies the bellman equation. A lot of places online reference this fact, but none prove it. ...
snatchysquid's user avatar
2 votes
2 answers
213 views

How the proof of the contraction of variance for distributional Bellman operator follows

I am stuck at the proof of the contraction of variance for distributional Bellman operator from the paper, in which it is defined as and the proof is stated as In its second part, how is the ...
Magi Feeney's user avatar
3 votes
1 answer
211 views

Why does A2C use the actual returns from an episode in calculating the advantage?

Why does A2C use the actual returns from an episode in calculating the advantage instead of using a bellman equation style estimate of the value? Basically, why this: $A(s,a) = \sum_t\gamma^tr_t - V(s)...
JacKeown's user avatar
  • 125
1 vote
1 answer
87 views

How are these two equations for the optimal state-value function equivalent?

By substituting the optimal policy $\pi_{\star}$ into the Bellman equation, we get the Bellman equation for $v_{\pi_{\star}}(s)=v_{\star}(s)$: $$ v_{\star}(s) = \sum\limits_a \pi_{\star}(a|s) \sum\...
DSPinfinity's user avatar
1 vote
2 answers
220 views

Why $V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s,a),\forall s \in S$ in reinforcement learning?

In some RL notes, I encountered the following equation, which I am trying to prove: $$ V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s, a),\forall s \in S $$ Here is my attemption: Firstly, I only need to ...
vincen's user avatar
  • 11
2 votes
1 answer
192 views

What is the difference between these two versions of the Bellman equation?

The first version is the one I am most familiar with: $$V_\pi(s) = \sum_{a}^{}\pi(a|s) \sum_{s'}^{}T(s, a, s')[R(s, a, s') + \gamma V_\pi(s')]$$ where $T(s, a, s')$ represents the probability of ...
Nova's user avatar
  • 133
2 votes
1 answer
1k views

Are my proofs that the Bellman operators are contractions correct?

Introduction I'm studying Reinforcement Learning, and in order to increase my understanding I've been challenging myself by trying to write proofs that show that the right hand side of the Bellman ...
cfml's user avatar
  • 53
1 vote
0 answers
30 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 ...
SHASHANK RANJAN's user avatar
1 vote
1 answer
141 views

What would be the Bellman optimality equation for $q_∗(s, a)$ for an MDP with continuous states and actions?

I'm currently studying Reinforcement Learning and I'd like to know what would be the Bellman optimality equation for action values $q_∗(s, a)$ for a MDP with continuous states and actions, written out ...
user's user avatar
  • 145
0 votes
1 answer
219 views

Is my derivation of the Bellman equation for $q_{\pi}$ in terms of $p(s'|s,a)$ and $r(s,a)$ correct?

I have done exercise 3.29 from Sutton and Barto and I'd like to check if it's correct. Here's the exercise: Rewrite the Bellman equation for the function $q_{\pi}$ in terms of the three argument ...
user's user avatar
  • 145
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
3 votes
1 answer
106 views

Can we also estimate $V_{\pi}$ with SARSA?

For SARSA, I know we can estimate the action value $Q(s,a)$, and the relationship between $V(s)$ and $Q(s,a)$ is $V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s)Q_{\pi} (s,a)$. So my question is, can ...
Dingzhi Hu's user avatar
-1 votes
1 answer
1k views

What is so special about the Bellman Optimality Principle?

In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this ...
stats_noob's user avatar
2 votes
1 answer
351 views

Determining to terminate at a reward or not

I am practicing the Bellman equation on Grid world examples and in this scenario, there are numbered grid squares where the agent can choose to terminate and collect the reward equal to the amount ...
Krellex's user avatar
  • 145
2 votes
2 answers
1k views

What is the Bellman equation for V(s) in the case of a deterministic environment?

I am currently trying to practice reinforcement learning for an agent on a grid. The grid is deterministic. Since the grid is deterministic, to calculate the value for each grid square from the reward ...
Krellex's user avatar
  • 145
0 votes
0 answers
184 views

Determine Gridworld values

I am learning Reinforcement learning for games following Gridworld examples. Apologies in advance if this is a basic question, very new to reinforcement learning. I am slightly confused in scenarios ...
Krellex's user avatar
  • 145
3 votes
1 answer
2k views

What is the difference between a greedy policy and an optimal policy?

I am struggling to understand what is the difference between an optimal policy and a greedy policy. Let $F(r_{t+1},s_{t+1}| s_t,a_t)$ be the probability distribution accorting to which, given action $...
fennel's user avatar
  • 33
2 votes
1 answer
489 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
2 votes
1 answer
289 views

Where are the parentheses in the Bellman update rule?

I'm not having a lot of intuition about the equation. I have this Bellman update rule: $$v_{\pi}(s) =\sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)[r+ \gamma v_{k}(s')]$$ But where are the parenthesis? Is the ...
nammerkage's user avatar
1 vote
1 answer
56 views

Would it be possible to enforce the same $s_{t + 1}$ between the model's estimate and the target function's Q-value?

Say I have a game of blackjack, and I am trying to teach a single forward-pass neural network to approximate the Q value of the current state and action. There are 3 inputs: The current card in hand, ...
GeorgeWTrump's user avatar
3 votes
1 answer
441 views

Can an optimal policy have a value function that has a smaller value for a state than a non-optimal policy?

I'm starting to learn about the Bellman Equation and a question came to my mind. A policy $\pi$ is optimal if the value $v_\pi(s)$ is greater or equal than the value $v_{\pi'}(s)$ for all states $s \...
raphael_mav's user avatar
1 vote
1 answer
275 views

What is the difference between gradient decent in neural networks and temporal difference in reinforcement learning?

I am studying Q-learning in reinforcement learning. My question is about the Bellman equation. In Q-learning, the Bellman equation is often introduced as follows. \begin{align} Q_{new}(s,a) &= Q_{...
Osama El-Ghonimy's user avatar
1 vote
1 answer
272 views

How are these two versions of the Bellman optimality equation related?

I saw two versions of the optimality equation for $V_{*}(s)$ and $Q_{*}(s,a)$. The first one is: $$ V_{*}(s)=\max _{a} \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma V_{*}\left(s^{\prime}\...
Kronic's user avatar
  • 49
3 votes
2 answers
409 views

Why must the value of a state under an optimal policy equal the expected return for the best action from that state?

The Sutton and Barto reinforcement learning textbook states that the value of a state under an optimal policy must equal the expected return for the best action from that state. That is, $$v_*(s) = \...
bonzo_pippinpaddle's user avatar
3 votes
2 answers
1k views

How can we find the value function by solving a system of linear equations?

I am following the book "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, and they give an example of a problem for which the value function can be computed ...
phil's user avatar
  • 143
5 votes
1 answer
3k views

What do the terms 'Bellman backup' and 'Bellman error' mean?

Some RL literature use terms such as: 'Bellman backup' and 'Bellman error'. What do these terms refer to?
user529295's user avatar
4 votes
1 answer
153 views

How to prove the second form of Bellman's equation?

I'd like to prove this "second form" of Bellman's equation: $v(s) = \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_{t} = s]$ starting from Bellman's equation: $v(s) = \mathbb{E}[G_{t} \mid ...
Daviiid's user avatar
  • 575
0 votes
1 answer
235 views

How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?

I am trying to understand the problem below, represented as an MDP with four states (PU, PF, RU, and RF) and two actions (AS). Let's consider V(RF), the value of the state RF. At time-step $h$, V(RF) ...
AHF's user avatar
  • 61
0 votes
1 answer
220 views

Converging to a wrong optimal policy if the agent is given more choices

I am a bit new to Reinforcement learning. So, I am extremely sorry if I am asking something obvious. I have written a small piece of code to find the optimal policy for a 5x5 grid problem. Scenario 1....
Tyrion 's user avatar
-2 votes
1 answer
910 views

Why the optimal Bellman operator of a Q-function can be approximated by a single point

I am currently studying reinforcement learning, especially DQN. In DQN, learning proceeds in such a way as to minimize the norm (least-squares, Huber, etc.) of the optimal Bellman equation and the ...
user's user avatar
  • 97
1 vote
1 answer
705 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
2 votes
1 answer
2k views

How to avoid being stuck local optima in q-learning and q-network

When using the Bellman equation to update q-table or train q-network to fit greedy max values, the q-values very often get to the local optima and get stuck although randomization rate ($\epsilon$) ...
Dan D.'s user avatar
  • 1,293
5 votes
1 answer
1k views

How would I compute the optimal state-action value for a certain state and action?

I am currently trying to learn reinforcement learning and I started with the basic gridworld application. I tried Q-learning with the following parameters: Learning rate = 0.1 Discount factor = 0.95 ...
Rim Sleimi's user avatar
3 votes
1 answer
355 views

How can we find the value function by solving a system of linear equations without knowing the policy?

An MDP is a Markov Reward Process with decisions, it’s an environment in which all states are Markov. This is what we want to solve. An MDP is a tuple $(S, A, P, R, \gamma)$, where $S$ is our state ...
Abc1729's user avatar
  • 45
2 votes
1 answer
149 views

How to prove the formula of eligibility traces operator in reinforcement learning?

I don't understand how the formula in the red circle is derived. The screenshot is taken from this paper
hijkzzz's user avatar
  • 23
2 votes
1 answer
770 views

How to derive matrix form of the Bellman operators?

Reading the Retrace paper (Safe and efficient off-policy reinforcement learning) I saw they often use a matrix form of the Bellman operators, for example as in the picture below. How do we derive ...
Federico Taschin's user avatar
6 votes
2 answers
2k views

What is the Bellman Equation actually telling?

What does the Bellman equation actually say? And are there many flavours of that? I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly ...
Johnny's user avatar
  • 69