12

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 Introduction by Barto and Sutton) because they are very related to reinforcement learning algorithms, like $Q$-learning. They are all based on the assumption that ...


6

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 $p(r,s'|s,a)$ is consistent. The current state $s$ is a key argument of that function. There is no adjustment for history of previous states, actions or ...


4

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 learning, like many topics whose names end with “ing,” such as machine learning and mountaineering, is simultaneously a problem, a class of solution methods that ...


4

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 instead of $v_{k+1}(s)$ or $v_{k}(s)$ (showing iterations of approximate value functions), you would have $v_{\pi}(s)$ (representing the true value of a state under ...


3

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 for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state ...


3

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 have a terminal state, they are continuous. Your statement may be true for instance in a board game environment where the goal is to win, but it is false for e.g. ...


2

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 1994. I'll very briefly summarize the seven different schemes listed in this paper, but full text of the paper is also freely available and contains more info: ...


2

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 $r$ and arriving in state $s'$ when starting in state $s$ and taking action $a$. This looks like: $$\pi^*(s) = \text{argmax}_a [\sum_{s',r} p(s',r|s,a)(r + \...


2

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 next action is chosen according to the modified policy $\pi'$. Moving the condition around is part of the proof's strategy, which eventually expresses the ...


2

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 tractable, you need for there to be at most finitely many states, actions, possible rewards, and possible transitions at each state. You also need to know the ...


1

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 reward after taking action $a$ in state $s$. Reward may depend on the state arrived in, $s'$, but that is ignored in the equations. Reward may vary randomly, but ...


1

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 search, or DFS, depth first search, you are at least implicitly thinking on the best way to explore/exploit the state space. As for model based RL, yes. There is ...


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

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 fix that, then you can solve your problem as a normal MDP, and base calculations on single timesteps. This allows you to continue using dynamic programming to ...


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.


1

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 related with the subject, as the HSE University that offers a course in Coursera, Maxim Lapan , or P. Palanisamy (both Packt's authors) include them into the ...


1

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 Reinforcement Learning is no domain knowledge other than the assumption that we're in a Markov Decision Process. This means we start learning from scratch, and before ...


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