1
$\begingroup$

Suppose in an Markov Decision Process (MDP), we have transition $(s, a, r, s', a', r', s'', ...)$, learning rate $\alpha$ and discount factor $\lambda$.

The update formula of $TD(0)$: $V(s) \leftarrow (1-\alpha)V(s)+\alpha(r+\gamma V(s'))$

The update formula of Q-learning: $Q(s,a) \leftarrow (1-\alpha)Q(s,a) + \alpha (r + max_a' Q(s',a'))$

If in the MDP applying any action on any state will deterministically lead to another state, should I use Q-learning (off-policy) or $TD(0)$ (on-policy)?

Furthermore, If we use function approximation for both $V(s)$ and $Q(s,a)$, I can imagine that $V(s)$ can directly input the feature representation of the state $s$, while $Q(s,a)$ can input the feature representation of the next state $s'$. If so, you will see the update formula Q-learning will only differ slightly with $TD(0)$: $Q(s') \leftarrow (1-\alpha)Q(s') + \alpha(r+\max_{s''} Q(s''))$.

I see people have applied $TD(0)$ (or $TD(\lambda)$ in many board games with deterministic actions such as Go [1] and BackGammon [2]. Why not Q-learning? What is the difference between the two methods in such case?

Reference

[1] Schraudolph, N. N., Dayan, P., & Sejnowski, T. J. (1994). Temporal difference learning of position evaluation in the game of Go. In Advances in Neural Information Processing Systems (pp. 817-824).

[2] Tesauro, G. (1995). Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3), 58-68.

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that in Q-learning, the Q matrix has dimension (# states x # actions), which can be huge in games such as Go and Backgammon, even considering only actions that are feasible in each state. This renders Q-learning computationally infeasible for these sorts of problems. $\endgroup$
    – jbowman
    Commented Apr 21, 2018 at 19:22
  • $\begingroup$ @jbowman like I said in the original question, if I use function approximation and I let Q(s,a) function take s' as input, where s' is the next state after (s,a), then Q-learning and TD(0) should have the same dimensionality. $\endgroup$
    – czxttkl
    Commented Apr 22, 2018 at 1:51

1 Answer 1

Reset to default
2
$\begingroup$

Whether or not actions are deterministic is not really relevant for your choice of algorithm here.

The first thing to know is that $TD(0)$ (or, more generally, $TD(\lambda)$) is an algorithm that learns state-values $V(s)$, it does not learn state-action-values $Q(s, a)$. $V(s)$ just tells you how "good" it is to be in a certain state under a given policy, it is not sufficient to tell you which action you want to take. It is an algorithm for the policy evaluation or prediction problem, not for the control problem. In Reinforcement Learning, if you want to have an algorithm that can learn to tell you which actions to take, you'll generally want $Q(s, a)$ values.

The only exception to the above paragraph is if you have access to a perfect forward model of the environment. That means that you have a simulator that, given a current state and an action, can tell you what the distribution over successor states will be (or, in your case with determinisim, just a single successor state). This is the case for those board games you mentioned, and in such a case the state-values $V(s)$ will be sufficient information (in combination with your forward model / simulator) to select actions. Note that determinism vs. nondeterminism is not the deciding factor here; having access to a perfect model of the environment is the deciding factor.

$Q$-learning is not the only algorithm for learning $Q(s, a)$ values though. It is a one-step, off-policy algorithm for the control problem. A one-step, on-policy algorithm for the control problem (a "control version" of $TD(0)$) would be $Sarsa$. There is also a version with a $\lambda$ parameter (like $TD(\lambda)$), named $Sarsa(\lambda)$. That would also be an option if you want to learn $Q(s, a)$ values.

The difference between $Q$-learning vs. $Sarsa$ is in off-policy vs. on-policy.

Off-policy algorithms can learn values for a policy that is different from the one that you're using to generate experience. This is useful if, for example, you ultimately want to learn values for a fully greedy agent (one that always selects actions that maximize $Q(s, a)$), but use a non-greedy agent (such as $\epsilon$-greedy) to generate experience. This is where you'd probably want to lean towards $Q$-learning.

On-policy algorithms learn values for the policy that you're also using to generate experience. So, for example, if you're generating experience with an $\epsilon$-greedy strategy with fixed $\epsilon$, you'll learn values for (and optimize a policy) that takes into account that you'll occasionally act randomly. This can, for example, lead to somewhat "safer" behaviour because your agent "knows" that it'll occasionally act randomly, and have to act safely to avoid disaster due to that randomness. This would be useful, for example, if you already care about having good performance during the training process itself (and don't care only about good performance in a separate evaluation period after training).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! Based on your answer, I think the work so-called"TD-gammon" is actually based on SARSA, which estimates $Q(s,a)$ for the current policy but also performs self-play so that the Q-values are constantly changing. Since we have a perfect forward model for back-gammon, $Q(s,a)$ actually becomes a state value $V(s')$, where $s'$ is the next state after $(s,a)$ . Am I right? Is there any reason that we don't see people applying Q-learning on games like Go and Back-Gammon? $\endgroup$
    – czxttkl
    Commented Apr 22, 2018 at 2:11
  • $\begingroup$ @czxttkl I never read the TD-gammon paper in detail, but from a very brief skim I get the impression that they do in fact just use TD, not Sarsa, so they just learn state-values. In order to make moves, they do indeed exploit the fact that they have knowledge of the game rules / a forward model: they simply generate all successor states $s'$, find all the $V(s')$ values for those states, and then select the move leading to the best successor. $\endgroup$
    – Dennis Soemers
    Commented Apr 22, 2018 at 9:00
  • $\begingroup$ As for applying Q-learning straight up in such games, that often doesn't work too well because Q-learning is an algorithm for single-agent problems, not for multi-agent problems. It does not inherently deal well with the whole minimax structure in games, where there are opponents selecting actions to minimize your value. Different forms of Reinforcement Learning (combined with tree search) have been used though, see the AlphaGo papers for example. $\endgroup$
    – Dennis Soemers
    Commented Apr 22, 2018 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.