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.
103
questions
1
vote
1
answer
71
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\...
- 285
0
votes
1
answer
63
views
Will my Q values keep going up forever?
In Q-learning,the q values can be updated by the bellman equation. What happens with my Q values is that they keep going up forever, in accordance with the more I train. After 10,000 training episodes,...
- 1
4
votes
1
answer
195
views
Why are policy gradient methods more effective in high-dimensional action spaces?
David Silver argues, in his Reinforcement Learning course, that policy-based reinforcement learning (RL) is more effective than value-based RL in high-dimensional action spaces. He points out that the ...
- 143
2
votes
1
answer
76
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 ...
- 133
1
vote
0
answers
24
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
0
answers
52
views
Policy and Value function as a function of Discount
I'm learning MDP's and I'd like to know if I'm doing these exercises correctly:
Consider the following MDP:
The agent starts at the cell marked by $S$. Whenever it enters a cell with a positive ...
- 91
0
votes
0
answers
47
views
How to learn the value function in a two-player game?
In single-player games, the optimal policy can be derived from the state value function v(s):
$$
\pi(s) = \underset{a}{\text{argmin}} \sum_{s'} p(s'|a,s)(c(a) + v(s'))
$$
where c(a) is the cost of ...
- 113
0
votes
1
answer
71
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 ...
- 91
0
votes
0
answers
58
views
Policy and Discount Factor
This question is similar to this question, however it has a different question.
I'm learning MDP's and I'd like to know if I'm doing these exercises correctly:
Consider the following MDP:
Suppose a ...
- 91
0
votes
0
answers
34
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 ...
- 91
0
votes
0
answers
28
views
Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ in terms of $p$ (3.4) and $r$ (3.5) [duplicate]
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 four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ ...
- 91
0
votes
0
answers
32
views
Exercise 3.21 Sutton Barto: Draw or describe the contours of the optimal action-value function for putting, $q_{*}(s, putter)$, for the golf example
I am doing exercise 3.21 in Sutton and Barto. Here's the exercise:
Draw or describe the contours of the optimal action-value function for
putting, $q_{*}(s, putter)$, for the golf example.
Here's ...
- 91
1
vote
2
answers
253
views
Does maximizing the value function and maximizing the state-action value function generate the same optimal policy?
In reinforcement learning, we define the optimal policy $\pi^*$ as the policy that maximizes the value of the state:
$$
\pi_v^*=\underset{\pi}{\operatorname{argmax}} {V_{\pi}(s)}
$$
In Q-learning, we ...
- 193
3
votes
1
answer
139
views
How do we estimate the value of a stochastic policy?
I'm learning about reinforcement learning, particularly policy gradient methods and actor-critic methods. I've noticed that many algortihms use stochastic policies during training (i.e. they select ...
7
votes
2
answers
1k
views
In Value Iteration, why can we initialize the value function arbitrarily?
I have not been able to find a good explanation of this, other than statements that the algorithm is guaranteed to converge with arbitrary choices for initial values in each state. Is this something ...
- 73
0
votes
1
answer
230
views
PPO custom implementation: do metrics like value loss, actor loss and entropy move a certain way?
I'm wondering whether problems with a custom PPO implementation (problem couldn't be made into a gym environment) can be debugged considering how the losses change over time.
In my current experiment, ...
3
votes
1
answer
51
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 ...
- 31
1
vote
0
answers
41
views
Does all GAN's in literature need to satisfy the properties of objective function of initial GAN? [closed]
Consider the following value function of the initial GAN
$V(D, G) = \mathbb{E}_{x \sim p_{data(x)}} [\log D(x)] + \mathbb{E}_{z \sim p_z(z)} [1- \log D(G(z))]$
The min-max game on the value function: $...
- 3,481
0
votes
1
answer
70
views
How is policy iteration capable of improving on a deterministic policy?
Given a policy $\pi$ and the improved version upon it using policy iteration $\pi'$ we have, for $\forall s \in S$, $v_{\pi'}(s)\geq v_{\pi}(s)$.
I think the way we choose $\pi'$ makes it ...
- 519
0
votes
0
answers
24
views
How can you know beforehand that the value of some actions are poor and what the greedy action is?
Sutton-Barto (Section 9.11, page 234)
The algorithms we have considered so far in this chapter have treated all the states
encountered equally, as if they were all equally important. In some cases, ...
- 285
3
votes
1
answer
1k
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 $...
- 33
1
vote
1
answer
126
views
Are these two forms of the state value function the same?
Why are there different forms of the value function in reinforcement learning?
Sutton & Barto (2nd edition, equation 3.14) define the state value function as follows
$$v_{\pi}(s) = \displaystyle\...
- 175
2
votes
1
answer
206
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
228
views
Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?
In Sutton and Barto's book (Reinforcement learning: An introduction. MIT press, 2018), the algorithm "Policy Iteration" is:
Here, $V(s)$ is initialized arbitrarily, meaning that I can ...
- 121
6
votes
1
answer
666
views
When to use the state value function $V(s)$ and when to use the state-action value function $Q(s, a)$?
I saw the difference between value function $V(s)$ and $Q(s, a)$. But when do I use each one? When I coded in Matlab I only used $Q(s, a)$ directly (as I was thinking of a tabular approach). So, when ...
0
votes
0
answers
112
views
What do we actually 'approximate' when dealing with large state spaces in Q-learning?
I realized that my state space is very large in size. I had planned to use tabular Q-learning (Bellman equation to update the $Q(s, a)$ after each action taken). But this 'large space' realization has ...
4
votes
1
answer
76
views
In TD(0) with linear function approximation, why is the gradient of $\hat v(S^{\prime}, \mathbf w)$ wrt parameters $\mathbf w$ not considered?
I am reading these slides. On page 38, the update for the parameters for the linear function approximation of TD(0) is given. I have a doubt regarding this.
The cost function (RMSE) is given on page ...
- 43
3
votes
1
answer
213
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 \...
- 133
5
votes
2
answers
4k
views
When to use Value Iteration vs. Policy Iteration
Both value iteration and policy iteration are General Policy Iteration (GPI) algorithms. However, they differ in the mechanics of their updates. Policy Iteration seeks to first find a completed ...
- 511
0
votes
1
answer
42
views
Discard irrelavant states from a MDP
I came across this question about MDP.
From the look of it, it seems the full MDP is reducible if the discarded state only have 1 way in and out but is it really so if we change the discounted factor? ...
- 49
1
vote
1
answer
1k
views
PPO when does the update happen?
In many places, it says PPO and Actor-Critic methods in general use TD-updates, but in the loss function for PPO, the Value function loss component uses the difference between output of the value ...
- 223
1
vote
1
answer
77
views
What is the intuition behind comparing action values to state values in the policy improvement theorem?
Sutton and Barto, in their book (Reinforcement Learning 2nd Edition) begin the discussion of policy improvement by comparing the action value $q_\pi(s, \pi'(s))$ to the state value $v_\pi(s)$.
What is ...
3
votes
1
answer
162
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) = \...
0
votes
0
answers
90
views
What are the recurrences used for updating state value function in $TD$ and $TD(\lambda)$ learning?
There are two types of value functions in reinforcement learning: State value function $V^{\pi} (s)$, state-action value function $Q^{\pi}(s, a)$.
State value function:
This value tells us how good ...
- 3,481
1
vote
1
answer
943
views
Is there any difference between an objective function and a value function?
I found the usage of both objective function and value function in the same context.
Context #1: In the paper titled Generative Adversarial Nets by Ian J. Goodfellow et al.
We simultaneously train G ...
- 3,481
3
votes
2
answers
747
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
1
vote
1
answer
164
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 ...
- 57
3
votes
1
answer
121
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 ...
- 519
2
votes
1
answer
104
views
Is the existence and uniqueness of the state-value function for $\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$...
- 3,481
1
vote
0
answers
55
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,481
4
votes
1
answer
251
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}\...
- 3,481
0
votes
1
answer
134
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
1
vote
1
answer
424
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 ...
- 19
3
votes
1
answer
93
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 \...
- 33
5
votes
1
answer
638
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
...
- 215
2
votes
1
answer
88
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 ...
user43110
0
votes
1
answer
203
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 ...
- 1,283
3
votes
1
answer
749
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 ...
user43972
1
vote
0
answers
82
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. ...
- 61
2
votes
0
answers
47
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 \...
- 31