14 votes
Accepted

What algorithms are considered reinforcement learning algorithms?

The dynamic programming (DP) algorithms like policy iteration (PI) and value iteration (VI) are often presented in the context of reinforcement learning (in particular, in the book Reinforcement ...
nbro's user avatar
  • 40.6k
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
Neil Slater's user avatar
  • 32.1k
4 votes
Accepted

Where does the TD formula for tic-tac-toe in Sutton & Barto come from?

The equation (1) you mentioned is a simplified form of the temporal difference TD(0) update rule, specifically for the case of episodic tasks where there's no discounting $\gamma$ and the only reward ...
cinch's user avatar
  • 2,307
4 votes

What is the relation between Dynamic Programming and Reinforcement Learning?

Dynamic programming is an algorithm paradigm (i.e. a way to design algorithms) that can be applied to many problem domains, not just Markov decision processes (MDPs), as long as they satisfy certain ...
nbro's user avatar
  • 40.6k
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
Neil Slater's user avatar
  • 32.1k
2 votes
Accepted

Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$?

To fully understand generically the transition dynamics from state $x$ to state $x′$ in terms of action values without state values involvement, we need to evaluate all possible combinations of ...
cinch's user avatar
  • 2,307
2 votes
Accepted

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?

Like it's explained in the image's caption, DP techniques are based on the idea that you can reuse the solution to subproblems, so it assumes that you can break down the original problem into ...
nbro's user avatar
  • 40.6k
2 votes

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?

Exhaustive search is just trial and error for the specified problem which has a fixed start node X and a fixed end node Y, thus every possible travel route from X to Y has to be evaluated ...
cinch's user avatar
  • 2,307
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 ...
Dennis Soemers's user avatar
  • 10.3k
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 $...
Neil Slater's user avatar
  • 32.1k
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
harwiltz's user avatar
  • 1,136
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....
bigdatadan's user avatar
2 votes

What is the relation between Dynamic Programming and Reinforcement Learning?

In the comment section you already knew that policy iteration and value iteration are reinforcement learning (RL) application of Dynamic Programming. To further address your remaining question ...
cinch's user avatar
  • 2,307
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 ...
mathewgomas's user avatar
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
João Schapke's user avatar
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 ...
James's user avatar
  • 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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
harwiltz's user avatar
  • 1,136
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 ...
Hermes Morales's user avatar
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 ...
Dennis Soemers's user avatar
  • 10.3k

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