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
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 ...
0 votes
1 answer
69 views

Bellman optimality equation for continuous variables

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 ...
  • 81
0 votes
1 answer
42 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 ...
  • 81
0 votes
0 answers
27 views

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

I have 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 value function $v_{\pi}$ in terms of the three argument ...
  • 81
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
0 votes
0 answers
23 views

Why is the projection reasonable in C51 algorithm?

In this paper, there is an equation about the projection. The author said we project the sample Bellman update $\hat{T}Z_θ$ onto the support of $Z_θ$ Why is the original support reasonable? And why ...
  • 3
3 votes
1 answer
41 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 ...
-1 votes
1 answer
69 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 ...
2 votes
1 answer
184 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 ...
  • 135
1 vote
2 answers
205 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 ...
  • 135
0 votes
0 answers
32 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 ...
  • 135
3 votes
1 answer
607 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 $...
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
2 votes
1 answer
257 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 ...
1 vote
1 answer
51 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, ...
3 votes
1 answer
146 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 \...
1 vote
1 answer
112 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_{...
1 vote
1 answer
85 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}\...
  • 49
2 votes
1 answer
78 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) = \...
3 votes
2 answers
491 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 ...
  • 143
3 votes
1 answer
721 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?
3 votes
1 answer
109 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 ...
  • 509
0 votes
1 answer
114 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) ...
  • 61
0 votes
1 answer
78 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....
-2 votes
1 answer
381 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 ...
  • 97
1 vote
1 answer
291 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 ...
2 votes
1 answer
738 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$) ...
  • 1,223
5 votes
1 answer
396 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 ...
3 votes
1 answer
234 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 ...
  • 35
2 votes
1 answer
113 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
  • 23
1 vote
1 answer
246 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 ...
5 votes
2 answers
1k 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 ...
  • 59
1 vote
1 answer
48 views

Equivalence of the $Q(s,a)$ and $V(s)$ under optimality conditions?

Are the state-action values and the state value function equivalent for a given policy? I would assume so as the value function is defined as $V(s)=\sum_a \pi(a|s)Q_{\pi}(s,a)$. If we are operating a ...
7 votes
1 answer
644 views

How is the DQN loss derived from (or theoretically motivated by) the Bellman equation, and how is it related to the Q-learning update?

I'm doing a project on Reinforcement Learning. I programmed an agent that uses DDQN. There are a lot of tutorials on that, so the code implementation was not that hard. However, I have problems ...
4 votes
1 answer
213 views

How are afterstate value functions mathematically defined?

In this answer, afterstate value functions are mentioned, and that temporal-difference (TD) and Monte Carlo (MC) methods can also use these value functions. Mathematically, how are these value ...
  • 35k
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)$, ...
8 votes
2 answers
1k views

Why are the Bellman operators contractions?

In these slides, it is written \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \tag{9} \label{9} \\ \|T V-T U\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \...
  • 181
7 votes
0 answers
216 views

Is the Bellman equation that uses sampling weighted by the Q values (instead of max) a contraction?

It is proved that the Bellman update is a contraction (1). Here is the Bellman update that is used for Q-Learning: $$Q_{t+1}(s, a) = Q_{t}(s, a) + \alpha*(r(s, a, s') + \gamma \max_{a^*} (Q_{t}(s', ...
1 vote
1 answer
41 views

If the transition model is available, why would we use sample-based algorithms?

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model. Assuming I do have access to a transition model, are ...
1 vote
1 answer
209 views

Connection between the Bellman equation for the action value function $q_\pi(s,a)$ and expressing $q_\pi(s,a) = q_\pi(s, a,v_\pi(s'))$

When deriving the Bellman equation for $q_\pi(s,a)$, we have $q_\pi(s,a) = E_\pi[G_t | S_t = s, A_t = a] = E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]$ (1) This is what is confusing me, at this ...
  • 362
3 votes
1 answer
464 views

Why we don't use importance sampling in tabular Q-Learning?

Why don't we use an importance sampling ratio in Q-Learning, even though Q-Learning is an off-policy method? Importance sampling is used to calculate expectation of a random variable by using data ...
7 votes
2 answers
364 views

Why does the state-action value function, defined as an expected value of the reward and state value function, not need to follow a policy?

I often see that the state-action value function is expressed as: $$q_{\pi}(s,a)=\color{red}{\mathbb{E}_{\pi}}[R_{t+1}+\gamma G_{t+1} | S_t=s, A_t = a] = \color{blue}{\mathbb{E}}[R_{t+1}+\gamma v_{\pi}...
4 votes
2 answers
127 views

Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?

In equation 3.17 of Sutton and Barto's book: $$q_*(s, a)=\mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a]$$ $G_{t+1}$ here have been replaced with $v_*(S_{t+1})$, but no reason has ...
2 votes
1 answer
178 views

Are these two definitions of the state-action value function equivalent?

I have been reading the Sutton and Barto textbook and going through David Silvers UCL lecture videos on YouTube and have a question on the equivalence of two forms of the state-action value function ...
2 votes
1 answer
107 views

How are the Bellman optimality equations and minimax related?

Is the philosophy between Bellman equations and minimax the same? Both the algorithms look at the full horizon and take into account potential gains (Bellman) and potential losses (minimax). ...
  • 171
7 votes
2 answers
2k views

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

Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges. It appeals to intuition that, with each ...
4 votes
3 answers
523 views

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

In chapter 4.1 of Sutton's book, the Bellman equation is turned into an update rule by simply changing the indices of it. How is it mathematically justified? I didn't quite get the initiation of why ...
2 votes
2 answers
104 views

Why is there an expectation sign in the Bellman equation?

In chapter 3.5 of Sutton's book, the value function is defined as: Can someone give me some clarification about why there is the expectation sign behind the entire equation? Considering that the ...
  • 23
24 votes
1 answer
11k views

What is the Bellman operator in reinforcement learning?

In mathematics, the word operator can refer to several distinct but related concepts. An operator can be defined as a function between two vector spaces, it can be defined as a function where the ...
  • 35k
3 votes
2 answers
655 views

Apart from the state and state-action value functions, what are other examples of value functions used in RL?

In reinforcement learning, we often define two functions, the state-value function $$V^\pi(s) = \mathbb{E}_{\pi} \left[\sum_{k=0}^{\infty} \gamma^{k}R_{t+k+1} \Bigg| S_t=s \right]$$ and the state-...
  • 35k