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
1answer
45 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)$, ...
4
votes
2answers
106 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} \...
5
votes
0answers
140 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
1answer
34 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
1answer
57 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 ...
2
votes
1answer
85 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
2answers
124 views

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

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

Equation not satisfied in Policy Iteration Algorithm

In equation 4.9 of Sutton and Barto's book on page 79, we have(for policy iteration algo): $\pi ^{'}(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]$ where $\pi$ is the previous policy ...
4
votes
2answers
107 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
1answer
95 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 ...
1
vote
1answer
28 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). ...
4
votes
2answers
201 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 ...
2
votes
2answers
94 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
2answers
48 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 ...
13
votes
1answer
4k 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 ...
6
votes
1answer
185 views

Why do Bellman equations indirectly create a policy?

I was watching a lecture on policy gradients and Bellman equations. And they say that a Bellman equation indirectly creates a policy, while the policy gradient directly learns a policy. Why is this?