Questions tagged [value-functions]

For questions related to the concept of value (or performance, or quality, or utility) function (as defined in reinforcement learning and other AI sub-fields). An example of this type of functions is the Q function (used e.g. in the Q-learning algorithm), also known as the state-action value function, given that $Q: S \times A \rightarrow \mathbb{R}$, where $S$ and $A$ are respectively the set of states and actions of the environment.

Filter by
Sorted by
Tagged with
3
votes
2answers
193 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 ...
1
vote
1answer
13 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 ...
0
votes
0answers
11 views

A2C value function outputs keep increasing

I was implementing the A2C algorithm with as close to baseline setup as possible, and this is the code I came up with. The problem is that even after multiple rechecks, the program isn't showing ...
2
votes
1answer
73 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 ...
2
votes
1answer
53 views

Is existence and uniqueness of state-value function at $\gamma < 1$ theoretical?

Consider the following statement from 4.1 Policy Evaluation of the first edition of Sutton and Barto's book. The existence and uniqueness of $V^{\pi}$ are guaranteed as long as either $\gamma < 1$...
1
vote
0answers
20 views

Is there any thumb rule on the cardinality of state space in order to use the parameterized function to estimate value functions?

Value functions for a given MDP can be learned in at least two ways by experience. The first way (tabular calculation) is generally used in the case of state spaces that are small enough. The second ...
3
votes
1answer
159 views

How is the state-value function expressed as a product of sums?

The state-value function for a given policy $\pi$ is given by $$\begin{align} V^{\pi}(s) &=E_{\pi}\left\{r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\cdots \mid s_{t}=s\right\} \\ &=E_{\pi}\...
0
votes
1answer
41 views

Given a sequence of states followed by the agent, is it possible to find the Q-value for a state-action pair not in this sequence?

Assume you are given a sequence of states followed by the agent, generated by a random policy, $[s_0, s_1, s_2, \dots, s_n]$. Furthermore, assume the MDP is fully observable and time is discrete. Is ...
1
vote
1answer
54 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 ...
3
votes
1answer
39 views

How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?

I am reading Sutton & Bartos's Book "Introduction to reinforcement learning". In this book, the defined the optimal value function as: $$v_*(s) = \max_{\pi} v_\pi(s),$$ for all $s \in \...
5
votes
1answer
85 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 ...
2
votes
1answer
68 views

Why do I get the best policy before Q values converge using DQN?

I have implemented DQN algorithm and wonder why during testing, the best performance is achieved by a policy from about 300 episode, when mean Q values converge at about 800 episode? Mean Q-values ...
0
votes
1answer
57 views

What are the popular approaches to estimating the Q-function?

I need the q-value for my RL training, there are some approaches: Brute-force the action sequence (this won't work for long sequence) Use a classic algorithm to optimise and estimate (this ain't much ...
2
votes
1answer
185 views

What is a “learned policy” in Q-learning?

I am completing an assignment at the moment. One of the assignment questions asks how you identified the learned policy and how you obtained it. The question is a reinforcement learning question, and ...
1
vote
0answers
72 views

How do I learn the value function for a POMDP with a single-step horizon (bandit)?

Consider a POMDP with a finite number of environment states, $|\mathcal{S}| = N$, but the number of belief states is uncountably infinite. The belief state space is the convex hull of an $N$ simplex. ...
2
votes
0answers
27 views

Does there necessarily exist “dominated actions” in a MDP?

In a Markov Decision Process, is it possible that there exists no "dominated action"? I define a dominated action the following way: we say that $(s,a)$ is a dominated action, if $\forall \...
1
vote
0answers
15 views

How to obtain the policy in the form of a finite-state controller from the value function vectors over the belief space of the POMDP?

I was reading this paper by Hansen. It says the following: A correspondence between vectors and one-step policy choices plays an important role in this interpretation of a policy. Each vector in $\...
1
vote
1answer
84 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
2answers
315 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 ...
1
vote
1answer
36 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 ...
1
vote
0answers
13 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 ...
4
votes
1answer
133 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 ...
3
votes
1answer
111 views

Is the expected value we sample in TD-learning action-value Q or state-value V?

Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, ...
1
vote
1answer
120 views

Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?

Here is David Silver's lecture on that. Look at 9:30 to 10:30. He says that, since it is model-free learning, the environment's dynamics are unknown, so the action-value function $Q$ is used. But ...
2
votes
1answer
76 views

When learning off-policy with multi-step returns, why do we use the current behaviour policy in importance sampling?

When learning off-policy with multi-step returns, we want to update the value of $Q(s_1, a_1)$ using rewards from the trajectory $\tau = (s_1, a_1, r_1, s_2, a_2, r_2, ..., s_n, a_n, r_n, s_n+1)$. We ...
3
votes
0answers
144 views

In Soft Actor Critic, why is the action sampled from current policy instead of replay buffer on value function update?

While reading the original paper of Soft Actor Critic, I came across on page number 5, under equation (5) and (6) $$ J_{V}(\psi)=\mathbb{E}_{\mathbf{s}_{t} \sim \mathcal{D}}\left[\frac{1}{2}\left(V_{\...
0
votes
0answers
41 views

Is using Bellman Optimality Equation to evaluate states a bad idea when episode number is low?

I am trying to build an RL agent that interacts with an environment, a 2D grid of dimensions 20*10: each (i,j) square in the grid gives out some reward to the agent when it visits that square. Each ...
1
vote
1answer
61 views

In the definition of the state-action value function, what is the random variable we take the expectation of?

I know that $$\mathbb{E}[g(X) \mid A] = \sum\limits_{x} g(x) p_{X \mid A}(x)$$ for any random variable $X$. Now, consider the following expression. $$\mathbb{E}_{\pi} \left[ \sum \limits_{k=0}^{\infty}...
3
votes
1answer
64 views

Can we stop training as soon as epsilon is small?

I'm new to reinforcement learning. As it is common in RL, $\epsilon$-greedy search for the behavior/exploration is used. So, at the beginning of the training, $\epsilon$ is high, and therefore a lot ...
3
votes
1answer
104 views

What is wrong with equation 7.3 in Sutton & Barto's book?

Equation 7.3 of Sutton Barto book: $$\text{Equation: } max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi| \le \gamma^nmax_s|V_{t+n-1}(s) - v_\pi(s)| $$ $$\text{where }G_{t:t+n} = R_{t+1} + \gamma R_{t+2}...
1
vote
1answer
184 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 ...
2
votes
0answers
34 views

What's an example of a simple policy but a complex value function?

Hado van Hasselt, a researcher at DeepMind, mentioned in one of his videos (from 7:20 to 8:20) on Youtube (about policy gradient methods) that there are cases when the policy is very simple compared ...
1
vote
1answer
45 views

The are some fundamental learning theories for developing an AI that imitates human behavior

Most if not all AI systems are not to imitate human, but to finally out-perform human. Examples include using AI to play a game, classification problems, auto-driving, and goal-oriented chatbots. ...
2
votes
1answer
397 views

Why is the expected return in Reinforcement Learning (RL) computed as a sum of cumulative rewards?

Why is the expected return in Reinforcement Learning (RL) computed as a sum of cumulative rewards? Would it not make more sense to compute $\mathbb{E}(R \mid s, a)$ (the expected return for taking ...
2
votes
1answer
54 views

Why isn't it wise for us to completely erase our old Q value and replace it with the calculated Q value?

Why isn't it wise for us to completely erase our old Q value and replace it with the calculated Q value? Why can't we forget the learning rate and temporal difference? Here's the update formula.
1
vote
1answer
77 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
90 views

How to express $v_\pi(s)$ in terms of $q_\pi(s,a)$?

This is the exercise 3.18 in Sutton and Barto's book. The task is to express $v_\pi(s)$ using $q_\pi(s,a)$. Looking at the diagram above, the value of $q_\pi(s,a)$ at $s$ for each $a \in A$ we take ...
0
votes
1answer
81 views

How do I know that the DQN has learnt an appropriate Q function?

Is there any sanity check to know whether the Q functions learnt are appropriate in deep Q networks? I know that the Q values for end states should approximate the terminal reward. However, is it ...
3
votes
2answers
156 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 ...
4
votes
2answers
209 views

Why are the value functions sometimes written with capital letters and other times with lower-case letters?

Why are the state-value and action-value functions are sometimes written in small letters and other times in capitals? For instance, why in the Q-learning algorithm (page 131 of Barto and Sutton's ...
3
votes
1answer
248 views

How do we express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$?

The task (exercise 3.13 in the RL book by Sutton and Barto) is to express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$. $q_\pi(s,a)$ is the action-value function, that states how good ...
2
votes
1answer
135 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
115 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 ...
3
votes
1answer
71 views

How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?

Here's the approximated value using weighted importance sampling $$ V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2 $$ Here's the incremental update rule for ...
2
votes
1answer
108 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 ...
0
votes
1answer
120 views

What is the difference between the state transition of an MDP and an action-value?

Let's say we have MDP where we have a state transition matrix. How is this state transition different from action value in reinforcement learning? Is the state transition in MDP stochastic ...
3
votes
1answer
82 views

Do policy independent state and action values exist in reinforcement learning?

The state value function $V(s)$ is defined as the expected return starting in state $s$ and acting according to the current policy $\pi(a|s)$ till the end of the episode. The state-action values $Q(s,...
5
votes
3answers
1k views

What is the target Q-value in DQNs?

I understand that in DQNs, the loss is measured by taking the MSE of outputted Q-values and target Q-values. What does the target Q-values represent? And how is it obtained/calculated by the DQN?
2
votes
1answer
78 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 ...
1
vote
2answers
59 views

Why does the policy $\pi$ affect the Q value?

From my understanding, the policy $\pi$ is basically how the agent acts (i.e. the actions it will take in each state). However, I am confused about the Q value and how it is "affected" by a policy. ...