Thompson Sampling for Parameterized Markov Decision Processes with Uninformative Actions

Decision-making in this paper be summarized as a parameterized Markov decision process (PMDP), which consists of a finite set of possible states $\mathcal{S}$, a finite set of possible actions or controls $\mathcal{A}$, and a finite set of parameters $\Theta$ (e.g. hypotheses) that specify both the reward and the state distribution. Specifically, given a control $a_{t}\in\mathcal{A}$ applied at time $t$ in state $s_{t}\in\mathcal{S}$, and a parameter $\theta\in\Theta$, the reward and the next state are sampled according to

We also define the reward function as $r_{\theta}\!\left(s,a\right)\coloneqq\operatorname{\mathbb{E}}_{\theta}\!\left[R|s,a\right]=\int rf_{\theta}(r|s,a)\,\mathrm{d}r$, which is assumed to be uniformly bounded on $\mathcal{S}\times\mathcal{A}$.

An admissible policy $\mu$ is defined as a sequence of mappings $\left\{\,\mu_{t}\,:\,t\geq 0\,\right\}$, where $\mu_{t}(\mathscr{H}_{t})\mapsto\mathscr{P}(\mathcal{A})$ maps the history of information observed up to time $t$, $\mathscr{H}_{t}=\left\{S_{0},A_{0},R_{0},\dots S_{t-1},A_{t-1},\dots R_{t-1},S_{t}\right\}$, to a probabilitity distribution over the action space, and $\Pi$ be the set of all admissible policies. On the other hand, a Markov policy is a sequence of mappings $\mu_{t}:\mathcal{S}\to\mathcal{A}$; it is further a stationary policy if $\mu_{0}=\mu_{1}=\dots$. Let $\Pi_{S}$ denote the set of all stationary policies. Given a fixed parameter $\theta\in\Theta$, the goal is to maximize over all $\mu\in\Pi$, the long-run expected average reward starting from an initial state $S_{0}=s_{0}$, given as

in which the expectation is computed with respect to $p_{\theta}$ and $A_{t}$ are sampled according to $\mu$. We assume that an optimal policy $\mu_{\theta}^{*}$ exists, which must necessarily be a stationary Markov policy. Furthermore, the state process $\mathscr{S}_{\theta}=\left\{\,S_{t}\,:\,t\geq 0\,\right\}$ induced by $\mu_{\theta}^{*}$ constitutes a time-homogeneous Markov chain, and we assume that

The decision maker accounts for uncertainty in $\theta\in\Theta$ by modeling it as a random variable $\Theta_{t}$ in each decision epoch. Starting with prior distribution $\pi_{0}(\theta)\coloneqq\operatorname{\mathbb{P}}\!\left(\Theta_{0}=\theta\,|\,\mathscr{H}_{0}\right)$, and given history $\mathscr{H}_{t}$, the decision maker updates his belief about $\theta$ by computing the posterior distribution using Bayes’ theorem:

where

is the likelihood. Note that $\pi_{t}(\theta)$ is a function of $\mathscr{H}_{t}$ and is therefore a random variable.

The agent selects controls that are consistent with the learned belief $\pi_{t}$ by following the Thompson sampling algorithm. Formally, this corresponds to an admissible (e.g. history-dependent) policy $\tau$ defined in Algorithm 1.

Intuitively, the posterior update (2) should only improve upon the decision maker’s belief about $\theta$ when $f_{\theta}(\cdot\,|\,s,a)\,p_{\theta}(\cdot\,|\,s,a)$ is distinguishable for different values of $\theta$. To see this, we can restate (2) as

from which we can see that $\pi_{t+1}(\theta)=\pi_{t}(\theta)$ precisely when the ratio of the two likelihoods does not change. Conceptually, the existence of such uninformative state-action pairs $(s,a)$ can significantly “stall” the posterior updates and prevent the decision maker from learning the correct PMDP parameters. On the other hand, recent analysis of posterior convergence [20] in general PMDPs precludes such scenarios, by imposing rather strong assumptions on the problem structure that do not always hold in practice. In the following section, we will formalize the notion of an uninformative action and provide an alternative and complementary set of assumptions that still provide an asymptotically optimal regret bound.

In order to assess the convergence speed of $\pi_{t}$ more precisely, it is necessary to quantify the magnitude of the posterior update. In particular, we define $\nu_{\theta}(s,a)$ as the joint probability distribution specified by $f_{\theta}(\cdot\,|\,s,a)\,p_{\theta}(\cdot\,|\,s,a)$ and the KL-divergence

We require that $\nu_{\vartheta}(s,a)$ is absolutely continuous with respect to $\nu_{\theta}(s,a)$, so that the above quantity is finite.

Formalizing the above intuition, an action $a\in\mathcal{A}$ is called informative in state $s\in\mathcal{S}$ if, for any two distinct $\theta,\vartheta\in\Theta$,

Finally, to ensure that the posterior belief converges at the optimal asymptotic rate, it is necessary that the Markov chain induced by Thompson sampling eventually visits an informative state a positive fraction of the time. One way to guarantee this is to ensure that the induced Markov chain under Thompson sampling mixes with respect to the special state $s^{*}$, which is now known to be informative. More formally, define $\mathcal{I}(s)\subseteq\mathcal{A}$ as the set of controls that are informative in state $s$, and the following random variables for every $\mu\in\Pi$ and $s\in\mathcal{S}$:

Finally, for each $s\in\mathcal{S}$, we define $\mathcal{A}^{*}(s)\coloneqq\left\{\,a\in\mathcal{A}\,:\,a=\mu_{\theta}^{*}(s)\mbox{ for some }\theta\in\Theta\,\right\}$. We then define $\Pi_{C}\subset\Pi$ to be the set of policies $\mu$ for which $\mu(s)\in\mathcal{A}^{*}(s)$ holds for all $s\in\mathcal{S}$, e.g. the set of policies whose controls are consistent with respect to the policy set $\left\{\,\mu_{\theta}^{*}\,:\,\theta\in\Theta\,\right\}$.

One way to interpret Assumptions 2 and 3 is to define another policy class $\Pi_{*}\subseteq\Pi$, consisting of all policies $\mu\in\Pi$ for which $\operatorname{\mathbb{P}}\!\left(\mu(s^{*})\in\mathcal{I}(s^{*})\right)=1$. Clearly, $\Pi_{C}\subset\Pi_{*}$ according to Assumption 2, and $\mu_{\theta}^{*}\in\Pi_{C}$ by construction. Furthermore, by the design of Thompson sampling (Algorithm 1), we can also conclude that $\tau\in\Pi_{C}$ (although $\tau\not\in\Pi_{S}$). Finally, Assumption 3 requires that $I^{\mu}(t;s^{*})\geq I^{\bar{\mu}}(t;s^{*})$ for all ${\mu}\in\Pi_{C}$, including $\tau$. These facts are summarized conceptually in Fig. 1. Note that $\bar{\mu}$ can be any policy in the shaded region for which the induced Markov chain is ergodic. As illustrated later in our examples, this policy also often lies in $\Pi_{*}$, but this is not required under our assumptions in general.

In the next section, we will prove that Assumptions 1-3 are sufficient to achieve asymptotically optimal regret bounds for Thompson sampling with uninformative actions. However, these assumptions are not in general necessary. To see this, suppose Assumption 3 is relaxed by defining a secondary state $s^{\prime}\in\mathcal{S}$ instead of $s^{*}$, that need not satisfy Assumption 2. Now, if we further assume that there is a non-zero probability of visiting $s^{*}$ between successive visits to $s^{\prime}$ under any policy in $\Pi_{C}$, then states $s^{\prime}$ and $s^{*}$ belong in the same communicating class, and the same convergence guarantees also extend to this setting. This generalization would allow us to establish convergence guarantees for learning the service rate parameters in the examples of the following paragraph.

We now provide several important classes of stochastic control problems that satisfy the required assumptions in this paper. Please note, however, that these examples do not satisfy the stronger assumption on the KL-divergence in [20], and thus the analysis in that paper cannot be applied to them.

The main theoretical result of this paper establishes that Thompson sampling with uninformative actions achieves asymptotically optimal learning rates (as measured by expected posterior probability of sampling the incorrect parameter) and regret. Here, we sketch out the main reasoning necessary to establish both results, and provide formal proofs in the following sections.

First, it is necessary to understand how fast the time-homogeneous Markov chain induced by the policy $\bar{\mu}$ mixes. In the following section, it will be shown that the Markov chain induced by the policy $\bar{\mu}$ mixes at an exponential (e.g. geometric) rate, and so Assumption 3 ensures that the special state $s^{*}$ will be visited at a linear rate asymptotically.

By making use of Proposition 1, we then prove that the posterior error converges to zero exponentially fast under our more general assumptions.

The following regret result follows immediately from Theorem 2 proved above, Assumption 1, and Theorem 5 in [20].

We first cite the following result.

Let $\mathscr{S}^{\bar{\mu}}=\left\{\,S_{t}^{\bar{\mu}}\,:\,t\geq 0\,\right\}$ denote the ergodic Markov chain induced by policy $\bar{\mu}$ specified in Assumption 3. First, Assumption 2 states that $\mu_{\theta}^{*}(s^{*})$ is an informative action for every $\theta\in\Theta$. Since Thompson sampling (randomly) selects one of the optimal policies $\mu_{\Theta_{t}}^{*}$ in each decision epoch, actions selected by Thompson sampling upon each visit to state $s^{*}$ must also be informative and thus $I^{\tau}(t)\geq I^{\tau}(t;s^{*})$. By replacing the abstract policy $\mu$ with Thompson sampling in Assumption 3, we have $I^{\tau}(t;s^{*})\geq I^{\bar{\mu}}(t;s^{*})$ for all $t\geq 0$, or in other words:

which hold for all $\eta>0$. Therefore, it remains to bound the rightmost quantity.

To this end, let $R(t)=I^{\bar{\mu}}(t;s^{*})/t$. By Assumption 3, $\mathscr{S}^{\bar{\mu}}$ is time-homogeneous and ergodic, and hence a limiting distribution exists such that $\operatorname{\mathbb{E}}_{\theta}\!\left[R(t)\right]\rightarrow r$ as $t\to\infty$ for some $r\in(0,1)$. More precisely, for each $\nu>0$ there exists $N\in\mathbb{N}$ (dependent on $\nu$) such that $\left\lvert\operatorname{\mathbb{E}}_{\theta}\!\left[R(t)\right]-r\right\rvert<\nu$ for $t\geq N$, in which case:

Now, choosing any $\eta\in(0,r)$ and substituting $\nu=\frac{r-\eta}{2}$, we obtain:

which is valid for all $t\geq N_{1}$ where $N_{1}\in\mathbb{N}$. Finally, we apply Proposition 4 by setting $Y_{i}=\mathbbm{1}\!\left\{S_{i}^{\bar{\mu}}=s^{*}\right\}$, $C_{t}=I^{\bar{\mu}}(t;s^{*})$, and $\|f\|=1$, so that there exists $N_{2}\in\mathbb{N}$ and $\delta,\lambda>0$ dependent on $\eta$ and $\theta$ such that

Therefore, by setting $N_{\theta}=\max\left\{N_{1},N_{2}\right\}$, we have found $\delta_{\theta},\lambda_{\theta}>0$ and $\eta_{\theta}\in(0,1)$ such that

This completes the proof. $\blacksquare$

The proof begins in an identical manner to [20] but diverges after the second paragraph. We begin by writing $\pi_{t}(\theta)$ as:

where $c_{\vartheta}\coloneqq\pi_{0}(\vartheta)/\pi_{0}(\theta)$, and where:

and where the processes $\left\{\,S_{t}\,:\,t\geq 0\,\right\}$ and $\left\{\,A_{t}\,:\,t\geq 0\,\right\}$ are understood to evolve under Thompson sampling.

We define the processes $\mathscr{Z}^{\vartheta}=\left\{\,Z_{t}^{\vartheta}\,:\,t\geq 0\,\right\}$ as

and for convenience, the filtration $\mathscr{F}=\left\{\,\mathscr{F}_{t}\,:\,t\geq 0\,\right\}$ as the sequence of sigma algebras $\mathscr{F}_{t}\coloneqq\sigma(\mathscr{H}_{t},A_{t})$., e.g, by concatenating $A_{t}$ to $\mathscr{H}_{t}$. We can now separate $\mathscr{Z}^{\vartheta}$ into a martingale and a predictable process using the Doob Decomposition theorem [22]:

where $\mathscr{M}^{\vartheta}=\left\{\,M_{t}^{\vartheta}\,:\,t\geq 0\,\right\}$ is an $\mathscr{F}_{t}$-martingale under $\operatorname{\mathbb{P}}_{\theta}$ by construction, with $M_{0}^{\vartheta}=0$ since $\Lambda_{0}^{\vartheta}=1$.

Since $A_{i}$ is $\mathscr{F}_{i}$-measurable, for every $i\in\left\{1,2\dots t\right\}$, $\vartheta\in\Theta$ with $\vartheta\not=\theta$, we have:

where the constants $\varepsilon(\theta,\vartheta)>0$ follow from the definition of an informative action. As a result, $\left\{\,P_{t}^{\vartheta}\,:\,t\geq 0\,\right\}$ is a non-decreasing process with $P_{0}^{\vartheta}=0$ and:

where $I(t)\coloneqq I^{\tau}(t)$.

We now take expectation of the posterior in (IV-B):

For $\eta\in(0,1)$, we define the event $\mathcal{G}_{t}^{\eta}=\{I(t)\geq\eta t\}$ and condition as follows:

For $\delta\in(0,\varepsilon\eta)$, we define the event $\mathcal{B}_{t}(\delta)\coloneqq\bigcap_{\vartheta\not=\theta}\left\{\left\lvert M_{t}^{\vartheta}\right\rvert\leq\delta t\right\}$ and the scalar $d_{\theta}\coloneqq\frac{1-\pi_{0}(\theta)}{\pi_{0}(\theta)}$. Then:

which yields the lower bound

Next, we apply DeMorgan’s law and the union bound as follows:

Using conditional probability, the summand can be further simplified to

Next, we apply Proposition 1, so there exists $N$ (dependent on $\eta$ and $\theta$) such that for $t>N$, $\operatorname{\mathbb{P}}_{\theta}\!\left(\mathcal{G}_{t}^{\eta}\right)\geq\frac{1}{2}$ and thus

Since $\mathcal{D}\!\left(\nu_{\theta}(S_{i-1},A_{i-1})\,\|\,\nu_{\vartheta}(S_{i-1},A_{i-1})\right)<\infty$ for all $\vartheta\not=\theta$, $\mathscr{M}^{\theta}$ is an $\mathscr{F}_{t}$-martingale with bounded increments, and applying Azuma’s inequality [22] obtains:

which holds for $t$ large, $\eta$ small and $\delta<\varepsilon\eta$. Plugging this into (IV-B):

and therefore (5) leads to:

for $t$ sufficiently large and some $\delta_{1},\delta_{2},\lambda_{1},\lambda_{2}>0$ dependent on $\theta$ and $p$. Finally: