13
votes
Accepted
What algorithms are considered reinforcement learning algorithms?
The dynamic programming algorithms (like policy iteration and value iteration) are often presented in the context of reinforcement learning (in particular, in the book Reinforcement Learning: An ...
- 39.1k
6
votes
Accepted
Why does TD Learning require Markovian domains?
The Markov assumption is used when deriving the Bellman equation for state values:
$$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
One requirement for this equation to hold is that ...
- 28.9k
4
votes
What algorithms are considered reinforcement learning algorithms?
In Reinforcement Learning: An Introduction the authors suggest that the topic of reinforcement learning covers analysis and solutions to problems that can be framed in this way:
Reinforcement ...
- 28.9k
4
votes
Accepted
Why is update rule of the value function different in policy evaluation and policy iteration?
Yes, the two update equations are equivalent. As an aside, technically the equation you give is not the Bellman equation, but the update step re-written as an equation - in the Bellman equation ...
- 28.9k
3
votes
Accepted
Do we need the transition probability function when calculating the importance sampling ratio?
There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?
It is not needed ...
- 28.9k
3
votes
Accepted
Should we feed a greater fraction of terminal states to the value network so that their values are learned first?
The basis of Q-learning is recursive (similar to dynamic programming), where only the absolute value of the terminal state is known.
This may be true in some environments. Many environments do not ...
- 28.9k
2
votes
Accepted
What are the common techniques one could use to deal with collisions in a transposition table?
The term you're looking for is "replacement schemes". As far as I'm aware, the primary reference on this is still Replacement Schemes for Transposition Tables, although it is a fairly old paper from ...
- 9,914
2
votes
Accepted
Is it possible to retrieve the optimal policy from the state value function?
You can obtain the optimal policy from the optimal state value function if you also have the state transition and reward model for the environment $p(s',r|s,a)$ - the probability of receiving reward $...
- 28.9k
2
votes
Accepted
How do we get from conditional expectation on both state and action to only state in the proof of the Policy Improvement Theorem?
I don't understand how did we get rid of the condition $A_{t}=\pi'(s)$.
We don't really, it is just moved into the subscript $\pi'$ in $\mathbb{E}_{\pi'}[]$ - it means the same thing here, that the ...
- 28.9k
2
votes
Accepted
Are policy and value iteration used only in grid world like scenarios?
Policy and value iteration both require you to, for each possible transition and each corresponding possible reward at each state, compute a statistic of $r + \gamma V(s')$. In order for this to be ...
- 1,106
2
votes
Accepted
Interpretation of the Dynamic Time Warping (DTW) graph
The graph plots two things:
the optimal warping path;
the accumulated cost matrix (which looks like a heat map).
To interpret the graph, suppose we draw some other path from bottom left to top right....
- 61
1
vote
Consequence of Dvoretzky Stochastic Approximation Theorem
The Dvoretzky Stochastic Approximation Theorem is a result in the field of stochastic approximation theory, which provides insights into the convergence properties of certain iterative algorithms used ...
- 11
1
vote
How are these two versions of the Bellman optimality equation related?
My guess is that $r(s,a)$ is the constant so it can be moved out of the summation, leaving $r(s,a)\sum_{s'}P^{a}_{ss'} = r(s,a)$
Yes, this is the case. More specifically:
$r(s,a)$ is the expected ...
- 28.9k
1
vote
Is there a notion of exploration-exploitation tradeoff in dynamic programming (or model-based RL)?
I think there is an implicit notion of it in dynamic programming; say, if you have to make some sort of search over a subset of a state space and you are deciding whether to use BFS, breath first ...
- 121
1
vote
Accepted
How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?
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 ...
- 241
1
vote
Accepted
Bellman optimality equation in semi Markov decision process
The core problem here is state representation, not estimating return due to delayed response to actions on the original state representation (which is no longer complete for the new problem). If you ...
- 28.9k
1
vote
If the transition model is available, why would we use sample-based algorithms?
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 ...
- 1,106
1
vote
What algorithms are considered reinforcement learning algorithms?
It seems that another rather controversial point is about the inclusion of evolutionary algorithms as Reinforcement Learning ones.
Sutton & Barto do not. They argue that
And also:
Other people ...
- 221
1
vote
Should we feed a greater fraction of terminal states to the value network so that their values are learned first?
If you have enough domain knowledge to be able to reliably, intentionally reach those terminal states often when generating experience, yeah, that could help.
Generally, the assumption in ...
- 9,914
Only top scored, non community-wiki answers of a minimum length are eligible