Suppose that, for every state $s$, there is a set of actions $\mathcal{A}(s)$ that can be chosen in that state.

Let $Q(s, a)$ denote the expected utility of choosing action $a \in \mathcal{A}(s)$ in state $s$.

Let the agent choose an action according to the probability that it maximizes $Q(s, a)$. This strategy is called Thompson sampling. That is, for each action $a \in \mathcal{A}(s)$, sample $Q(s, a)$ and then choose the action with the greatest sampled $Q$ value:

$$ \hat{a} = \arg\max_{a \in \mathcal{A}(s)} q(s, a) $$

where $\hat{a}$ denotes the chosen action and $q$ denotes a sampled $Q$ value.

After receiving a reward $r$ and transitioning to a state $s'$, update the $Q(s, a)$ distribution using the following learned value:

$$ p = r + \gamma \max_{a' \in \mathcal{A}(s')} q(s', a') $$

where the $q$ are again sampled $Q$ values, and $\gamma \in [0, 1]$ is the discount factor. In other words, add $p$ to the set of samples $P$ which are used to estimate the distribution $Q(s, a)$. Assuming the rewards are normally distributed, we can use the t-distribution to obtain the distribution for $Q$:

$$ Q = \bar{p} + \frac{s_p}{\sqrt{\lvert P \rvert}} t $$

where $\bar{p}$ and $s_p$ are the sample mean and sample variance of the collected samples $P$. $t$ is a random variable drawn from a t-distribution, which has a bell curve shape.

Naturally, as more and more samples are collected in $P$ (for state $s$ and action $a$), this distribution will become more sharply peaked around the true expected value, assuming the variance is well-defined. However, before this happens, there is "room" for the distribution to take on a range of values, thus accommodating exploration when the sample size is small.

Letting the $Q(s, a)$ be distributions rather than point estimates, and taking samples from these distributions, seems to solve the exploration-exploitation dilemma in a natural way. No artificial, external "exploration rate" parameter is needed.

Is this the right way to extend Q-learning to a Bayesian setting? Does it have the same optimality properties that Thompson sampling has for the multi-armed bandit problem?

  • 1
    $\begingroup$ You can't let $Q(s,a)$ be a distribution, because it has to be an expected value in order to be maximizable. I think you're confusing a single instance of the utility of choosing $a$ in state $s$ with the expected value of same. $\endgroup$ – jbowman Aug 31 '16 at 0:25
  • $\begingroup$ @jbowman I mean to treat $Q(s, a)$ as a distribution of Q values, which are themselves expected utilities. Perhaps better notation might make this clearer: $Q(s, a)$ is sampled from $\mathcal{Q}(s, a)$. $\mathcal{Q}(s, a)$ is a distribution of expected utilities, just as the expression containing a $t$ value drawn from a t-distribution is a distribution of expected values for the Gaussian distribution. $\endgroup$ – user76284 Aug 31 '16 at 0:31
  • 4
    $\begingroup$ Did you read the Dearden paper with exactly the same name as your question? $\endgroup$ – Neil G Sep 15 '16 at 19:44
  • 1
    $\begingroup$ @NeilG - The definition in the second line is that it is an expected utility. As such, it can't be a distribution. The notation in the question is actually pretty sloppy, though; we have "sample $Q(s,a)$", which makes no sense if $Q(s,a)$ is an expected utility, and more of the same. Certainly the observed utilities, say $q(s,a)$, can have a distribution, but they are observed utilities, not distributions themselves. $\endgroup$ – jbowman Sep 16 '16 at 17:09
  • 1
    $\begingroup$ @jbowman Q values can be distributions. This is what Dearden did in his paper. (Carlos got close, but his update is not as good and his use of the T-distribution doesn't make sense to me.) $\endgroup$ – Neil G Sep 16 '16 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.