# Tag Info

## Hot answers tagged bellman-equations

4

It seems that you are getting confused between the definition of a Q-value and the update rule used to obtain these Q-values. Remember that to simply obtain an optimal Q-value for a given state-action pair we can evaluate $$Q(s, a) = r + \gamma \max_{a'} Q(s', a)\;;$$ where $s'$ is the state we transitioned into (note that this only holds when obtaining the ...

3

Your equations all look correct to me. It is not possible to solve the linear equation for state values in the vector $V$ without knowing the policy. There are ways of working with MDPs, through sampling of actions, state transitions and rewards, where it is possible to estimate value functions without knowing either $\pi(a|s)$ or $P^{a}_{ss'}$. For instance,...

3

Based on this and this resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton & Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there ...

3

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations. Policy iteration In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form \pi(a|... 2 The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} whereU$and$Vare two value functions, follows from the definition of Bellman policy operator (at slide 16) \begin{align} T^{\pi} V(s) &\triangleq R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime}... 2 For a Markov Decision Process(\mathcal{S}, \mathcal{A}, P, R)$(here$P(s, s') = \mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a))$;, let us define the value of being in a certain state. That is, $$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) | S_t =s\right].$$ That is, the value of being in state$s$... 2 There's not much to derive here it's simply a definition of Bellman operator, it comes from Bellman equation. If you're wondering why \begin{equation} Q^{\pi} = (I - \gamma P^{\pi})^{-1}r \tag{1} \end{equation} they state that$Q^{\pi}$is a fixed point which means if you apply Bellman operator to it you get the same value \begin{equation} T^{\pi}(Q^{\pi}) = ... 2 Reinforcement Learning is really fun because the agent will find any bug in your implementation and will exploit it. >>> take_left(0) 0 >>> take_left(1) -4 The agent figured out your bug with negative values and exploits negative indexing to get to the target faster. 2 The Bellman equation in RL is usually defined $$v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)\left[r + v_\pi(s')\right] = \mathbb{E}_{s' \sim p, a \sim \pi}\left[r(s, a) + v_\pi(s')\right] \; .$$ The way you have written it is correct, but I just thought I would point this out. Regardless, your intuition is correct in that it expresses a recursive ... 1 Since my question arose from my incomprehension of$v(S_{t + 1})$and since I got clarifications on it by Neil Slater, I thought I'd go back to this question and try to answer it again. So I'm assuming that$v(S_{t + 1})$is a random variable made by the composition of the state-value function$v$and the random variable$S_{t + 1}$. Since$v(s) = \mathbb{E}[...

1

Wow, that's a really confusing example, if I were you I would check out some other RL resources. I wouldn't consider h being the last step and h-1 being the previous step. In terms of steps of iterations of the dynamic programming algorithm, h is actually the first step, h-1 the next step and so on. Viewing it in these terms it makes sense that the Value of ...

1

What am I missing here? You are not missing anything mathematically. Potentially what you are missing is that the discount factor $\gamma$, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any ...

1

I will refer to $\mathcal T^{\pi}$as $\mathcal T$ and $P^{\pi}$ as $P$ for notational simplicity \begin{align} (\mathcal{T})^{n+1} Q &= \mathcal{T}(\mathcal{T}(...(\mathcal{T}(Q))))\\ &= r + \gamma P(r + \gamma P(...(r + \gamma P Q)))\\ &= r + r\sum_{i=1}^{n} \gamma^i P^i + \gamma^{n+1} P^{n+1} Q \end{align} \begin{align} \mathcal{T}_{\lambda}Q &...

1

Just to add to the previous answer some more background and intuition. The background of Bellman equation comes from optimal control theory of dynamic systems of form (in discrete time case) \begin{equation} s_{k+1} = f_d(s_k, a_k) \tag{1} \end{equation} where $s_k$ represents state at time $k$ and $a_k$ action at time $k$. The goal is to optimize multistage ...

1

In general they are not the same and that should be clear as to why -- mathematically you are conditioning on an extra random variable being known in the state-action value function. You have the correct relationship between them, but I think your understanding of the two may be slightly off. The state-action value function is a function of both $s$ and $a$ ...

1

Theorem The optimal state-action value function of $r'(s, a) \triangleq r(s, a) + c$, for $c \in \mathbb{R}$, would be \begin{align} q_*(s, a) + c + c\gamma + c \gamma^2 + c \gamma^3 + \dots &=q_*(s, a) + c \left( 1 + \gamma + \gamma^2 + \gamma^3 + \dots \right) \\ &= q_*(s, a) + c \left( \sum_{k=0}^{\infty} \gamma^{k} \right) \\ &=q_*(s, a) + c\...

1

A full Bellman update can be intractable. For instance, if your state space or action space are continuous, the full Bellman update is intractable. You can try to solve this by discretizing, but if your state space is large this will also be intractable.

Only top voted, non community-wiki answers of a minimum length are eligible