I am studying Chapter 36 Thompson Sampling of the book Bandit Algorithms by Lattimore and Szepesvari. The authors present two equivalent formulations of Thompson Sampling on page 460, and I am having trouble seeing why they are equivalent.

Let $(\mathcal{E},\mathcal{G},P_0)$ be a probability space, where $\mathcal{E}$ is a collection of bandit environments, $\mathcal{G}$ is a $\sigma$-algebra over $\mathcal{E}$, and $P_0$ is the prior distribution. The mean of the $i$th arm in bandit $\nu\in\mathcal{E}$ is denoted by $\mu_i(\nu)$. Let $A_t$ denote the action in round $t$, and $X_t$ the reward in round $t$. Let $\mathcal{F}_t=\sigma(A_1,X_1,...,A_{t-1},X_{t-1})$. The two formulations are as follows.

  1. Select an arm according to the posterior probability that the arm is optimal, that is, Thompson Sampling is the policy $\pi=(\pi_t)_{t=1}^{\infty}$ with $$ \pi_t(a\mid a_1,x_1,...,a_{t-1},x_{t-1}) = Q(V_a\mid a_1,x_1,...,a_{t-1},x_{t-1}), $$ where $V_a=\{\nu\in\mathcal{E}:a=\text{argmax}_i\mu_i(\nu)\}$, and $Q$ is the posterior distribution.
  2. First sample $\nu_t\sim Q(\cdot\mid \mathcal{F}_{t-1})$, then let $$ A_t=\text{argmax}_{i\in[k]}\mu_i(\nu_t). $$

Moreover, on page 461, the authors further note that $A_t$ satisfies $$ \mathbb{P}(A^*=\cdot\mid \mathcal{F}_{t-1}) = \mathbb{P}(A_t=\cdot\mid \mathcal{F}_{t-1}), \tag{$*$} $$ where the authors define $A^*$ by $A^*=\text{argmax}_{i\in[k]}\mu_i$. (I think the authors are being sketchy here. A more rigorous definition should be as follows. For each $\nu\in\mathcal{E}$, define $A(\nu)=\text{argmax}_{i\in[k]}\mu_i(\nu)$. Let $V$ be a random variable with law $P_0$, and define $A^*=A(V)$.)

My question: How to show (using a measure-theoretic argument) that the two formulations are equivalent and that $(*)$ holds?



Your Answer

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