Abstract

Thompson sampling (TS) has been known for its outstanding empirical performance supported by theoretical guarantees across various reward models in the classical stochastic multi-armed bandit problems. Nonetheless, its optimality is often restricted to specific priors due to the common observation that TS is fairly insensitive to the choice of the prior when it comes to asymptotic regret bounds. However, when the model contains multiple parameters, the optimality of TS highly depends on the choice of priors, which casts doubt on the generalizability of previous findings to other models. To address this gap, this study explores the impact of selecting noninformative priors, offering insights into the performance of TS when dealing with new models that lack theoretical understanding. We first extend the regret analysis of TS to the model of uniform distributions with unknown supports, which would be the simplest non-regular model. Our findings reveal that changing noninformative priors can significantly affect the expected regret, aligning with previously known results in other multiparameter bandit models. Although the uniform prior is shown to be optimal, we highlight the inherent limitation of its optimality, which is limited to specific parameterizations and emphasizes the significance of the invariance property of priors. In light of this limitation, we propose a slightly modified TS-based policy, called TS with Truncation (TS-T), which can achieve the asymptotic optimality for the Gaussian models and the uniform models by using the reference prior and the Jeffreys prior that are invariant under one-to-one reparameterizations. This policy provides an alternative approach to achieving optimality by employing fine-tuned truncation, which would be much easier than hunting for optimal priors in practice.

1 Introduction↩︎

In the classical parametric stochastic multi-armed bandit (MAB) problems, an agent plays an arm at every round. In each round, the agent observes a reward generated from the distribution associated with the played arm, whose functional form is known, but the specific values of parameters are unknown. Since the agent observes a reward only from the played arm and is not aware of the true parameters, they have to choose an arm carefully to maximize rewards based on the history of their choices and corresponding rewards. Therefore, the MAB problem is one of the elementary models that exemplify the tradeoff between the exploration to learn parameters and the exploitation of knowledge to accumulate rewards.

For this problem, we can evaluate the performance of an agent’s policy by the regret defined as the difference between maximum rewards and the rewards obtained from the policy since minimizing the expected regret is equivalent to maximizing expected rewards. [1] provided an asymptotic problem-dependent lower bound on the expected regret that captures the optimal problem-dependent performance, which was generalized by [2]. Note that their regret bounds are on the frequentist’s view, where the parameters are regarded as fixed quantities, and we say a policy matching this lower bound to be asymptotically optimal.

Out of the various policies in the bandit literature, this paper focuses on the asymptotic optimality of Thompson sampling (TS) due to its outstanding empirical performance [3]. TS is a randomized Bayesian policy that maintains a posterior distribution over the unknown parameters [4]. Therefore, the choice of the priors would be important since TS plays an arm according to the posterior probability of being the best arm. When there is no prior knowledge of the parameters, it is reasonable to utilize noninformative priors based on the interpretation initially proposed by [5] and subsequently discussed by [6]:

Noninformative priors should be taken as default priors, upon which everyone could fall back when the prior information is missing.

In this study, we translate this description to the usefulness of TS with noninformative priors as a starting point for bandit problems where no prior knowledge is available. One naive choice would be the uniform prior that assigns equal probability to all possible values over the parameter space [7], which obviously represents the ignorance of the parameters and can be defined for any model. However, as pointed out in literature [8], uniform priors can vary depending on the parameterization of the distribution, which means that when the same distribution is modeled by different parameters, the resulting posterior distributions may also be different. [6] also emphasized the importance of invariance properties, especially when one makes inferences on multiple parameters.

Nevertheless, when it comes to the problem-dependent regret bounds of TS, it is often reported that TS is not too sensitive to the choice of the prior for the model of single-parameter distributions. For example, both the uniform prior [9] and the Jeffreys prior [10] are found to be optimal for the Bernoulli models. Note that the reference prior also leads to the optimal regret bound for the Bernoulli bandit models since the Jeffreys prior coincides with the reference prior for the regular single-parameter models [11]. This would be due to the fact that in MAB problems, the focus is solely on inferring the mean of the reward model, which differs from other pure inference tasks that involve multiple parameters of interest.

However, it has been shown that the choice of noninformative priors can significantly impact the performance of TS for noncompact multiparameter bandit models, such as the Gaussian models [12] and the Pareto models [13]. These results indicate that the choice of noninformative priors becomes more challenging in multiparameter models than that in single-parameter models. In this paper, we first show that the prior sensitivity of TS occurs not only in the noncompact multiparameter models but also in the uniform model with unknown supports, which is a compact non-regular multiparameter model. Specifically, we show that TS with the uniform prior with location-scale (LS) parameterization is asymptotically optimal, while TS with the reference prior and the Jeffreys prior are suboptimal. The implication of this discovery is twofold. Firstly, the bounds show the importance of selecting priors in multiparameter models, extending the understanding provided by [12] and [13]. Moreover, the invariance problems of the uniform priors mentioned above make the optimal regret bound less informative. This is demonstrated in the O-T column of Gaussian and uniform models in Table ¿tbl:tab:32overall95rslt?, where we showed that some uniform priors are optimal while others are not.

ccccccccc Model & R & C & T & Parameter \(\theta\) & Priors & O-T & O-TT
& & & & & \(\pi_\mathrm{u}^{\mu,\sig}\) & \(_{\text{Thm. 1}}\) & \(_{\text{Thm. 4}}\)
& & & & & \(\pi_\mathrm{j}\) & \(_{\text{Thm. 2}}\) & \(_{\text{Thm. 4}}\)
& & & & & \(\pi_\mathrm{r}\) & \(_{\text{Thm. 2}}\) & \(_{\text{Thm. 4}}\)
& & & & & & &
& & & & & & & &
& & & & & \(\pi_\mathrm{u}^{\mu,\sig}\) & \(_H\) & \(_{\text{Thm. 5}}\)
& & & & & \(\pi_\mathrm{j}\) & \(_H\) & \(_{\text{Thm. 5}}\)
& & & & & \(\pi_\mathrm{r}\) & \(_H\) & \(_{\text{Thm. 5}}\)
& & & & & & &
& & & & & & & &
& & & & & \(\pi_\mathrm{u}^{\sig, \alpha}\) & \(_L\) & \(_L\)
& & & & & \(\pi_\mathrm{j}\) & \(_L\) & \(_L\)
& & & & & \(\pi_\mathrm{r}\) & \(_L\) & \(_L\)
& & & & & & &
& & & & & & & &

Moreover, recent findings have demonstrated that selecting the uniform prior with scale-shape parameterization is suboptimal for Pareto bandits [13]. These results raise concerns about the reliability of the uniform prior as a fallback option, as it becomes evident that the choice of parameterization in statistical models requires meticulous consideration. This brings us to the central question that serves as the driving force behind this paper:

Is there a universally applicable prior in general bandit models that consistently leads to high-performance outcomes when employed in posterior sampling?

As noted in [14], the three most important criteria for noninformative priors would be simplicity, generality, and trustworthiness. Although several well-known noninformative priors have been studied for multiparameter models, none of them simultaneously satisfy all three criteria in the context of MAB problems. In general, there is no silver bullet that can optimally address all problems. However, it might be possible to discover a “bronze bullet”, a solution that achieves optimal performance in certain scenarios while still maintaining reasonable effectiveness in others, which can serve as a valuable baseline.

On the other hand, one might be looking forward to an alternative approach with renowned (invariant) priors that can provide practical and optimal solutions rather than hunting for good priors. In this regard, we propose a variant of TS, called TS with Truncation (TS-T), for the uniform models and the Gaussian models. We provide a finite-time regret analysis of TS-T, which demonstrates its asymptotic optimality under the reference prior and the Jeffreys prior for both models. Our approach builds upon the basic strategy of TS, but with key modifications that improve the performance and address the limitations of TS. In particular, we devise an adaptive truncation procedure on the parameter space of the posterior distribution to control the problems in the early stage of learning, hence the name truncation in TS-T. The proposed policy is inspired by the policies proposed in [15] and [13], extending and generalizing their approaches. We further provide a high-level design idea that can be generalized to other reward models easily.

The main results of this paper and related works are summarized in Table ¿tbl:tab:32overall95rslt?, and our contributions are summarized as follows:

We prove the asymptotic optimality/suboptimality of TS with noninformative priors for the uniform bandits. This extends the understanding of TS in the multiparameter models, which have not been well studied so far, emphasizing the significance of selecting noninformative priors.
We show that some uniform priors with different parameterizations are suboptimal. This makes the optimality of TS with the uniform prior less attractive in general, as it inherently involves the non-trivial task of selecting appropriate parameterizations.
We propose a variant of TS that is asymptotically optimal for the uniform models and the Gaussian models under the reference prior and the Jeffreys prior, where the vanilla TS is found to be suboptimal. This provides optimal results that remain consistent regardless of the way of parameterizing the models, which addresses the limitations of the vanilla TS.

2 Preliminaries↩︎

In this section, we formulate \(K\)-armed bandit problems and the asymptotic regret lower bound for the uniform models and Gaussian models.

2.1 Problem Formulation↩︎

Suppose that there are finite \(K\) arms associated with a reward distribution \(\nu_{\theta}\) belonging to the LS family, whose density function is denoted by \(f_{l,\sigma}(x)\) with location \(l \in \mathbb{R}\) and scale \(\sigma\in \mathbb{R}_{+}\). Here, the parameters \(\theta = (l,\sigma) \in \mathbb{R}\times \mathbb{R}_{+}\) are unknown to the agent. Note that we consider MAB problems where every arm is modeled by the same type of distribution but with possibly different parameters.

If a random variable \(X\) with the density function \(f_{\theta}(x)\) belongs to the LS family, then \(f_{l,\sigma}\) can be written using a probability density function \(f_{0,1}(\cdot)\) as \[\label{eq:32uni95LSfamily} f_{l,\sigma}(x) = \frac{1}{\sigma}f_{0,1}\left( \frac{x - l}{\sigma}\right).\tag{1}\] Although location \(l\) is not necessarily equivalent to the expectation \(\mu(\theta) = \mathbb{E}_{\nu_\theta}[X]\) in general, we use them interchangeably in this paper since they coincide for both the Gaussian and uniform models. One can retrieve the density function of the Gaussian distribution \(\mathrm{Gaussian}({\mu, \sigma})\) with location (mean) \(\mu\) and scale \(\sigma\), \(f_{{\mu, \sigma}}^{\mathrm{G}}(x)\), by substituting the standard normal density for \(f_{0,1}\). The uniform distribution can be obtained by letting \(f_{0,1}(x) = \boldsymbol{1}[0 \leq x \leq 1]\) for the indicator function \(\boldsymbol{1}[\cdot]\). If \(X\) follows the uniform distribution \(\mathrm{Uni}_{\mu\sigma}(\mu, \sigma)\) under the LS parameterization, then it has the density of the form with location (mean) \(\mu\) and scale \(\sigma\), \[f_{\mu,\sigma}^{\mathrm{U}_{\mu\sigma}}(x) = \frac{1}{\sigma} \boldsymbol{1}\left[ \mu - \frac{\sigma}{2} \leq x \leq \mu + \frac{\sigma}{2}\right].\] The uniform distribution can be reparameterized in terms of the boundary of the support by letting \((a,b) = \left(\mu - \frac{\sigma}{2}, \mu + \frac{\sigma}{2} \right)\), denoted by \(\mathrm{Uni}_{ab}(a,b)\), whose density function is given as \(f_{a,b}^{\mathrm{U}_{ab}}(x) = \frac{1}{b-a} \boldsymbol{1}[a \leq x \leq b]\). Here, we assume that the arm \(1\) is the unique optimal arm that has the maximum expected reward for convenience without loss of generality, i.e., \(\mu_1 = \max_{i\in[K]} \mu_i\) and \(\mu_1 > \mu_i\) for \(i \in \{2, \ldots, K\}\). This assumption is made to simplify the analysis, and it is worth noting that incorporating additional optimal arms can only decrease the expected regret of TS [16].

Denote the index of the arm played at round \(t\) by \(j(t)\) and the number of rounds that the arm \(i\) is played until round \(t\) by \(N_i(t)=\sum_{s=1}^{t-1}\boldsymbol{1}[j(s)=i]\). Then, the regret at round \(T\) is defined with the sub-optimality gap \(\Delta_i := \mu_1 - \mu_i\) as \[\mathrm{Reg}(T) = \sum_{t=1}^T \Delta_{j(t)} = \sum_{i=2}^K \Delta_i N_i(T+1).\] When the sub-optimality gap is regarded as a fixed quantity, [2] showed that any policy, satisfying \(\mathrm{Reg}(T) = o(t^\alpha)\) for all \(\alpha \in (0,1)\), must satisfy \[\begin{align} \label{eq:32burnetasLB} \liminf_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \geq \sum_{i=2}^K \frac{\Delta_i}{\inf_{\theta: \mu(\theta)> \mu_1}\mathrm{KL}(\nu_{\theta_i}; \nu_{\theta})}, \end{align}\tag{2}\] where \(\mathrm{KL}(\cdot;\cdot)\) denotes the Kullback-Leibler (KL) divergence. Here, an algorithm is said to be asymptotically optimal if it satisfies \[\limsup_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \leq \sum_{i=2}^K \frac{\Delta_i}{\inf_{\theta: \mu(\theta)> \mu_1}\mathrm{KL}(\nu_{\theta_i};\nu_{\theta})}.\] The infimum over the KL divergence can be explicitly computed for any \(i\ne 1\) under uniform models [17] as \[\label{eq:32LB95u} \inf_{\theta: \mu(\theta)> \mu_1}\mathrm{KL}(\nu_{\theta_i};\nu_{\theta}) = \log\left(1+ \frac{2\Delta_i}{\sigma_i}\right)\tag{3}\] and under Gaussian models [12] as \[\label{eq:32LB95g} \inf_{\theta: \mu(\theta)> \mu_1}\mathrm{KL}(\nu_{\theta_i};\nu_{\theta}) = \frac{1}{2}\log \left(1 + \left(\frac{\Delta_i}{\sigma_i}\right)^2 \right).\tag{4}\]

3 Thompson Sampling and the Choice of Priors↩︎

In this section, we instantiate TS and propose a variant of TS, TS-T, for the uniform model and the Gaussian model based on the noninformative priors.

3.1 Noninformative Priors in the LS Family↩︎

To develop an invariant noninformative prior, one can consider the Fisher information matrix (FIM), which does not rely on any prior information on unknown parameters. The FIM for the LS family is given as follows [11]: \[I(l, \sigma) = \sigma^{-2} \begin{bmatrix} c_1 & c_2 \\ c_2 & c_3 \end{bmatrix},\] where \(c_1, c_2\), and \(c_3\) are functions of \(f\) and do not involve parameters \(\theta=(l,\sigma)\). Then, the FIM for the uniform model and the Gaussian model are given as follows: \[\begin{align} (c_1, c_2, c_3) = \begin{cases} (0, 0, 1) &\text{ if } f_{l,\sigma} = f_{\mu, \sigma}^{\mathrm{U}_{\mu\sigma}}, \\ (1, 0, 2) &\text{ if } f_{l,\sigma} = f_{\mu, \sigma}^{\mathrm{G}}. \end{cases} \end{align}\] Since \(c_2 =0\), from the orthogonality, the first-order probability matching prior is of the form \(\sigma^{-k}\) for \(k\in \mathbb{R}\) [18], [19]. This prior not only provides the posterior in a close form, but also encompasses various well-known noninformative priors as special cases in the LS family such as the uniform prior \(\pi_{\mathrm{u}}(l,\sigma) \propto 1\) by \(k=0\). Throughout the rest of the paper, unless otherwise stated, \(\pi_\mathrm{u}\) denotes the uniform prior with \((l,\sigma)\) parameterization.

Furthermore, when \(k=1\), it coincides with the reference prior \(\pi_{\mathrm{r}}(l, \sigma) \propto \sigma^{-1}\), which is the unique second-order probability matching prior [20]. On the other hand, the Jeffreys prior is not defined well for the uniform model since the determinant of the FIM is zero. Nevertheless, in this paper, we call prior with \(k=2\) as the Jeffreys prior \(\pi_{\mathrm{j}}(l, \sigma) \propto \sigma^{-2}\) even for the uniform model to maintain consistency with the Gaussian model. More details on the noninformative priors are provided in the appendix for completeness.

3.2 Thompson Sampling↩︎

For the priors \(\sigma^{-k}\), we denote the joint posterior distribution after observing \(n\) rewards from the arm \(i\), \(X_{i,n} := (x_{i,1}, \ldots, x_{i,n})\) by \(\pi^{k}({\mu, \sigma}|X_{i,n})\) or simply \(\pi_{i,n}^k({\mu, \sigma})\). Let us denote the (classical) sufficient statistic \(T(X_{i,n})\) for the parameter \((\mu_i,\sigma_i)\). Since the sufficient statistic is always Bayes-sufficient [21], one can rewrite the posterior distribution using the sufficient statistic as \[\pi^k({\mu, \sigma}|X_{i,n}) = \pi^k({\mu, \sigma}| T(X_{i,n})).\] The vanilla TS observes samples \((\tilde{\mu}_i(t), \tilde{\sigma}_i(t))\) generated from the posterior \(\pi_{i,N_i(t)}^k({\mu, \sigma})\) at each round. Since maximum likelihood estimators (MLEs) can be chosen as a function of sufficient statistics if any MLE exists [22], we denote the posterior after \(n\) observations as \(\pi^k({\mu, \sigma}|\hat{\mu}_{i,n}, \hat{\sigma}_{i,n})\), instead of \(\pi^k({\mu, \sigma}|T(X_{i,n}))\), to explicitly indicate the estimates after \(n\) observations for the priors \(\sigma^{-k}\). We adopt this notation as it facilitates a clear distinction between the vanilla TS and TS-T.

3.3 Thompson Sampling with Truncation↩︎

As shown in previous studies on the multiparameter bandit models [12], [13], TS sometimes plays only suboptimal arms when the posterior of the optimal arm has a very small variance in the early stage of learning, which contributes to the suboptimality in expectation. To avoid such problems, TS-T samples parameters from the distributions obtained by replacing an MLE of the scale \(\hat{\sigma}_n\) with a truncated estimator \(\bar{\sigma}_n\) satisfying \(\bar{\sigma}_n = \Omega(n^{-\beta})\) for some \(\beta >0\). Note that we choose a specific \(\beta\) to make regret analysis simple, but our discussion can be easily extended to any \(\beta >0\). Such truncation prevents an extreme case where \(\hat{\sigma}_n \approx 0\) for small \(n\) in the regret analysis. In summary, TS-T is a policy that samples parameters from the distribution at every round, which is \[\label{eq:32TST95post} \bar{\pi}_{i,n}^k({\mu, \sigma}) = \pi^k({\mu, \sigma}| \hat{\mu}_{i,n}, \bar{\sigma}_{i,n}).\tag{5}\] Strictly speaking, TS-T is not a Bayesian policy but rather a kind of randomized probability matching policy as the distribution in (5 ) is not a posterior distribution anymore. However, TS-T can be seen as a pre-processed posterior probability matching policy since the truncation is applied before sampling and will behave like TS as \(n\) increases where the truncation has almost no effect.

3.3.1 General Design Idea of TS-T↩︎

Adaptive truncation in the parameter space of the posterior was considered in [13], where they aimed to compensate for the change of the priors by replacing the MLE with a truncated one. The following design principle is a generalization of their approach to handling the problems in the first few rounds:

Truncate the parameter space of the posterior distribution to stretch the distribution, which encourages a policy to explore more in the early stage of learning.

Here, stretching the posterior distribution can be seen as flattening the posterior distributions, which prevents them from overly concentrating on the specific value in the first few rounds. By flattening the distributions, we encourage exploration and avoid prematurely favoring a specific arm based on the small number of observations.

As an illustration, we consider a case where the posterior distribution is represented by a Gaussian distribution in Figure 1, where Figure 1 (a) displays the posteriors of each arm. During the initial learning phase, the inherent randomness of the rewards can cause the posterior distribution of the optimal arm (arm \(1\)) to be concentrated around a small value, such as \(0\), in this particular example. As a result, this concentration of the posterior may result in suboptimal behavior, where the vanilla TS is more likely to play the arm \(2\) that exhibits a higher expected reward according to the current posterior distribution. To address this issue, one can lift the scale parameter of the Gaussian (posterior), as depicted in Figure 1 (b), in order to prevent the occurrence of extreme cases during the early stage of learning. Obviously, one has to design the truncation carefully to cover the entire parameter space of the posterior as the number of samples increases.

In this paper, we truncate the parameter space by replacing sufficient statistics with truncated ones, which induces a truncated estimator instead of the MLE. Therefore, we expect that our approach can be easily applied to any model where sufficient statistics have a constant dimension, such as the (quasi-)exponential family [6]. This offers an alternative approach to achieving optimality without the need to search for an optimal or appropriate prior for each specific problem, a process we expect will be significantly more convenient in practical applications.

3.3.2 Comparison with Different Adaptive Approaches↩︎

It is worth noting that a similar adaptive approach has been considered in the Gaussian model with known variance [15] and linear models [23]. In these approaches, the posterior distribution was modeled as a Gaussian distribution and an adaptive inflation value \(\rho_t\) was introduced to the scale parameter, which effectively flattened the posterior distributions. If one extends their approaches to the LS family, it becomes a probability matching policy with the modified posterior \(\pi^k(\mu,\sigma| \hat{\mu}_{i,n}, \rho_t \hat{\sigma}_{i,n})\). However, we found that this still has a similar problem to the naive TS in our analysis, which is related to Lemmas 10 and 12 in the appendix². In addition, [15] clipped the outputs after sampling to achieve minimax optimality, which can be seen as a post-processed posterior matching policy. While our paper does not establish the minimax optimality of TS-T, we expect that combining similar techniques with our approach could be a promising direction for the simultaneous achievement of asymptotic optimality and minimax optimality in multiparameter models, which presents an interesting problem for follow-up investigation.

3.4 Analytical Expressions of Posterior Distributions↩︎

Here, we present the formulation of the posterior for TS and TS-T in the uniform and Gaussian models. The detailed derivation for the uniform model is given in the appendix.

3.4.1 Uniform Bandits↩︎

If rewards \((x_{i,s})\) follow \(\mathrm{Uni}_{\mu\sigma}(\mu_i, \sigma_i)\), the sufficient statistic is given as \(T(X_{i,n}) = (x^{(1)}_i, x^{(n)}_i)\) for \(x^{(1)}_i = \min_{s \in [n]} x_{i,s}\) and \(x^{(n)}_i= \max_{s \in [n]} x_{i,s}\). Then, the marginal posterior of \(\sigma\) and the conditional posterior of \(\mu\) given \(\sigma\) under the prior \(\sigma^{-k}\) are given as follows: \[\begin{align} \pi^{\mathrm{U}, k}(\sigma| \hat{\mu}_{i,n}, \hat{\sigma}_{i,n}) &= n_k(n_k+1) \left(\hat{\sigma}_{i,n}\right)^{n_k} \frac{\sigma- \hat{\sigma}_{i,n}}{\sigma^{n_k+2}} \boldsymbol{1}\left[\sigma\geq \hat{\sigma}_{i,n}\right],\addtocounter{equation}{1}{\tag{6}}\\ \pi^{\mathrm{U}, k}(\mu | \hat{\mu}_{i,n}, \hat{\sigma}_{i,n}, \sigma= \tilde{\sigma}) &= f_{\hat{\mu}_{i,n}, \tilde{\sigma}-\hat{\sigma}_{i,n}}^{\mathrm{U}_{\mu\sigma}}(\mu),\addtocounter{equation}{1}{\tag{7}} \end{align}\] where MLEs \(\hat{\mu}_{i,n} = \frac{x^{(n)}_i + x^{(1)}_i}{2}\) and \(\hat{\sigma}_{i,n} = x^{(n)}_i - x^{(1)}_i\), and \(n_k = n+k-2\).

Here, following [13], we employ a sequential sampling scheme to avoid the use of computationally costly approximation methods. This means that \(\tilde{\sigma}\) is sampled first from the marginal posterior in (6 ), which can be easily implemented by using the inverse transform sampling method. Then we sample \(\tilde{\mu}\) from the conditional posterior given the sampled scale parameter \(\tilde{\sigma}\) in (7 ). This sequential sampling approach yields the same result as sampling \(\mu\) from the joint posterior \(\pi_{i,n}({\mu, \sigma}) = \pi_{i,n}(\sigma) \pi_{i,n}(\mu|\sigma)\). Here, initial \(n_0=\max(2, 3-\lceil k \rceil)\) plays are required to avoid improper posteriors, where \(\lceil \cdot \rceil\) denotes the ceiling function.

As described in (5 ), TS-T is a sampling policy with the distribution parameterized by a truncated scale estimator. For the uniform models, we simply replace \(x^{(n)}\) with a truncated statistic \(\bar{x}^{(n)}=\max( x^{(1)}+n^{-1}, x^{(n)} )\). In other words, we replace \(\hat{\sigma}_{n}\) with \(\bar{\sigma}_{n} = \bar{x}^{(n)} - x^{(1)}\), which satisfies \(\bar{\sigma}_{n} \geq n^{-1}\). This truncation procedure is specific to the posterior sampling in (6 ) and (7 ), and is introduced to avoid the situation where parameters are sampled from a distribution whose density function is similar to the Dirac delta function. Therefore, under the TS-T policy, an agent observes samples from the following distributions: \[\begin{align} \bar{\pi}_{i,n}^{\mathrm{U},k}(\sigma) &= \pi^{\mathrm{U},k}(\sigma| \hat{\mu}_{i,n}, \bar{\sigma}_{i,n}) \addtocounter{equation}{1}{\tag{8}} \\ \bar{\pi}_{i,n}^{\mathrm{U},k}(\mu|\sigma= \tilde{\sigma}) &= f_{\hat{\mu}_{i,n}, \tilde{\sigma}-\bar{\sigma}_{i,n}}^{\mathrm{U}_{\mu\sigma}}(\mu),\addtocounter{equation}{1}{ \tag{9}} \end{align}\] where we simply replaced \(\hat{\sigma}_{i,n}\) with \(\bar{\sigma}_{i,n}\) in (6 ) and (7 ).

3.4.2 Gaussian Bandits↩︎

For the Gaussian model, the sufficient statistic is given as \(T(X_{i,n})=(\hat{x}_{i,n}, S_{i,n})\) where \(\hat{x}_{i,n} = \frac{1}{n}\sum_{s=1}^n x_{i,s},\) and \(S_{i,n} = \sum_{s=1}^n (x_{i,s} - \hat{x}_{i,n})^2\). Then, the marginal posterior distribution of \(\mu\) under the priors \(\sigma^{-k}\) is given as \[\label{eq:32TSpost95gauss} \pi^{\mathrm{G}, k}\left(\mu| \hat{\mu}_{i,n}, \hat{\sigma}_{i,n} \right) = f^{\mathrm{t}}_{n_k}(\mu|\hat{\mu}_{i,n}, \hat{\sigma}_{i,n}),\tag{10}\] where \(f^{\mathrm{t}}_{n_k}(\cdot|\hat{\mu}_{i,n}, \hat{\sigma}_{i,n})\) denotes the density function of the non-standardized \(\mathrm{t}\)-distribution with the degree of freedom \(n_k= n+k-2\), location \(\hat{\mu}_{i,n}= \hat{x}_{i,n}\), and scale \(\hat{\sigma}_{i,n}= \sqrt{S_{i,n}/n}\). [12] showed that TS with priors \(k\geq 1\) could not achieve the lower bound with (4 ).

For the realization of the TS-T policy in the Gaussian models, we consider a truncated statistic and the corresponding scale estimator as follows: \[\bar{S}_{i,n} = \max(1, S_{i,n}) \implies \bar{\sigma}_{i,n} = \sqrt{\bar{S}_{i,n} n^{-1}}\geq n^{-\frac{1}{2}}.\] This implies that TS-T draws a sample from the distribution whose density function is given as \[\label{eq:32TSTpost95gauss} \bar{\pi}^{\mathrm{G},k}_{i,n}\left(\mu\right) = \pi^{\mathrm{G},k}\left(\mu| \hat{\mu}_{i,n}, \bar{\sigma}_{i,n} \right) = f_{n_k}^{t}(\mu | \hat{\mu}_{i,n}, \bar{\sigma}_{i,n}),\tag{11}\] where we just replaced \(\hat{\sigma}_{i,n}\) with \(\bar{\sigma}_{i,n}\) in (10 ). In the Gaussian models, we can easily sample the location parameter directly from its marginal posterior distribution as it can be expressed by a well-known probability distribution. Note that we require \(n_0\) initial plays to avoid improper posteriors.

4 Main Results↩︎

This section provides the main theoretical results of this paper, whose detailed proofs are postponed to the appendix.

Theorem 1. Assume that the arm \(1\) is the unique optimal arm with a finite mean. Given arbitrary \(\epsilon\in \left(0, \min_{i\ne 1} \frac{\Delta_i}{2}\right)\), the expected regret of TS with the prior \(\sigma^{-k}\) with \(k < 1\) for the uniform models is bounded as \[\mathbb{E}[\mathrm{Reg}(T)] \leq \sum_{i=2}^K \Delta_i \Bigg( \frac{ \log T}{\log\left(1 + \frac{2\Delta_i - 4\epsilon}{\sigma_i} \right)} + \frac{2\sigma_i}{\epsilon} + \frac{11}{2} - \lceil k \rceil - k \Bigg) + \Delta_{\mathrm{max}} C(\epsilon, k, \sigma_1),\] where \(\Delta_{\mathrm{max}}=\max_{i\ne 1} \Delta_i\) and \(C(\epsilon,k, \sigma_1) = 1+\frac{9\sigma_1}{\epsilon} + \frac{3}{16(1-k)} \frac{\sigma_1^2}{\epsilon^2}(2e^{\frac{2\epsilon}{\sigma_1}}-1) = \mathcal{O}\left(\frac{\sigma_1^2}{(1-k)\epsilon^2}\right)\).

Since Theorem 1 holds for any \(\epsilon\in \left(0, \min_{i\ne 1} \frac{\Delta_i}{2}\right)\), letting \(\epsilon= \mathcal{O}((\log T)^{-1/3})\) directly implies that \[\begin{align} \liminf_{T\to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \leq \sum_{i=2}^K \frac{\Delta_i}{\log\left(1 + \frac{2\Delta_i}{\sigma_i} \right)}, \end{align}\] which shows the asymptotic optimality of TS with \(k < 1\) in terms of the regret lower bound with (3 ). Notice that our bound is tighter than the optimal upper-confidence bound (UCB) based policy of [17], where the remaining term is \(\mathcal{O}(\epsilon^{-3})\).

Theorem 1 not only establishes asymptotic optimality but also provides two additional observations: (i) A moderate choice of \(k\) can be beneficial because having a too small \(k\) induces larger regrets as it requires many initial plays, while large \(k\) increases \(C(\epsilon, k, \sigma_1)\). The reduction in \(C(\epsilon, k, \sigma_1)\) is preferable when \(\epsilon\) is sufficiently small. (ii) We need a more delicate approach to consider the worst-case scenario where both \(\Delta_i\) and \(\sigma_i\) are extremely large. Since \(\sigma_i\) is an unknown problem-dependent constant in this paper, we cannot directly apply the techniques used in the case where \(\sigma_i\) is assumed to be a given fixed constant [15], [24].

Next, we show that the vanilla TS with \(k \geq 1\) based on the posteriors in (6 ) and (7 ) cannot achieve the regret lower bound in the theorem below. To simplify the analysis, we consider two-armed bandit problems where two arms have the same left-boundary point of the support. Furthermore, we provide the full information on the arm \(2\) to the agent following the previous proofs [12], [13], where the prior on the arm 2 is the Dirac measure so that \(\tilde{\mu}_2(t) = \mu_2\) holds for any round \(t \in \mathbb{N}\).

Theorem 2. Assume that the arm \(1\) follows \(\mathrm{Uni}_{ab}(a_1, b_1)\) and the arm \(2\) follows \(\mathrm{Uni}_{ab}(a_2, b_2)\) with \(a_1= a_2\) and \(b_2 < b_1\), where \(\mu_1 > \mu_2\) holds. When \(\tilde{\sigma}_1(t)\) and \(\tilde{\mu}_1(t)\) are sampled from the posteriors in (6 ) and (7 ) with the priors \(k\geq 1\), and \(\tilde{\mu}_2(t) = \mu_2\) holds, there exists a constant \(\xi^{\mathrm{U}} > 0\) independent of \(\sigma_2\) satisfying \[\liminf_{T \to \infty}\frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \geq \Delta_2 \xi^{\mathrm{U}}.\] If \(k>1\), then there exist constants \(\xi^{\mathrm{U}}_k >0\) independent of \(\sigma_2\) satisfying \[\liminf_{T \to \infty}\frac{\mathbb{E}[\mathrm{Reg}(T)]}{T^{\frac{k-1}{k}}} \geq \Delta_2 \xi^{\mathrm{U}}_k.\]

Theorem 2 shows that TS with \(k\geq 1\) suffers at least logarithmic regrets in expectation. Although the regret lower bound with (3 ) approaches zero for sufficiently small \(\sigma_2=b_2-a_2\), the regret of TS is lower-bounded by a non-zero term since the coefficient of \(\log T\) converges to a non-zero constant. Therefore, TS with prior \(k \geq 1\) is suboptimal, at least for sufficiently small \(\sigma_2\), where the same result was found in the Gaussian models [12]. Furthermore, one can see that priors with \(k > 2\) are suboptimal even in the view of the worst-case analysis since their regret can be larger than \(\sqrt{T}\) order for some instances.

From Theorem 2, we can obtain the following corollary, which shows the suboptimality of some uniform priors with different parameterizations.

Corollary 1. For any one-to-one transformations \(g(\mu)\) and \(h(\sigma)\), if \(\frac{\mathrm{d}}{\mathrm{d}\mu} g^{-1}(\mu)\propto 1\) and \(\frac{\mathrm{d}}{\mathrm{d}\sigma} h^{-1}(\sigma) \propto \sigma^{-k}\) hold with some \(k\geq 1\), then TS with the uniform priors with \((g(\mu),h(\sigma))\) parameterization, \(\pi_{\mathrm{u}}^{g(\mu), h(\sigma)}\) is suboptimal.

Proof. The uniform prior with \((g(\mu),h(\sigma))\) parameterization indicates that \(\pi_{\mathrm{u}}^{g(\mu), h(\sigma)} \propto 1\). Let us define \(f(\mu,\sigma) = (g^{-1}(\mu), h^{-1}(\sigma))\). Then, the corresponding prior with \(({\mu, \sigma})\) parameterization can be obtained by multiplying the absolute value of the Jacobian determinant of \(f\), which is given as \(|\det \nabla f| \cdot \pi_{\mathrm{u}}^{g(\mu), h(\sigma)} = \sigma^{-k}\). Since \(k\geq 1\) holds from the assumption, the proof follows from Theorem 2 in this paper for the uniform models and from Theorem 2 in [12] for the Gaussian models. ◻

The result of Corollary 1 would not be surprising since one can easily expect that some arbitrary parameterizations can result in poor performance of TS with the uniform prior. However, this variability can introduce unnecessary concerns about the appropriate way to parameterize models. While the uniform prior with the LS parameterization might seem like a natural choice in the LS family, this idea cannot be generalized to other models. For instance, the uniform prior with the scale-shape parameterization in the Pareto model was shown to be suboptimal [13] and Corollary 1 further demonstrates the suboptimality of the rate-shape parameterization. Another consideration would be the use of natural parameters for exponential family models. However, the uniform prior with \(\left( \frac{\mu}{\sigma^2}, -\frac{1}{2\sigma^2} \right)\) parameterization can be seen as prior with \(k=5\) in the LS parameterization, which is suboptimal in the Gaussian bandits. Therefore, such observations emphasize the importance of the invariance property of the priors in the MAB problems, which is related to the trustworthiness of priors.

The theorem below shows the asymptotic optimality of TS-T with the prior with any \(k\), including the reference prior³ and the Jeffreys prior that are invariant under any one-to-one transformations.

Theorem 3. With the same notation as Theorem 1, the expected regret of TS-T with prior \(k \in \mathbb{R}\) for the uniform models is bounded as \[\mathbb{E}[\mathrm{Reg}(T)] \leq \sum_{i=2}^K \Delta_i \Bigg(\frac{ \log T}{\log\left(1 + \frac{2\Delta_i - 4\epsilon}{\sigma_i} \right)} + \frac{2\sigma_i}{\epsilon} + \frac{1}{\sigma_i} + \max\left( \frac{7}{2} , \frac{9}{2}-\lceil k \rceil \right)\Bigg) + \Delta_{\mathrm{max}}C'(\epsilon, k, \sigma_1),\] where \(C'(\epsilon, k, \sigma_1) = 1+\frac{9\sigma_1}{\epsilon} + \frac{3}{16} \frac{\sigma_1^2}{\epsilon^2}(2e^{\frac{2\epsilon}{\sigma_1}}-1) = \mathcal{O}\left(\frac{\sigma_1^2}{\epsilon^2}\right)\) for \(k < 1\), \(C'(\epsilon, 1, \sigma_1) = \mathcal{O}\left( \frac{\sigma_1^2 \log(\sigma_1)}{\epsilon^2} \right)\), and for \(k>1\) \(C'(\epsilon, k, \sigma_1) = \mathcal{O}\left( \frac{\sigma_1^{2k}}{\epsilon^{k+1}} \right)\).

Although Theorem 3 states that any prior \(\sigma^{-k}\) can achieve the regret lower bound asymptotically, we recommend using the priors with \(k\in [0,1]\) since small \(k\) requires many initial plays from \(n_0= \max(2, 3-\lceil k \rceil)\), while large \(k\) will suffer from a large regret in the finite time due to large \(C'(\epsilon,k,\sigma_1)\).

Not only for the uniform models, but TS-T with the reference prior and the Jeffreys prior are also asymptotically optimal for the Gaussian models, which were found to be suboptimal for TS [12].

Theorem 4. Assume arm \(1\) is the unique optimal arm with a finite mean. Given arbitrary \(\epsilon\in \left(0, \min_{i\ne 1} \frac{\Delta_i}{2}\right)\), there exists a problem-prior-dependent constant \(C''(\epsilon, k, \sigma_1)\) such that the expected regret of TS-T with priors \(\sigma^{-k}\) for the Gaussian models is bounded for \(k \leq 2\) as \[\mathbb{E}[\mathrm{Reg}(T)] \leq \sum_{i=2}^K \Delta_i \Bigg( \frac{ \log T}{\frac{1}{2}\log\left(1 + \frac{(\Delta_i-2\epsilon)^2}{\sigma_i^2+\epsilon}\right)} + \frac{1}{\sigma_i^2 } + 3 -k + \frac{\sqrt{\sigma_i^2+\epsilon}}{\Delta_i - 2\epsilon} + \frac{2\sigma_i^2 e^{\frac{\epsilon}{2\sigma_i^2}}+2\sigma_i^4 e^{\frac{\epsilon}{\sigma_i^2}}}{\epsilon^2} \Bigg) + \Delta_{\mathrm{max}} C''(\epsilon, k, \sigma_1),\] where \(C''(\epsilon, k, \sigma_1) = \mathcal{O}\left( \left(\frac{\sigma_1}{\epsilon}\right)^{4 + \lceil k \rceil \boldsymbol{1}[k \geq 1]}\right)\).

Letting \(\epsilon=\mathcal{O}\left((\log T)^{-1/7}\right)\) provides an \(\epsilon\)-free bound, which shows the asymptotic optimality of TS-T. Although the overall proofs of Theorem 4 resemble that of [12], the introduction of the truncated estimator \(\bar{\sigma}\) induces a technical challenge of integrating a product of the beta function and the incomplete gamma function, which did not occur in the previous analysis. We solve it by exploiting the modified Bessel functions of the second kind and confluent hypergeometric functions of the second kind to carefully control the effect of \(\bar{\sigma}\).

5 Numerical Validation↩︎

This section presents simulation results to validate the theoretical analysis of TS and TS-T. To provide a baseline for comparison, we present the results of asymptotically optimal UCB-based policies, CK-UCB for the uniform bandits [17] where “CK” is the initials of the authors following the notation in the original paper.

We considered a \(6\)-armed uniform bandit instance with parameters given as \(\boldsymbol{\mu}=(5.5, 5.0, 4.5, 4.0, 4.75, 3.0)\) and \(\boldsymbol{\sigma} = (4.5, 5.0, 4.5, 4, 3.75, 2.0)\), which was previously studied [17]. In Figure 2, the solid lines denote the averaged regret over 10,000 independent runs of the policy that was found to be optimal in terms of the regret lower bound with (3 ), whereas the dashed lines denote that of the suboptimal policies. The dotted lines denote the asymptotic regret lower bound. Note that the Jeffreys prior (\(k=2\)) coincides with the uniform prior with the location-rate parameterizations (\(\mu, \sigma^{-1}\)). Validations in the Gaussian models are given in the appendix.

In Figure 2 (a), TS with the uniform prior \(\pi_{\mathrm{u}}^{{\mu, \sigma}}\) shows the best performance, while TS with the Jeffreys prior \(\pi_{\mathrm{j}}\) and the reference prior \(\pi_{\mathrm{r}}\) suffer from a large regret. Although TS with the reference prior shows a similar finite-time performance to CK-UCB, it seems to have a larger regret order compared to asymptotically optimal policies. However, as shown in Figure 2 (b), the performance of TS-T with the reference prior improves significantly, which highlights the effectiveness of the truncation procedure in the TS-based policy.

6 Conclusion↩︎

In this paper, we first demonstrated the importance of choosing noninformative priors for the vanilla TS under the uniform bandit models with unknown supports. Although the uniform prior is optimal in terms of the expected problem-dependent regret, we showed that the use of the uniform prior is problematic due to its dependency on parameterizations, which makes the optimality under the specific parameterization less informative in general. On the other hand, invariant noninformative priors, the reference prior and the Jeffreys prior, are shown to be suboptimal.

Nevertheless, in the various multiparameter models, the reference priors have been shown to be on the borderline between optimal and suboptimal in terms of prior parameter \(k\) [12], [13]. Therefore, we expect that TS with the reference prior could serve as a baseline for other models since the reference posterior can be derived generally [14] and that an optimal policy would perform at least better than TS with the reference priors. Furthermore, by combining with TS-T, one can focus on the adaptive truncation, which provides an alternative solution to achieve optimality with renowned invariant priors. We expect that adaptively truncating parameter space would be more convenient than finding good priors for each model in practice. Our analysis was supported by the simulation results, where the invariant priors under TS-T showed a better performance than those under TS.

Acknowledgement↩︎

JL was supported by JST SPRING, Grant Number JPMJSP2108. CC and MS were supported by the Institute for AI and Beyond, UTokyo.

7 Details on Priors↩︎

In this section, we provide a brief introduction to some well-known noninformative priors that are of relevance to this paper. For a more comprehensive understanding and detailed information, we encourage readers to refer to the references herein.

7.1 Conjugate Priors↩︎

While it is true that prior distributions can be designed arbitrarily, it is obvious that certain choices can make it difficult to accurately infer parameters or induce extremely complicated posterior distributions obtained by Bayes’ theorem, which is computationally expensive to handle. The conjugate prior is defined to solve at least the latter problem by simplifying the computation of the posterior distribution and performing analytical calculations efficiently. Usually, a prior is called conjugate if the posterior and the prior distributions belong to the same model. Beyond the algebraic convenience, [25] provided a geometric meaning of the conjugate prior, where they showed that the conjugate prior has the same geometry as the likelihood when it belongs to the exponential family.

Strictly speaking, the conjugate prior is not a noninformative prior since it often involves the choice of hyperparameters for prior distributions where one can combine their own belief or knowledge [6]. Furthermore, the existence of the conjugate prior for the regular non-exponential family, such as \(t\)-distribution, is unclear since the derivation of the conjugate prior is usually based on the Neyman factorization theorem where the existence of the sufficient is crucial [26], [27] and the existence of a sufficient statistic directly implies the model belongs to the exponential family under mild regularity conditions by Pitman-Koopman-Darmois Lemma [28]. For more details, one can refer to [29], where a similar concept to conjugacy was also introduced.

7.2 Uniform Priors↩︎

One of the most well-known noninformative priors would be the uniform prior, which can be defined for any model as \(\pi_{\mathrm{u}}(\theta) \propto 1\). The simplicity of the uniform prior has led to its widespread adoption in various problem domains, including inventory modeling [30], and bandit problems [9]. However, despite its simplicity and generality, the uniform prior has been criticized due to its variance under reparameterization [31]. This implies that uniform priors can differ depending on the parameterization of the model. Therefore, when the same model is expressed using different parameters, the resulting posterior distributions may also vary. As highlighted by [6], this issue becomes even more critical when performing inference on multiple parameters.

7.3 Jeffreys Priors↩︎

To develop an invariant noninformative prior, [28] employed the Fisher information matrix (FIM), which does not rely on any prior information about unknown parameters. Although there exist multiple definitions of the Fisher information (FI), we adopt the definition suggested by [32] since it can accommodate weaker assumptions and constraints. It is worth noting that the FI obtained from the following definition may not always be well-defined since some elements can be infinite under some distributions.

Definition 1 (Fisher information matrix [32]). For a random variable \(X\) with density \(f_\theta(\cdot)\), Fisher information that \(X\) contains about the parameter \(\theta\) is defined as \[\begin{align} [I(\theta)]_{ij} = I_{ij} = \mathbb{E}_\theta \left[ \left( \frac{\partial}{\partial \theta_i}\log f_\theta(X) \right) \left( \frac{\partial}{\partial \theta_j}\log f_\theta(X) \right)\right], \end{align}\] where the partial derivative of \(\log f\) denotes the score with respect to parameter \(\theta_i\).

Notice that the determinant of FI, which is a natural volume form on a statistical manifold [33], is invariant for all non-singular transformations of the parameters. Here, if \(\eta = g(\theta)\) holds for a differentiable function \(g\), then FI that \(X\) contains about \(\eta\) is given as follows [34]: \[\begin{align} I(\theta) &= \left( \nabla g(\theta) \right) I(\eta) \left( \nabla g(\theta) \right)^\intercal, \\ \det(I(\theta)) &= \det(I(\eta)) \det(\nabla g(\theta))^2, \addtocounter{equation}{1}{\label{eq:32pre95FI95Jacob}} \end{align}\tag{12}\] where \(\nabla g\) denotes the Jacobian matrix of \(g\) and superscript \(^\intercal\) denotes the transpose of a matrix. To satisfy the requirement of the invariance on reparameterization, the Jeffreys prior is defined by \[\pi_{\mathrm{j}}(\theta) \propto \sqrt{\det(I(\theta))}.\] Nevertheless, it is important to note that if the FI regularity conditions outlined below are violated, the FI may not be well-defined, or the FIM can become singular [35].

Definition 2 (FI regularity conditions [35]). The following conditions will be known as the FI regularity conditions:

There exists \(B\) with \(\nu_\theta(B)=0\) such that for all \(\theta\), \(\frac{\partial f_\theta(x)}{\partial \theta_i}\) exists for \(x \notin B\) and each \(i\).
\(\int f_\theta(x) \mathrm{d}\nu_\theta(x)\) can be differentiated under the integral sign with respect to each coordinate of \(\theta\).
The support of \(f_\theta\) is the same for all \(\theta \in \Theta\).

When the FI regularity conditions hold, it is known that the FI matrix defined in (1) has alternative expressions that are more convenient to compute. If the FI regularity conditions hold, it holds for any \(i\in [d]\) that \[\mathbb{E}_\theta\left[ \frac{\partial}{\partial \theta_i} \log f_{\theta}(X) \right] = 0.\] Therefore, FI can be written as follows [32]: \[I(\theta)_{ij} = \mathrm{cov}_\theta \left[ \frac{\partial}{\partial \theta_i} \log f_\theta(X), \frac{\partial}{\partial \theta_j} \log f_\theta(X)\right],\] which recovers the definition of FI in [35]. In addition, if \(f_\theta\) is twice differentiable with respect to \(\theta\), then it coincides with the negative expected value of the Hessian matrix of \(\log f(X| \boldsymbol{\theta})\), i.e., \[I(\theta) = - \mathbb{E}_\theta\left[ \frac{\partial^2}{\partial \theta^2} \log f_{\theta}(X) \right].\] Therefore, if FI regularity conditions hold, one can compute the FI matrix easily and can use it to derive the Jeffreys prior.

Although the Jeffreys prior is widely applicable, it cannot be generalized to the models that do not satisfy some of the FI regularity conditions. Additionally, the Jeffreys prior is known to perform poorly in some inference tasks when the model contains nuisance parameters [11], [36]. These observations cast doubts on the reliability of the Jeffreys prior as a guideline prior, despite its desirable properties in regular models without nuisance parameters.

7.4 Reference Priors↩︎

To develop a method of noninformative priors that can be applied in almost any situation, [37] proposed a reference prior approach, where the general derivations of the reference prior were described by four steps [14]. The reference priors coincide with the Jeffreys prior for continuous parameter space without any nuisance parameters, and with the uniform prior for finite parameter space with sufficient regularity [5]. Importantly, the reference prior solves the inferential problems that the Jeffreys prior cannot [14], and it exhibits invariance under one-to-one reparameterization that preserves the group order of parameters [8].

Although the derivation of the reference prior is not simple in general, it can be easily computed based on the FIM when it is a block diagonal matrix.

Lemma 1 (Theorem 1 of [36]). Suppose that the parameters \(\theta = (\theta_1, \ldots ,\theta_d) \in \Theta\) is group ordered as \(\theta = \{ \theta_{(1)}, \ldots, \theta_{(m)} \}\), where \(\theta_{(m)}\) has \(d_i\) coordinates and \(\sum_{i=1}^m d_i = d\). Here, the subscript \((i)\) represents a prioritization of inference, where there is greater interest in inference regarding \(\theta_{(i)}\) than in \(\theta_{(i+1)}\), and where all \(\theta_{j}\) in the same group have equal importance⁴. For \(\theta_{\sim(j)} = (\theta_{(1)}, \ldots, \theta_{(j-1)},\theta_{(j+1)}, \theta_{(m)} )\), assume that

\(I(\theta) = \mathrm{diag}(h_1(\theta), \ldots, h_m(\theta))\), where \(h_1(\theta)\) is \(d_1 \times d_1\) matrix than is not necessarily diagonal.
\(\det(h_j(\theta)) = h_{j1}(\theta_{(j)}) h_{j2}(\theta_{\sim(j)})\) for nonnegative functions \(h_{j1}\) and \(h_{j2}\).

Then, \[\label{eq:32pre95def95ref95ort} \pi_{\mathrm{r}}(\theta) = \prod_{j=1}^m \sqrt{h_{j1}(\theta_{(j)})}.\tag{13}\]

Notice that the formulation for the reference prior based on the FIM in (13 ) is enough to consider the bandit models in this paper, similar to previous studies [12], [13].

7.5 Probability Matching Priors↩︎

The probability matching prior is a type of noninformative prior that is designed to achieve the synthesis between the coverage probability of the Bayesian interval estimates and that of the frequentist interval estimates [18], [38]. Therefore, the posterior probability of certain intervals matches exactly or asymptotically the frequentist’s coverage probability under the probability matching prior.

Although several matching priors have been developed under slightly different considerations [20], we introduce the quantile matching prior, which is a common approach [6], [11]. The quantile matching prior aims to achieve a synthesis between the credible interval and confidence interval. For any priors \(\pi\), suppose that \[\mathbb{P}_{\theta \sim \pi} [ \theta \in C_{\alpha} \mid X] = \int \mathbb{P}[\theta \in C_{\alpha}] \pi(\theta) \mathrm{d}\theta = 1-\alpha\] for \(\alpha\in (0,1)\) and a set \(C_{\alpha} \subset \Theta\). When the prior is a probability matching prior, \(\pi_{\mathrm{pm}}\), it holds that \[\label{eq:32par95def95pmp} \mathbb{P}[\theta \in C_{\alpha}] = \alpha + \mathcal{O}(n^{-(k+1)/2}).\tag{14}\] A prior satisfying (14 ) is called the \(k\)-th order matching prior⁵. Any positive continuous prior \(\pi\) satisfies the zeroth order matching property from the first-order quadratic approximation, which shows the equivalence of frequentist and Bayesian normal approximation up to \(\mathcal{O}(n^{-1/2})\). Furthermore, the first-order matching prior is known to be invariant under one-to-one reparameterization [8]. If there are no additional terms in (14 ), such a prior is called an exact matching prior.

When there are no nuisance parameters, the Jeffreys prior is known to be the unique first-order matching prior [20]. In the presence of the nuisance parameters, [42] showed that the first-order matching prior is equivalent to the solution of a partial differential equation. Therefore, it is usually difficult to derive the probability matching priors, which becomes more complex when one considers the multiparameter models. Nevertheless, when the FI matrix is diagonal, the unique first-order joint probability matching prior is given as follows [39]: \[\pi_{\mathrm{jpm}}(\theta) \propto \prod_{j=1}^d \sqrt{h_{j1}(\theta_j)},\] which is the same as the reference prior given in (13 ) when every parameter group is a singleton. Furthermore, when \(\theta_1\) is a parameter of interest and \(\theta_{\sim(1)} = (\theta_2, \ldots, \theta_d)\) is a vector of nuisance parameters, the first-order probability matching prior is given as follows [18], [19]: \[\label{eq:32pre95def95pm} \pi_{\mathrm{pm}}(\theta) = g(\theta_{\sim (1)}) \sqrt{h_{11}(\theta)},\tag{15}\] where \(g(\cdot)\) is an arbitrary positive function. For the LS family, it is known that the unique second-order probability matching prior is given as \(\pi_{\mathrm{pm}}(l,s) \propto \sigma^{-1}\) regardless of orthogonality [20]. Furthermore, [40] showed that \(\sigma^{-1}\) yields exact conditional matching in the univariate LS family regardless of parameters of interest.

8 Additional Discussions↩︎

Here, we provide additional discussions on the results of this paper and the future investigations.

8.1 The Choice Priors for Multiparameter Models↩︎

For the uniform bandits and the Gaussian bandits, the uniform prior with LS parameterization is shown to be asymptotically optimal, while the reference prior and the Jeffreys prior are suboptimal. We further show that the uniform prior with location-rate parameterization coincides with the Jeffreys prior in the LS family, which shows the importance of the way to parameterize the statistical model when one uses the uniform prior. Furthermore, in the Pareto bandits, the uniform prior with scale-shape parameterizations are shown to be worse than the reference priors [13] and Corollary 1 further showed the suboptimality of the uniform prior with rate-shape parameterizations, which is even worse than the Jeffreys prior. Therefore, using the uniform prior as a baseline prior could be problematic since its performance highly depends on the parameterizations. On the other hand, in the analysis of the uniform, Gaussian, and Pareto bandits, the reference priors are shown to be on the borderline between optimal and suboptimal in terms of prior parameter \(k\) [12], [13]. Therefore, TS with the reference prior can serve as a baseline for general bandit models since the reference posterior can be generally derived via reference analysis [14], [43] and one might expect that an optimal policy would perform better than TS with the reference priors. Furthermore, by combining with TS-T, one can focus on the design of adaptive truncation rather than finding an optimal prior, which would be easier.

8.2 The Choice of Priors and Minimax Optimality↩︎

This paper focused on the asymptotic optimality of TS with different choices of noninformative priors in the multiparameter reward models. In the current stage, the reference priors have been shown to be on the borderline between optimal priors and suboptimal priors in terms of prior parameter \(k\) for all three different models studied so far. Although such observations partially answered the research question in this paper, the full answer can be obtained with the problem-independent analysis (a.k.a. worst-case analysis) since Gaussian prior was shown to be better than the Beta priors in the Bernoulli bandits where both priors are shown to be minimax suboptimal [24]. On the other hand, [15] showed that post-processed posterior sampling with the uniform prior was shown to achieve both minimax and asymptotic optimality simultaneously, and [44] showed a simple trick can make TS achieve both optimality with a specific prior for some single-parameter exponential models. Therefore, we expect that combining their techniques with TS-T can provide a minimax and asymptotically optimal solution to the multiparameter bandit models. However, in the regret analysis of this paper, the regret upper bound exhibits the dependency of scale \(\sigma\), which might be problematic when one considers the worst-case scenario and might require more careful analysis than the usual analysis in the single-parameter exponential family where \(\sigma\) is given and fixed [15], [24], [44].

9 Derivation of the Posteriors for the Uniform Bandits↩︎

Here, we provide the detailed derivation of the posteriors based on the priors \(\sigma^{-k}\).

Let \(X_n = (x_1, \ldots, x_n)\) denote the \(n\) observations of an arm. Then, it holds that \[\prod_{s=1}^n f_{\mu, \sigma}(x_s) = \frac{1}{\sigma^{n}} \boldsymbol{1}\left[ \mu - \frac{\sigma}{2} \leq x^{(1)} \leq x^{(n)} \leq \mu + \frac{\sigma}{2} \right],\] where \(x^{(1)} = \min_{s \in [n]} x_s\) and \(x^{(n)} = \max_{s \in [n]} x_s\) denotes the smallest and the largest order statistics. Since it holds that \[\begin{align} &\boldsymbol{1}\left[ \mu - \frac{\sigma}{2} \leq x^{(1)} \leq x^{(n)} \leq \mu + \frac{\sigma}{2} \right] = \boldsymbol{1}\left[ x^{(n)} - \frac{\sigma}{2} \leq \mu \leq x^{(1)} + \frac{\sigma}{2}\right] \boldsymbol{1}[\sigma\geq x^{(n)}-x^{(1)}], \end{align}\] one can obtain for \(\hat{\sigma}_n = x^{(n)}-x^{(1)}\) that \[\begin{align} \iint \frac{1}{\sigma^k}\prod_{s=1}^n f_{{\mu, \sigma}}(x_{s}) \mathrm{d}\mu \mathrm{d}\sigma &= \int_{\hat{\sigma}_n}^{\infty} \frac{\sigma- \hat{\sigma}_n}{\sigma^{n+k}} \mathrm{d}\sigma\\ &= \frac{1}{(n+k-1)(n+k-2)}\frac{1}{(\hat{\sigma}_n)^{n+k-2}}. \end{align}\] Therefore, by letting \(n_k = n+k-2\), the joint posterior density can be written as \[\begin{align} \pi^k({\mu, \sigma}\mid X_n) = n_k(n_k+1) \frac{(\hat{\sigma}_n)^{n_k}}{\sigma^{n_k+2}} \boldsymbol{1}\left[ \mu - \frac{\sigma}{2} \leq x^{(1)} \leq x^{(n)} \leq \mu + \frac{\sigma}{2} \right]. \end{align}\] By marginalizing with respect to \(\mu\), one can obtain the marginal posterior density of \(\sigma\), \[\begin{align} \pi^k(\sigma\mid X_n) =n_k(n_k+1) \frac{(\hat{\sigma}_n)^{n_k}}{\sigma^{n_k+2}} (\sigma- \hat{\sigma}_n) \boldsymbol{1}[\sigma\geq x^{(n)}-x^{(1)}]. \end{align}\] Then, the conditional posterior density of \(\mu\) is written as \[\begin{align} \pi^k(\mu \mid X_n, \sigma) &= \frac{\pi^k({\mu, \sigma}\mid X_n)}{\pi^k(\sigma\mid X_n)} \\ &= \frac{1}{\sigma- \hat{\sigma}_n} \boldsymbol{1}\left[ x^{(n)} - \frac{\sigma}{2} \leq \mu \leq x^{(1)} + \frac{\sigma}{2}\right], \end{align}\] which is the density function of \(\mathrm{Uni}_{ab}\left(x^{(n)}-\frac{\sigma}{2}, x^{(1)}+\frac{\sigma}{2}\right)\).

10 Proofs of the Optimality of TS and TS-T↩︎

In this section, we first provide a general proof outline that applies to our analysis of TS and TS-T in both the uniform bandits and the Gaussian bandits since the overall proofs of Theorems 1, 3, and 4 have a similar structure. The proof of Theorem 2 is postponed to Section 11.

10.1 Proof Outline of Theorems 1, 3, and 4 ↩︎

The overall regret decomposition presented here follows the conventional approaches [10], [12], [13], [24], [45]. However, it is worth noting that the detailed derivation requires different techniques to handle the model-dependent difficulties.

At the round \(t\), we denote the best arm under the posterior sample by \(\tilde{\mu}^* (t)=\max_{i \in [K]}\tilde{\mu}_i(t)\), which is computed as the maximum of the sampled expected rewards of all \(K\) arms at round \(t\). We use the notation \(\mathcal{M}_{\epsilon}(t)\) to denote an event related to \(\tilde{\mu}^*(t)\) at round \(t\), which we define for a small positive constant \(\epsilon\) as \[\mathcal{M}_{\epsilon}(t) = \left\{ \tilde{\mu}^*(t) \geq \mu_1 - \epsilon\right\}.\] Then, the proof starts by decomposing the regret as follows: \[\begin{align} \mathrm{Reg}(T) &= \sum_{t=1}^{T} \Delta_{i(t)} = \sum_{i=2}^K \Delta_{i} \boldsymbol{1}[i(t)=i] \\ &\leq \sum_{i=2}^K \Delta_in_0+ \underbrace{ \sum_{t=Kn_0+1}^T \Delta_{\mathrm{max}} \boldsymbol{1}[\mathcal{M}_\epsilon^c(t)]}_{\text{bad optimal (BO) term}} + \underbrace{\sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \boldsymbol{1}[i(t)=i, \mathcal{M}_\epsilon(t)]}_{\text{good optimal (GO) term }}, \addtocounter{equation}{1}{\label{eq:32general95regret95decomp}} \end{align}\tag{16}\] where \(n_0\) and the superscript “\(c\)” denote the number of initial plays and the complementary set, respectively.

\((\mathrm{BO})\) controls the regret induced when the sampled mean parameter of the optimal arm is less than its true value, and \((\mathrm{GO})\) contains the exploration term that becomes the main regret term. Note that \(\mathrm{(BO)}\) is the main difficulty term of the regret analysis of TS in many bandit models.

10.1.1 Uniform Bandits↩︎

The lemmas below conclude the proof of Theorems 1 and 3, which shows the asymptotic optimality of TS and TS-T for the uniform models with unknown supports.

Lemma 2. For the \(K\)-armed uniform bandit models, it holds under TS \[\begin{align} \mathbb{E}[(\mathrm{GO})] \leq \sum_{i=2}^{K} \Delta_i\Bigg( \frac{ \log T}{\log\left( 1 + \frac{2\Delta_i-4\epsilon}{\sigma_i} \right)} + \frac{2\sigma_i}{\epsilon} + \max\left( \frac{1}{2}, \frac{5}{2}- k \right) \Bigg) \end{align}\] and under TS-T that \[\begin{align} \mathbb{E}[(\mathrm{GO})] \leq \sum_{i=2}^{K} \Delta_i\Bigg( \frac{ \log T}{\log\left( 1 + \frac{2\Delta_i-4\epsilon}{\sigma_i} \right)} + \frac{2\sigma_i}{\epsilon} + \frac{1}{\sigma_i} + \frac{3}{2}\Bigg). \end{align}\]

Lemma 3. For the \(K\)-armed uniform bandit models, under TS with \(k < 1\) \[\mathbb{E}[(\mathrm{BO})] \leq \Delta_{\mathrm{max}} C(\epsilon, k , \sigma_1)\] and under TS-T with \(k \in \mathbb{R}\) \[\mathbb{E}[(\mathrm{BO})] \leq \Delta_{\mathrm{max}} C'(\epsilon, k , \sigma_1).\]

In the proof of Lemma 3, our analysis cannot derive the finite upper-bound for TS with \(k\geq 1\), including the reference prior and the Jeffreys prior, where the same problem was observed in the Gaussian models [12]. Although the infinite upper-bound term does not necessarily mean the suboptimality of the policy, Theorem 2 shows that it actually contributes to increasing the regret in expectation. This is because TS could induce a polynomial regret with a small but non-negligible probability, which leads to a larger expected regret. A truncation procedure is introduced to make such a probability ignorable so that \(\mathrm{(BO)}\) can be upper-bounded by a finite term.

10.1.2 Gaussian Bandits↩︎

The lemmas below conclude the proof of Theorem 4, which shows the asymptotic optimality of TS-T for the Gaussian bandits.

Lemma 4. For the \(K\)-armed Gaussian bandit models, it holds under TS-T that \[\begin{align} \mathbb{E}[(\mathrm{GO})] \leq \sum_{i=2}^{K} \Delta_i \Bigg( \frac{ \log T}{\frac{1}{2}\log\left(1 + \frac{(\Delta_i-2\epsilon)^2}{\sigma_i^2+\epsilon}\right)} + \frac{1}{\sigma_i^2 } + 3 -k + \frac{\sqrt{\sigma_i^2+\epsilon}}{\Delta_i - 2\epsilon} + \frac{2\sigma_i^2 e^{\frac{\epsilon}{2\sigma_i^2}}+2\sigma_i^4 e^{\frac{\epsilon}{\sigma_i^2}}}{\epsilon^2} \Bigg). \end{align}\]

Lemma 5. For the \(K\)-armed Gaussian bandit models, it holds under TS-T with prior \(k\leq 2\) that \[\mathbb{E}[(\mathrm{BO})] \leq \Delta_{\mathrm{max}} C''(\epsilon, k, \sigma_1).\]

Although some parts of the proof of Lemmas 4 and 5 can be obtained using the results by [12], the main difficulty comes from the term introduced by the truncated estimators \(\bar{\sigma}\). To be precise, it involves integrating a product of the beta function and the incomplete gamma function. This integration introduces additional functions, such as the modified Bessel function of the second kind and the confluent hypergeometric function of the second kind, which makes the analysis technically more complicated.

10.2 Proof of Lemma 2 ↩︎

Before beginning the proof, we first introduce the result that demonstrates the joint distribution of the order statistics of the uniform distribution. Here, an additional notation in superscript, \(\mathrm{SD}_{\mathrm{U}}\), is used to clarify that it is a density function of the sampling distribution in the uniform models.

Lemma 6 (Lemma 6 in [17]). Let \((x_{i})_{i=1}^n\) be i.i.d. random variables following \(\mathrm{Uni}_{ab}(a,b)\), with finite \(a < b\). For \(n \geq 2\), let \(x^{(n)} = \max_{s\in[n]} x_s\) and \(x^{(1)} = \min_{s\in[n]} x_s\). Then, the joint density of \((x^{(1)}, x^{(n)})\) is given by \[f_n^{\mathrm{SD}_{\mathrm{U}}}( y, z ) = \begin{cases} n(n-1)\frac{(z-y)^{n-2}}{(b-a)^{n}} &\mathrm{if } y \leq z, \\ 0 & \mathrm{otherwise}. \end{cases}\]

Proof. Recall that MLEs \(\hat{\mu}_i(n) = \frac{x^{(1)}_i+x^{(n)}_i}{2}\) and \(\hat{\sigma}_i(n) = x^{(n)}_i - x^{(1)}_i\) are functions of sufficient statistics \(T(X_{i,n})=(x^{(1)}_i, x^{(n)}_i)\). Define events on the order statistic \(x^{(1)}_i\) and \(x^{(n)}_i\), and an event on the truncated statistic \(\bar{x}^{(n)}_i\) of the arm \(i\) at round \(t\) for any positive \(\epsilon< \frac{\Delta_i}{2}\), \[\begin{align} \mathcal{A}_{i,n}(\epsilon) &= \left\{ \mu_i - \frac{\sigma_i}{2} \leq x^{(1)}_i \leq \mu_i - \frac{\sigma_i}{2} + \epsilon\right\} \\ \mathcal{B}_{i,n}(\epsilon) &= \left\{ \mu_i + \frac{\sigma_i}{2} -\epsilon\leq x^{(n)}_i \leq \mu_i + \frac{\sigma_i}{2}\right\}\\ \mathcal{E}_{i,n}(\epsilon) &= \mathcal{A}_{i,n}(\epsilon) \cap \mathcal{B}_{i,n}(\epsilon) \\ \bar{\mathcal{B}}_{i,n}(\epsilon) &= \left\{ \mu_i + \frac{\sigma_i}{2} -\epsilon\leq \bar{x}^{(n)}_i \leq \mu_i + \frac{\sigma_i}{2}\right\} \\ \bar{\mathcal{E}}_{i,n}(\epsilon) &= \mathcal{A}_{i,n}(\epsilon) \cap \bar{\mathcal{B}}_{i,n}(\epsilon). \end{align}\] Then, \((\mathrm{GO})\) is decomposed under TS by \[\begin{align} (\mathrm{GO}) &= \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \boldsymbol{1}\left[i(t)=i, \mathcal{E}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \Delta_i \boldsymbol{1}\left[i(t)=i, \mathcal{E}_{i,N_i(t)}^c(\epsilon), \mathcal{M}_\epsilon(t)\right] \\ &\leq \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \boldsymbol{1}\left[i(t)=i, \mathcal{E}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \Delta_i \boldsymbol{1}\left[i(t)=i, \mathcal{E}_{i,N_i(t)}^c(\epsilon) \right]. \end{align}\] The last equality holds since an event \(\{i(t)=i, N_i(t)=n\}\) occurs only once from the definition \(N_i(t)\). Similarly, \((\mathrm{GO})\) can be decomposed under TS-T by \[\begin{align} (\mathrm{GO}) \leq \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \boldsymbol{1}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \Delta_i \boldsymbol{1}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}^c(\epsilon), \right]. \end{align}\] Then, two lemmas below conclude the proof of Lemma 2, whose proofs are postponed to Section 10.4. ◻

Lemma 7. For all \(i \in [K]\) and \(n \in \mathbb{N}_{\geq 2}\), it holds that \[\begin{align} \mathbb{P}\left[\bar{\mathcal{E}}_{i,n}^c(\epsilon)\right] \leq \mathbb{P}[\mathcal{E}_{i,n}^c(\epsilon)] \leq 2\exp(-\frac{\epsilon}{\sigma_i}n). \end{align}\]

Lemma 8. Under TS, it holds that for any \(i \in [K]\) and given \(\epsilon\in \left( 0, \frac{\Delta_i}{2}\right)\) \[\begin{align} \sum_{t=n_0K+1}^T \mathbb{E}[\boldsymbol{1}[i(t)=i, \mathcal{E}_{i,N_i(t)}(\epsilon), \mathcal{M}_{\epsilon}(t) ]] \leq \max\left(\frac{1}{2},\frac{5}{2}-k\right)+\frac{\log T}{\log\left( 1 + \frac{2\Delta_i-4\epsilon}{\sigma_i} \right)}. \end{align}\] and under TS-T, \[\begin{align} \sum_{t=n_0K+1}^T \mathbb{E}[\boldsymbol{1}[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_{\epsilon}(t) ]] \leq \frac{3}{2} + \frac{1}{\sigma_i}+ \frac{\log T}{\log\left( 1 + \frac{2\Delta_i-4\epsilon}{\sigma_i} \right)}. \end{align}\]

10.3 Proof of Lemma 3 ↩︎

Proof. For a event \(\{ i(t)\ne 1,\mathcal{M}_\epsilon^c(t), N_1(t) =n \}\) Let us consider the following decomposition: \[\begin{align} \sum_{t=Kn_0+1}^T \boldsymbol{1}[i(t)\ne 1, \mathcal{M}_\epsilon^c(t)] &= \sum_{n=n_0}^T \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1,\mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg] \\ &= \sum_{n=n_0}^T \sum_{m=1}^T \boldsymbol{1}\Bigg[m \leq \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg]\Bigg]. \end{align}\] Notice that \[m \leq \sum_{t=Kn_0+ 1}^T \boldsymbol{1}[i(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) =n]\] implies that \(\tilde{\mu}_1(t) \leq \max_{i\in[K]} \tilde{\mu}_i(t) \leq \mu_1 -\epsilon\) occurred \(m\) times in a row on \(\{t: \mathcal{M}_\epsilon^c(t), N_1(t) =n \}\). Therefore, we obtain that \[(\mathrm{BO}) \leq \sum_{i=2}^K \sum_{n=n_0}^T \sum_{m=1}^T \Delta_i \boldsymbol{1}\Bigg[m \leq \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg]\Bigg].\] Firstly, we provide the upper bound of \(\mathbb{E}[(\mathrm{BO})]\) under TS.

10.3.1 Under TS↩︎

Let us define \(p_n(y| {\theta}_{1,n}) = \mathbb{P}\left[\tilde{\mu}_1 \geq \mu_1 - y \,\middle\vert\, x^{(1)}_1, x^{(n)}_1\right]\), where \(p_n(\epsilon|\theta_{1,n})\) denote the probability that \(\mathcal{M}_\epsilon(t)\) occurs given sufficient statistics \(\theta_{1,n} = T(X_{i,n})\) where \(N_1(t)=n\). Therefore, we have \[\begin{align} \mathbb{E}[(\mathrm{BO})] &\leq \sum_{i=2}^K \sum_{n=n_0}^T \sum_{m=1}^T \Delta_i \mathbb{P}\Bigg[m \leq \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg]\Bigg] \\ &\leq \sum_{i=2}^K \sum_{n=n_0}^T \mathbb{E}_{\theta_{1,n}} \left[ \sum_{m=1}^T (1-p_n(\epsilon|{\theta}_{1,n}))^m \right] \addtocounter{equation}{1}{\label{eq:32uni95BO95U95TS95total95exp}} \\ &\leq \sum_{n=n_0}^T \mathbb{E}_{\theta_{1,n}}\left[ \frac{1-p_n(\epsilon|{\theta}_{1,n})}{p_n(\epsilon|{\theta}_{1,n})} \right], \end{align}\tag{17}\] where we utilized the total law of expectation in (17 ). From now on, we fix \(n\) so that \((\tilde{\mu}_1, \tilde{\sigma}_1)\) are sampled from the same posterior parameterized by fixed \((\hat{\mu}_{1,n}, \hat{\sigma}_{1,n})\) and drop the subscript \(\theta_{1,n}\) of \(\mathbb{E}_{\theta_{1,n}}\) for simplicity. Therefore, \(\tilde{\sigma}_1 \geq \hat{\sigma}_{1,n} = x^{(n)}_1 - x^{(1)}_1\) holds from its marginal posterior in (6 ), which implies the existence of a positive random variable \(D\) satisfying \(\tilde{\sigma}_1 = x^{(n)} - x^{(1)} + D\). From the sequential sampling with posteriors in (6 ) and (7 ), it holds that \(\tilde{\mu}_1 \sim \mathrm{Uni}_{\mu\sigma}\left( \frac{x^{(1)}_1 + x^{(n)}_1}{2}, D \right)\). Therefore, if \(\frac{x^{(1)}_1 + x^{(n)}_1}{2} \geq\mu_1 - \epsilon\), \(p_n(\epsilon| \theta_{1,n}) \geq \frac{1}{2}\) holds regardless the value of \(D\). Since \(\frac{x^{(1)}_1 + x^{(n)}_1}{2} \geq \mu_1 - \frac{\epsilon}{2}\) holds on \(\mathcal{E}_{1,n}(\epsilon)\), we obtain \[\begin{align} \mathbb{E}\left[ \frac{1-p_n(\epsilon|{\theta}_{1,n})}{p_n(\epsilon|{\theta}_{1,n})} \right] &\leq 2\mathbb{E}\left[ \boldsymbol{1}\left[ x^{(1)}_1 + x^{(n)}_1 \geq 2(\mu_1 - \epsilon) \right](1-p_n(\epsilon|{\theta}_{1,n}))\right] + \mathbb{E}\left[ \frac{\boldsymbol{1}\left[ x^{(1)}_1 + x^{(n)}_1 \leq 2(\mu_1 - \epsilon) \right]}{p_n(\epsilon|\theta_{1,n})} \right] \\ &\leq 2\mathbb{P}\left( \mathcal{E}_{1,n}^c\left(\frac{\epsilon}{2} \right)\right) + 2\mathbb{E}\left[\boldsymbol{1}\left[\mathcal{E}_{1,n}\left(\frac{\epsilon}{2} \right) \right] (1-p_n(\epsilon|\theta_{1,n})) \right] + \mathbb{E}\left[ \frac{\boldsymbol{1}\left[ x^{(1)}_1+ x^{(n)}_1 \leq 2(\mu_1 - \epsilon) \right]}{p_n(\epsilon|\theta_{1,n})} \right]. \addtocounter{equation}{1}{\label{eq:32uni95diff95decom95TS}} \end{align}\tag{18}\] From Lemma 7, the first term of (18 ) can be bounded as \[\begin{align} \label{eq:32uni95diff95first95TS} 2\mathbb{P}\left( \mathcal{E}_{1,n}^c\left(\frac{\epsilon}{2} \right)\right) &\leq 4e^{-\frac{\epsilon}{2\sigma_1}n}. \end{align}\tag{19}\] Since \(\tilde{\mu}_1 | \tilde{\sigma}_1 \sim \mathrm{Uni}_{ab}\left(x^{(n)}_1 - \frac{\tilde{\sigma}_1}{2}, x^{(1)}_1 + \frac{\tilde{\sigma}_1}{2} \right)\), we have \[x^{(n)}_1 - \frac{\tilde{\sigma}_1}{2} \geq \mu_1 - \epsilon\Leftrightarrow \tilde{\sigma}_1 \leq 2(x^{(n)}_1 - (\mu_1 - \epsilon)) \implies 1-p_n(\epsilon|\theta_{1,n}) = 0.\] For a constant \(A = x^{(n)}_1 - (\mu_1 - \epsilon)\), we can bound the second term of (18 ) as \[\begin{align} \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg]\bigg(1-p_n(\epsilon|\theta_{1,n})\bigg) &= \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg] \int_{2A}^{\infty} \pi^{k}(s|\theta_{1,n})\int_{x^{(n)}_1-\frac{s}{2}}^{\mu_1 - \epsilon} \pi^{k}(m|\theta_{1,n}, \tilde{\sigma}_1 = s) \mathrm{d}m \mathrm{d}s \\ &= \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg] \int_{2A}^{\infty} \frac{(n+k-1)(n+k-2)\left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n+k-2}}{s^{n+k}} \\ &\cdot \left(s-(x^{(n)}_{1}-x^{(1)}_{1})\right) \int_{x^{(n)}_1-\frac{s}{2}}^{\mu_1 - \epsilon} f_{\hat{\mu}_{1,n}, s-\hat{\sigma}_{1,n}}^{\mathrm{U}_{\mu\sigma}} (m) \mathrm{d}m \mathrm{d}s \\ &= \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg] \int_{2A}^{\infty} \frac{(n+k-1)(n+k-2)\left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n+k-2}}{s^{n+k}} \\ &\cdot \left(s-(x^{(n)}_{1}-x^{(1)}_{1})\right) \frac{1}{s-x^{(n)}_{1}-x^{(1)}_{1}}\left(\frac{ s -2A}{2}\right) \mathrm{d}s \\ &= \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg] \int_{2A}^{\infty} \frac{(n+k-1)(n+k-2)\left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n+k-2}}{s^{n+k}} \left(\frac{ s -2A}{2}\right) \mathrm{d}s\\ &= \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg]\frac{1}{2}\left(\frac{x^{(n)}_1-x^{(1)}_1}{2\left(x^{(n)}_1-\mu_1+\epsilon\right)} \right)^{n+k-2}. \end{align}\] Since \(x^{(n)}_1 \geq \mu_1 + \frac{\sigma_1}{2} - \frac{\epsilon}{2}\) and \(x^{(n)}_1 -x^{(1)}_1 \leq \sigma_1\) hold for any \(n\) on \(\mathcal{E}_{1,n}(\epsilon/2)\), we have \[\begin{align} \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg]\left(1-p_n(\epsilon|\theta_{1,n})\right) &\leq \boldsymbol{1}\bigg[\mathcal{E}_{1,n}(\epsilon/2)\bigg]\frac{1}{2}\left(\frac{x^{(n)}_1-x^{(1)}_1}{2\left(x^{(n)}_1-\mu_1+\epsilon\right)} \right)^{n+k-2} \\ &\leq \frac{1}{2}\left( \frac{\sigma_1}{\sigma_1 +\epsilon}\right)^{n+k-2} \leq \frac{1}{2}e^{- \frac{\epsilon}{\sigma_1+\epsilon}(n+k-2)}. \end{align}\] Therefore, the second term of (18 ) is bounded as \[\label{eq:32uni95diff95second95TS} 2\mathbb{E}\left[\boldsymbol{1}\left[\mathcal{E}_{1,n}\left(\frac{\epsilon}{2} \right) \right] (1-p_n(\epsilon|\theta_{1,n})) \right] \leq e^{- \frac{\epsilon}{\sigma_1+\epsilon}(n+k-2)}.\tag{20}\] Finally, we evaluate the last term of (18 ). From the conditional posterior of \(\mu\), we have \[\tilde{\mu}_1 | \tilde{\sigma}_1 \sim \mathrm{Uni}_{ab}\left(x^{(n)}_1 - \frac{\tilde{\sigma}_1}{2}, x^{(1)}_1 + \frac{\tilde{\sigma}_1}{2} \right),\] which gives that \[\begin{align} \boldsymbol{1}\left[ x^{(1)}_1 + x^{(n)}_1 \leq 2(\mu - \epsilon) \right]&\mathbb{P}[\tilde{\mu}_1 \geq \mu_1 -\epsilon| \theta_{1,n}, \sigma = \tilde{\sigma}_1] \\ &= \boldsymbol{1}\left[ x^{(1)}_1 + x^{(n)}_1 \leq 2(\mu_1 - \epsilon) \right] \cdot \begin{cases} 0 &\mathrm{if}x^{(1)}_1 + \frac{\tilde{\sigma}_1}{2} \leq \mu_1 - \epsilon, \\ \frac{x^{(1)}_1+\tilde{\sigma}_1/2-(\mu_1 - \epsilon)}{\tilde{\sigma}_1 - \left( \bar{x}^{(n)}_{1}-x^{(1)}_{1} \right)} & \mathrm{otherwise}. \end{cases} \end{align}\] For simplicity in notation, we denote the event \(\{x^{(1)}_1 + x^{(n)}_1 \leq 2(\mu_1 - \epsilon)\}\) by \(\mathcal{T}\). For a constant \(A' = \mu_1 - \epsilon- x^{(1)}_1\), it holds that \[\begin{align} \boldsymbol{1}\bigg[ x^{(1)}_1 + x^{(n)}_1 \leq 2(\mu_1 - \epsilon) \bigg]p_n(\epsilon|\theta_{1,n})&= \boldsymbol{1}\left[ \mathcal{T} \right] \int_{2(\mu_1 -\epsilon-x^{(1)}_1)}^{\infty} \pi^{k}(s|\theta_{1,n})\frac{x^{(1)}_1+s/2-(\mu_1 - \epsilon)}{s - \left( \bar{x}^{(n)}_{1}-x^{(1)}_{1} \right)} \mathrm{d}s \\ &= \boldsymbol{1}\left[ \mathcal{T} \right] \int_{2A'}^{\infty} \frac{(n+k-1)(n+k-2)\left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n+k-2}}{s^{n+k}} \\ &\cdot \left(s-(x^{(n)}_{1}-x^{(1)}_{1})\right) \frac{x^{(1)}_1+\frac{s}{2}-(\mu_1 - \epsilon)}{s - \left( x^{(n)}_{1}-x^{(1)}_{1} \right)} \mathrm{d}s \\ &= \boldsymbol{1}\left[ \mathcal{T} \right] \int_{2A'}^{\infty} (n+k-1)(n+k-2) \\ & \cdot \frac{x^{(1)}_1+\frac{s}{2}-(\mu_1 - \epsilon)}{s^{n+k}} \left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n+k-2} \mathrm{d}s \\ & = \boldsymbol{1}\left[ \mathcal{T} \right] \frac{(n+k-1)(n+k-2) \left(x^{(n)}_{1}-x^{(1)}_{1}\right)^{n-1}}{2}\int_{2A'}^{\infty} \frac{s-2A'}{s^{n+k}} \mathrm{d}s\\ & = \boldsymbol{1}\left[ \mathcal{T}\right] \frac{1}{2}\left( \frac{x^{(n)}_{1}-x^{(1)}_{1}}{2A'} \right)^{n+k-2} = \boldsymbol{1}\left[ \mathcal{T}\right] \frac{1}{2}\left( \frac{x^{(n)}_{1}-x^{(1)}_{1}}{2(\mu_1 -\epsilon- x^{(1)}_1)} \right)^{n+k-2}. \end{align}\] Taking expectations gives that \[\begin{align} \mathbb{E}\left[ \frac{\boldsymbol{1}\bigg[ \mathcal{T} \bigg]}{p_n(\epsilon|\theta_{1,n})} \right]&= 2\underbrace{\mathbb{E}\left[ \boldsymbol{1}\left[ \mathcal{T}\right] \left( \frac{2(\mu_1-\epsilon-x^{(1)}_1)}{x^{(n)}_1 - x^{(1)}_1} \right)^{n+k-2} \right]}_{(\star_{\mathrm{U}})} \addtocounter{equation}{1}{\label{eq:32uni95star95TS}} \\ & = 2\int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y}^{\min(2(\mu_1-\epsilon-y), \mu_1+\frac{\sigma_1}{2})} f_n^{\mathrm{SD}_{\mathrm{U}}} (y,z) \mathrm{d}z \mathrm{d}y. \end{align}\tag{21}\] By injecting the sampling distributions of the order statistics in Lemma 6, we obtain that \[\begin{align} (\star_{\mathrm{U}}) = \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y}^{\min(2(\mu_1-\epsilon-y), \mu_1+\frac{\sigma_1}{2})} \frac{n(n-1)}{\sigma_1^n}(z-y)^{n-2} \cdot \left( \frac{2(\mu-\epsilon-y)}{z - y} \right)^{n+k-2} \mathrm{d}z \mathrm{d}y. \end{align}\] Therefore, we have that \[\begin{align} (\star_{\mathrm{U}}) &\leq \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n}(z-y)^{n-2} \left( \frac{2(\mu_1-\epsilon-y)}{z - y} \right)^{n+k-2} \mathrm{d}z \mathrm{d}y \\ &= \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n} \frac{\left(2(\mu_1-\epsilon-y) \right)^{n+k-2}}{(z-y)^k} \mathrm{d}z \mathrm{d}y \addtocounter{equation}{1}{\label{eq:32why95trun1}} \\ & =\int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \frac{n(n-1)}{\sigma_1^n} \left(2(\mu_1-\epsilon-y) \right)^{n+k-2} \left( 2(\mu_1-\epsilon-y) - y \right)^{1-k} \mathrm{d}y\text{if } k< 1. \end{align}\tag{22}\] Note that under TS with \(k\geq 1\), the integral in (22 ) with respect to \(z\) becomes infinite due to \(z-y = 0\), which implies that our analysis does not result in a finite upper bound for \(k \geq 1\). One can avoid such infinite terms by modifying the domain of the integral with respect to \(z\) from \([y, 2(mu_1 - \epsilon-y)\) to \([y+\alpha, 2(\mu_1 - \epsilon-y)]\) for some \(\alpha>0\). Since \(f_n(y,z)\) is the joint density of \((x^{(1)}, x^{(n)})\), the domain restriction on \(z\) can be interpreted as an additional restriction \(x^{(n)}\geq x^{(1)} + \alpha\), which motivates us to design the TS-T policy.

By defining \(w=2(\mu_1-\epsilon- y)\), we can obtain for \(k <1\) that \[\begin{align} (\star_{\mathrm{U}}) &\leq \frac{n(n-1)}{2(1-k)\sigma_1^n} \int_{0}^{\sigma_1 - 2\epsilon} \left( w- \left( \mu_1 - \epsilon- \frac{w}{2} \right)\right)^{1-k} w^{n+k-2} \mathrm{d}w \\ &\leq \frac{n(n-1)}{2(1-k)\sigma_1^n} \int_{0}^{\sigma_1 - 2\epsilon} \left(\frac{3w}{2}\right)^{1-k} w^{n+k-2} \mathrm{d}w \\ &= \frac{3(n-1)}{4(1-k)\sigma_1^n} (\sigma-2\epsilon)^{n} = \frac{3(n-1)}{4(1-k)} \left(1 - \frac{2\epsilon}{\sigma_1} \right)^n\\ &\leq \frac{3(n-1)}{4(1-k)} e^{-\frac{2\epsilon}{\sigma_1}n}. \addtocounter{equation}{1}{\label{eq:32TS95main95star}} \end{align}\tag{23}\] Therefore, by combining (19 ), (20 ), and (23 ) with (18 ) and (17 ), we have for \(\epsilon\in \left(0, \min_{i \ne 1}\frac{\Delta_i}{2}\right)\) and \(k<1\) that \[\begin{align} \sum_{n=n_0}^T \mathbb{E}\left[ \frac{1-p_n(\epsilon|{\theta}_{1,n})}{p_n(\epsilon|{\theta}_{1,n})} \right] &\leq \sum_{n=n_0}^T 4e^{-\frac{\epsilon}{2\sigma_1}n} + e^{-\frac{\epsilon}{\sigma_1+\epsilon}(n-1)} + \frac{3(n-1)}{4(1-k)} e^{- \frac{2\epsilon}{\sigma_1}n} \\ &\leq \frac{8\sigma_1}{\epsilon} + \frac{\sigma_1 + \epsilon}{\epsilon} + \frac{3}{16(1-k)} \frac{\sigma_1^2}{\epsilon^2}\left(2e^{\frac{2\epsilon}{\sigma_1}}-1\right) \\ &=: C(\epsilon, k,\sigma_1) = \mathcal{O}\left(\frac{\sigma_1^2}{(1-k)\epsilon^2}\right), \end{align}\] which concludes the proof of Lemma 3 for the case of TS.

10.3.2 Under TS-T↩︎

The overall proofs are the same as that of TS, except we replace \(p_n(\cdot)\) with \(\bar{p}_n(y| {\theta}_{1,n}) = p_n(y|\bar{\theta}_{1,n}) = \mathbb{P}[\tilde{\mu}_1 \geq \mu_1 - y | x^{(1)}_1, \bar{x}^{(n)}_1]\) and replace \(x^{(n)}\) with \(\bar{x}^{(1)}\). Similarly to (17 ) in TS, we have for TS-T that \[\begin{align} \mathbb{E}\Bigg[ \sum_{t=Kn_0+1}^T \boldsymbol{1}[i(t)\ne 1, \mathcal{M}_\epsilon^c(t)] \Bigg] &\leq \mathbb{E}\left[ \sum_{n=n_0}^T \sum_{m=1}^T (1-\bar{p}_n(\epsilon|{\theta}_{1,n}))^m \right] \\ &\leq \sum_{n=n_0}^T \mathbb{E}\left[ \frac{1-\bar{p}_n(\epsilon|{\theta}_{1,n})}{\bar{p}_n(\epsilon|{\theta}_{1,n})} \right]. \addtocounter{equation}{1}{\label{eq:32uni95BO95U95TST95total95exp}} \end{align}\tag{24}\] By following the same steps as (18 ), we obtain that \[\begin{align} \mathbb{E}\left[ \frac{1-\bar{p}_n(\epsilon|{\theta}_{1,n})}{\bar{p}_n(\epsilon|{\theta}_{1,n})} \right] &\leq 2\mathbb{E}\left[ \boldsymbol{1}\left[ x^{(1)}_1 + \bar{x}^{(n)}_1 \geq 2(\mu_1 - \epsilon) \right](1-\bar{p}_n(\epsilon|{\theta}_{1,n}))\right] + \mathbb{E}\left[ \frac{\boldsymbol{1}\left[ x^{(1)}_1 + \bar{x}^{(n)}_1 \leq 2(\mu_1 - \epsilon) \right]}{\bar{p}_n(\epsilon|\theta_{1,n})} \right] \\ &\leq 2\mathbb{P}\left( \bar{\mathcal{E}}_{1,n}^c\left(\frac{\epsilon}{2} \right)\right) + 2\mathbb{E}\left[\boldsymbol{1}\left[\bar{\mathcal{E}}_{1,n}\left(\frac{\epsilon}{2} \right) \right] (1-\bar{p}_n(\epsilon|\theta_{1,n})) \right] + \mathbb{E}\left[ \frac{\boldsymbol{1}\left[ x^{(1)}_1+ \bar{x}^{(n)}_1 \leq 2(\mu_1 - \epsilon) \right]}{\bar{p}_n(\epsilon|\theta_{1,n})} \right]. \addtocounter{equation}{1}{\label{eq:32uni95diff95decom95TST}} \end{align}\tag{25}\] From Lemma 7, the first term of (25 ) can be bounded as \[\begin{align} \label{eq:32uni95diff95first95TST} 2\mathbb{P}\left( \bar{\mathcal{E}}_{1,n}^c\left(\frac{\epsilon}{2} \right)\right) &\leq 4e^{-\frac{\epsilon}{2\sigma_1}n}. \end{align}\tag{26}\] Since \(\bar{x}^{(n)}_1 \geq \mu_1 + \frac{\sigma_1}{2} - \frac{\epsilon}{2}\) and \(\bar{x}^{(n)}_1 -x^{(1)}_1 \leq \sigma_1\) hold for any \(n\) on \(\bar{\mathcal{E}}_{1,n}(\epsilon/2)\), we have \[\begin{align} \boldsymbol{1}\bigg[\bar{\mathcal{E}}_{1,n}(\epsilon/2)\bigg]\left(1-p_n(\epsilon|\theta_{1,n})\right) &\leq \boldsymbol{1}\bigg[\bar{\mathcal{E}}_{1,n}(\epsilon/2)\bigg]\frac{1}{2}\left(\frac{\bar{x}^{(n)}_1-x^{(1)}_1}{2\left(\bar{x}^{(n)}_1-\mu_1+\epsilon\right)} \right)^{n+k-2} \\ &\leq \frac{1}{2}\left( \frac{\sigma_1}{\sigma_1 +\epsilon}\right)^{n+k-2} \leq \frac{1}{2}e^{- \frac{\epsilon}{\sigma_1+\epsilon}(n+k-2)}. \end{align}\] Therefore, the second term of (25 ) is bounded as \[\label{eq:32uni95diff95second95TST} 2\mathbb{E}\left[\boldsymbol{1}\left[\bar{\mathcal{E}}_{1,n}\left(\frac{\epsilon}{2} \right) \right] (1-\bar{p}_n(\epsilon|\theta_{1,n})) \right] \leq e^{- \frac{\epsilon}{\sigma_1+\epsilon}(n+k-2)}.\tag{27}\] Finally, we evaluate the last term of (25 ). By following the same steps to the last term of (18 ), one can obtain for \(\bar{\mathcal{T}} = \left\{ x^{(1)}_1 + \bar{x}^{(n)}_1 \leq 2(\mu - \epsilon) \right\}\) \[\begin{align} \boldsymbol{1}\left[ x^{(1)}_1 + \bar{x}^{(n)}_1 \leq 2(\mu - \epsilon) \right]\mathbb{P}[\tilde{\mu}_1 \geq \mu_1 -\epsilon| \theta_{1,n}, \sigma = \tilde{\sigma}_1] \leq \boldsymbol{1}\left[ \bar{\mathcal{T}} \right] \frac{1}{2}\left( \frac{\bar{x}^{(n)}_{1}-x^{(1)}_{1}}{2(\mu_1 -\epsilon- x^{(1)}_1)} \right)^{n+k-2}. \end{align}\] Since \(\boldsymbol{1}[\bar{x}^{(n)}_1 \ne x^{(n)}_1] = \boldsymbol{1}\left[\bar{x}^{(n)}_1 = x^{(1)}_1 + \frac{1}{n}\right]\) from the definition of \(\bar{x}^{(n)}_1\), taking expectation gives us \[\begin{align} \mathbb{E}\left[ \frac{\boldsymbol{1}\bigg[ \bar{\mathcal{T}} \bigg]}{p_n(\epsilon|\theta_{1,n})} \right] &= 2\mathbb{E}\left[ \boldsymbol{1}\left[ x^{(1)}_1 + \bar{x}^{(n)}_1 \leq 2(\mu_1 - \epsilon)\right] \left( \frac{2(\mu_1-\epsilon-x^{(1)}_1)}{\bar{x}^{(n)}_1 - x^{(1)}_1} \right)^{n+k-2} \right] \\ &= 2\underbrace{\mathbb{E}\left[ \boldsymbol{1}\left[ \bar{\mathcal{T}}, \bar{x}^{(n)}_1 =x^{(n)}_1 \right] \left( \frac{2(\mu_1-\epsilon-x^{(1)}_1)}{\bar{x}^{(n)}_1 - x^{(1)}_1} \right)^{n+k-2} \right]}_{(\dagger_{\mathrm{U}})} \\ & + 2\underbrace{\mathbb{E}\left[ \boldsymbol{1}\left[ \bar{\mathcal{T}}, \bar{x}^{(n)}_1 = x^{(1)}_1+ 1/n\right] \left( \frac{2(\mu_1-\epsilon-x^{(1)}_1)}{\bar{x}^{(n)}_1 - x^{(1)}_1} \right)^{n+k-2} \right]}_{(\diamond_{\mathrm{U}})}. \end{align}\] Note that \((\diamond_{\mathrm{U}})\) term is introduced due to the truncation procedure in TS-T.

10.3.3 (1) Upper bound of \((\dagger_{\mathrm{U}})\)↩︎

Under the condition \(\{x^{(1)}_1 + \bar{x}^{(n)}_1 \leq 2(\mu_1 - \epsilon), \bar{x}^{(n)}_1 = x^{(n)}_1\}\), we have \[\begin{align} x^{(1)}_1 &\in \left[ \mu_1 - \frac{\sigma_1}{2}, \mu_1 -\epsilon\right) \\ x^{(n)}_1 &\in \left[ x^{(1)}_1 + \frac{1}{n}, \min(2(\mu_1-\epsilon-x^{(1)}_1), \mu_1+\frac{\sigma_1}{2}) \right). \end{align}\] By applying Lemma 6, we obtain \[\begin{align} (\dagger_{\mathrm{U}}) &= \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y+\frac{1}{n}}^{\min(2(\mu_1-\epsilon-y), \mu_1+\frac{\sigma_1}{2})} \frac{n(n-1)}{\sigma_1^n}(z-y)^{n-2} \left( \frac{2(\mu-\epsilon-y)}{z - y} \right)^{n+k-2} \mathrm{d}z \mathrm{d}y \\ &\leq \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y+\frac{1}{n}}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n}(z-y)^{n-2} \left( \frac{2(\mu_1-\epsilon-y)}{z - y} \right)^{n+k-2} \mathrm{d}z \mathrm{d}y \\ &= \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y+\frac{1}{n}}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n} \frac{\left(2(\mu_1-\epsilon-y) \right)^{n+k-2}}{(z-y)^k} \mathrm{d}z \mathrm{d}y. \addtocounter{equation}{1}{\label{eq:32why95trun}} \end{align}\tag{28}\] Note that the domain of the integral respect to \(z\) in (28 ) is \([y + n^{-1}, 2(\mu_1-\epsilon-y)]\) differently from the integral introduced in TS, \([y, 2(\mu_1-\epsilon-y)]\) in (22 ). The upper bounds on (\(\star_{\mathrm{U}}\)) in (21 ) directly gives the upper bound of \((\dagger_{\mathrm{U}})\) for \(k< 1\). By defining \(w=2(\mu_1-\epsilon- y)\), we can derive the upper bound of \((\dagger_{\mathrm{U}})\) for \(k \geq 1\).

10.3.3.1 (1-i) For the reference prior (\(k=1\)):

\[\begin{align} (\dagger_{\mathrm{U}}) &\leq \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y+\frac{1}{n}}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n} \frac{\left(2(\mu_1-\epsilon-y) \right)^{n-1}}{(z-y)} \mathrm{d}z \mathrm{d}y \\ &=\frac{1}{2}\int_{0}^{\sigma_1 - 2\epsilon} \frac{n(n-1)}{\sigma_1^n} w^{n-1}\log(n w)) \mathrm{d}w \\ &= \frac{1}{2} \left(\frac{\sigma_1-2\epsilon}{\sigma_1}\right)^n n(n-1) \frac{n\log(n(\sigma_1-2\epsilon))-1}{n^2} \\ &\leq \frac{n \log(n \sigma_1)}{2} e^{- \frac{2\epsilon}{\sigma_1}n}. \end{align}\]

10.3.3.2 (1-ii) For priors with \(k>1\):

One can see that the integral in (28 ) is an increasing function with respect to \(k\) since \(2(\mu_1 - \epsilon-y) > (z-y)\) holds for all \(z \in (y+1/n, 2(\mu_1-\epsilon-y)\). For \(k > 1\), it holds that \[\begin{align} (\dagger_{\mathrm{U}}) &\leq \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y+\frac{1}{n}}^{2(\mu_1-\epsilon-y)} \frac{n(n-1)}{\sigma_1^n} \frac{\left(2(\mu_1-\epsilon-y) \right)^{n+k-2}}{(z-y)^k} \mathrm{d}z \mathrm{d}y \\ & \leq \frac{n(n-1)}{\sigma_1^n} \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \left(2(\mu_1-\epsilon-y) \right)^{n+k-2} \frac{n^{k-1}}{k-1} \mathrm{d}y \\ & = \frac{n^k(n-1)}{2\sigma_1^n(k-1)} \int_0^{\sigma_1 - 2\epsilon} w^{n+k-2} \mathrm{d}w = \frac{n^k(n-1)}{2(n+k-2)} (\sigma_1 - 2\epsilon)^{k-1} e^{-\frac{2\epsilon}{\sigma_1}n}. \end{align}\]

10.3.3.3 (1-iii) Summary:

Therefore, we have the following results. \[\begin{align} (\dagger_{\mathrm{U}}) \leq \begin{cases} \frac{3(n-1)}{4}e^{-\frac{2\epsilon}{\sigma_1}n} & k<1, \\ \frac{n \log(n \sigma_1)}{2} e^{- \frac{2\epsilon}{\sigma_1}n} & k= 1 \\ \frac{n^k(n-1)}{n+k-2} \frac{(\sigma_1-2\epsilon)^{k-1}}{2} e^{-\frac{2\epsilon}{\sigma_1}n} & k >1. \end{cases}\addtocounter{equation}{1}{\label{eq:32uni95diff95third95TST}} \end{align}\tag{29}\]

10.3.4 (2) Upper bound of \((\diamond_{\mathrm{U}})\)↩︎

From \(\boldsymbol{1}[\bar{x}^{(n)}_1 = x^{(1)}_1 + 1/n] = \boldsymbol{1}[x^{(n)}_1 \leq x^{(1)}_1 + 1/n]\), it holds that \[\boldsymbol{1}[\bar{x}^{(n)}_1 = x^{(1)}_1 + 1/n] \left( \frac{2(\mu_1 -\epsilon- x^{(1)}_1)}{\bar{x}^{(n)}_1 - x^{(1)}_1} \right) = \boldsymbol{1}[x^{(n)}_1 \leq x^{(1)}_1 + 1/n] 2n(\mu_1 -\epsilon- x^{(1)}_1).\] Therefore, applying Lemma 6, we obtain \[\begin{align} (\diamond_{\mathrm{U}}) &= \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu_1 - \epsilon} \int_{y}^{y+\frac{1}{n}} \frac{n(n-1)}{\sigma_1^n} (2n(\mu_1-\epsilon-y))^{n+k-2} (z-y)^{n-2} \mathrm{d}z \mathrm{d}y \\ &= \int_{\mu_1-\frac{\sigma_1}{2}}^{\mu - \epsilon} \frac{n^k}{\sigma_1^n} (2(\mu_1-\epsilon-y))^{n+k-2} \mathrm{d}y \\ &= \frac{1}{2}\int_{0}^{\sigma_1-2\epsilon} \frac{n^k}{\sigma_1^n} w^{n+k-2} \mathrm{d}w \tag*{By a change of variables}\\ &= \frac{1}{2} \frac{n^k}{n+k-1} (\sigma_1-2\epsilon)^{k-1}\left( \frac{\sigma_1-2\epsilon}{\sigma_1} \right)^{n} \\ &\leq \frac{1}{2} \frac{n^k}{n+k-1} (\sigma_1-2\epsilon)^{k-1} e^{-\frac{2\epsilon}{\sigma_1}n}. \addtocounter{equation}{1}{\label{eq:32uni95diff95fourth95TST}} \end{align}\tag{30}\]

10.3.5 (3) Conclusion↩︎

Therefore, by combining (26 ), (27 ), (29 ), and (30 ) with (25 ) and (24 ), we have for \(\epsilon>0\) that \[\begin{align} \sum_{n=n_0}^T \mathbb{E}\left[ \frac{1-p_n(\epsilon|{\theta}_{1,n})}{p_n(\epsilon|{\theta}_{1,n})} \right] &\leq \sum_{n=n_0}^T 4e^{-\frac{\epsilon}{2\sigma}n} + e^{-\frac{\epsilon}{\sigma+\epsilon}(n-1)} + (\dagger_{\mathrm{U}}) + (\diamond_{\mathrm{U}}) \\ &\leq \frac{8\sigma_1}{\epsilon} + \frac{\sigma_1 +\epsilon}{\epsilon} + \begin{cases} \frac{3}{16}\frac{\sigma_1^2}{\epsilon^2}(2e^{\frac{2\epsilon}{\sigma_1}-1}) &\text{if } k < 1 \\ \frac{\sigma_1^2\log(\sigma_1)}{8\epsilon^2} + \frac{\sigma_1}{4\epsilon} &\text{if } k = 1 \\ \frac{(\sigma_1-2\epsilon)^{k-1}}{2}\left( \mathrm{Li}_{1-k}(e^{-\frac{2\epsilon}{\sigma_1}}) + \mathrm{Li}_{-k}(e^{-\frac{2\epsilon}{\sigma_1}}) \right) &\text{if } k > 1 \end{cases}, \end{align}\] where \(\mathrm{Li}_{s}(z)\) denotes the polylogarithm function of order \(s\) at \(z\). This concludes the proof of Lemma 3 for the case of TS-T. ◻

10.4 Proofs of technical lemmas for Lemma 2 ↩︎

In this section, we provide the detailed proofs of Lemmas 7 and 8. Notice that Lemma 8 is related to the main regret term of the policy.

Proof of Lemma 7. By the definition of \(x^{(1)}_i\) and \(x^{(n)}_i\), which is the first order statistic and the last order statistic of \(X_{i,n}\), respectively, we have \[\begin{align} \mathbb{P}\left[x^{(1)}_i \geq \mu_i- \frac{\sigma_i}{2} + \epsilon\right] &= \mathbb{P}\left[\forall s \in [n]: x_{i,s} \geq \mu_i- \frac{\sigma_i}{2} + \epsilon\right] \\ &= \left( 1 - \frac{\epsilon}{\sigma_i}\right)^n \leq \exp(-\frac{\epsilon}{\sigma_i}n). \end{align}\] Similarly, we have \[\begin{align} \mathbb{P}\left[\bar{x}^{(n)}_i \leq \mu_i + \frac{\sigma_i}{2} - \epsilon\right] &= \mathbb{P}\left[\left\{\forall s \in [n]: x_{i,s} \leq \mu_i + \frac{\sigma_i}{2} - \epsilon\right\}, x^{(1)}_i \leq \mu_i + \frac{\sigma_i}{2} -\epsilon- \frac{1}{n} \right]\\ &\leq \mathbb{P}\left[\forall s \in [n]: x_{i,s} \leq \mu_i + \frac{\sigma_i}{2} - \epsilon\right] = \mathbb{P}\left[x^{(n)}_i \leq \mu_i + \frac{\sigma_i}{2} - \epsilon\right] \\ &\leq \left( 1 - \frac{\epsilon}{\sigma_i}\right)^n \leq \exp(-\frac{\epsilon}{\sigma_i}), \end{align}\] which concludes the proof. ◻

Proof of Lemma 8. The overall proofs for both TS and TS-T are almost the same. For simplicity, we fix a time index \(t\) and denote \(\mathbb{P}_t[\cdot] = \mathbb{P}\left[\cdot \mid T(X_{i,N_i(t)})\right] = \mathbb{P}\left[\cdot \mid \theta_{i,n}\right]\) and \(N_i(t) =n\) in this proof, where \(\theta_{i,n} = \left(x^{(1)}_i, x^{(n)}_i \right)\)

10.4.1 Under TS↩︎

Under the condition \(\{ \mathcal{E}_{i,N_i(t)}(\epsilon), N_i(t)\}\), by the law of total expectation, it holds that \[\begin{align} \mathbb{E}[\boldsymbol{1}[i(t)=i,\,\tilde{\mu}^*(t) \geq \mu_1 - \epsilon,\, &\mathcal{E}_{i,N_i(t)}(\epsilon), \, N_i(t) =n]] \leq \mathbb{E}_{\theta_{i,n}}\left[\mathbb{P}_t[\tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \mathcal{E}_{i,n}(\epsilon), N_i(t)=n]\right]. \end{align}\] Since \(\tilde{\mu}_i| \tilde{\sigma}_i \sim \mathrm{Uni}_{ab}\left( x^{(n)}_i - \frac{\tilde{\sigma}_i}{2}, x^{(1)}_i + \frac{\tilde{\sigma}_i}{2} \right)\), if \(x^{(n)}_i - \frac{\tilde{\sigma}_i}{2} \geq \mu_1 - \epsilon\) holds, then \(\tilde{\mu}_i \geq \mu_1 - \epsilon\) holds with probability \(1\). Therefore, we have \[\begin{align} \mathbb{P}_t[\tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \mathcal{E}_{i,n}(\epsilon)] &= \mathbb{P}_t\left[x^{(n)}_i - \frac{\tilde{\sigma}_i}{2} \geq \mu_1 - \epsilon, \mathcal{E}_{i,n}(\epsilon) \right] \\ &+ \mathbb{P}_t \left[ \tilde{\mu}_i(t) \geq \mu_1 -\epsilon, x^{(n)}_i - \frac{\tilde{\sigma}_i}{2} \leq \mu_1 - \epsilon\leq x^{(1)}_i + \frac{\tilde{\sigma}_i}{2}, \mathcal{E}_{i,n}(\epsilon) \right] \\ &\leq \mathbb{P}_t\left[\frac{\tilde{\sigma}_i}{2} \leq \mu_i + \frac{\sigma_i}{2}-(\mu_1 - \epsilon), \mathcal{E}_{i,n}(\epsilon)\right] \\ &+ \mathbb{P}_t \left[ \tilde{\mu}_i(t) \geq \mu_1 -\epsilon, x^{(n)}_i - \frac{\tilde{\sigma}_i}{2} \leq \mu_1 - \epsilon\leq x^{(1)}_i + \frac{\tilde{\sigma}_i}{2}, \mathcal{E}_{i,n}(\epsilon) \right]. \end{align}\] Since \(\tilde{\sigma}_i \geq x^{(n)}_i-x^{(1)}_i = \hat{\sigma}_{i,n}\) always holds from the sampling procedure of TS, we have \[\boldsymbol{1}[\mathcal{E}_{i,n}(\epsilon)] \tilde{\sigma}_i(t) \geq \boldsymbol{1}[\mathcal{E}_{i,n}(\epsilon)] \left(x^{(n)}_i-x^{(1)}_i\right) \geq \boldsymbol{1}[\mathcal{E}_{i,n}(\epsilon)](\sigma_i - 2\epsilon).\] By the choice of \(\epsilon< \frac{\Delta_i}{2}\), it holds that \[\sigma_i - 2 \epsilon\geq \sigma_i + 2\epsilon- 2 \Delta_i = \sigma_i + 2\epsilon+ 2 (\mu_i - \mu_1),\] which implies \[\mathbb{P}_t\left[\frac{\tilde{\sigma}_i}{2} \leq \mu_i + \frac{\sigma_i}{2}-(\mu_1 - \epsilon), \mathcal{E}_{i,n}(\epsilon)\right] = 0.\] Then, it holds that \[\begin{align} \mathbb{P}_t \bigg[ \tilde{\mu}_i(t) \geq \mu_1 -\epsilon, x^{(n)}_i - \frac{\tilde{\sigma}_i}{2} \leq \mu_1 - \epsilon\leq x^{(1)}_i + \frac{\tilde{\sigma}_i}{2}, \mathcal{E}_{i,n}(\epsilon) \bigg] & = \mathbb{P}_t \left[ \tilde{\mu}_i(t) \geq \mu_1 -\epsilon, \mu_1 - \epsilon\leq x^{(1)}_i + \frac{\tilde{\sigma}_i}{2}, \mathcal{E}_{i,n}(\epsilon) \right] \\ &\leq \mathbb{P}_t \left[ \tilde{\mu}_i(t) \geq \mu_1 -\epsilon, \sigma_i + 2\Delta_i - 4\epsilon\leq \tilde{\sigma}_i, \mathcal{E}_{i,n}(\epsilon) \right], \end{align}\] where the inequality holds from \(x^{(1)}_i \leq \mu_i - \frac{\sigma_i}{2} +\epsilon\) on \(\mathcal{E}_{i,n}(\epsilon)\). Therefore, by taking expectation, we have for a constant \(B_i :=\sigma_i + 2\Delta_i -4\epsilon\) that \[\begin{align} \mathbb{E}\bigg[ \mathbb{P}_t[\tilde{\mu}_i(t) \geq \mu_1- \epsilon, \mathcal{E}_{i,n}(\epsilon)]\bigg] &\leq \int_{\sigma_i + 2\Delta_i - 4\epsilon}^\infty \pi^{k}(s|\theta_{i,n}) \int_{\mu_1-\epsilon}^{\mu_i+\frac{s-\sigma_i}{2}+\epsilon} \pi^{k}(m|\theta_{i,n}, \tilde{\sigma}_i=s) \mathrm{d}m\mathrm{d}s \\ &= \int_{\sigma_i + 2\Delta_i - 4\epsilon}^\infty \frac{1}{s-\left(x^{(n)}_{i}-x^{(1)}_{i}\right)}\left( \frac{s-\sigma_i}{2} - \Delta_i + 2\epsilon\right) \pi^{k}(s|\theta_{i,n}) \mathrm{d}s \\ &= \left( x^{(n)}_{i}-x^{(1)}_{i}\right)^{n+k-2} \int_{\sigma_i + 2\Delta_i - 4\epsilon}^\infty \frac{(n+k-1)(n+k-2)}{s^{n+k}}\\ &\cdot \left( \frac{s-\sigma_i}{2} - \Delta_i + 2\epsilon\right)\mathrm{d}s \\ &= \frac{\left( x^{(n)}_{i}-x^{(1)}_{i}\right)^{n+k-2} }{2} \int_{B_i}^\infty \frac{(n+k-1)(n+k-2)}{s^{n+k}}\left( s - B_i\right)\mathrm{d}s \\ &= \frac{\left( x^{(n)}_{i}-x^{(1)}_{i}\right)^{n+k-2} }{2} \left( \frac{n+k-1}{B_i^{n+k-2}} - \frac{n+k-2}{B_i^{n+k-2}} \right) \\ &\leq \frac{1}{2} \left( \frac{\sigma_i}{\sigma_i + 2\Delta_i -4\epsilon} \right)^{n+k-2} = \frac{1}{2} \left( \frac{1}{1 + \frac{2\Delta_i -4\epsilon}{\sigma_i}} \right)^{n+k-2}, \addtocounter{equation}{1}{\label{eq:32uni95TS95mainregret95U}} \end{align}\tag{31}\] where the last inequality holds from \(x^{(1)}_i \geq \mu_i - \frac{\sigma_i}{2}\) and \(x^{(n)}_i \leq \mu_i+ \frac{\sigma_i}{2}\). For the arm \(i\ne 1\) and arbitrary \(n_i >n_0\), we have \[\begin{align} \sum_{t=n_0K+1}^T\mathbb{E}[\boldsymbol{1}[i(t)=i, \tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \mathcal{E}_{i,n}(\epsilon)]] &\leq n_i + \sum_{t=n_0K+1}^{T}\mathbb{P}[\tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \mathcal{E}_{i,N_i(t)}(\epsilon), N_i(t) \geq n_i ] \\ &\leq n_i + \sum_{t=n_0K+1}^T \frac{1}{2} \left( \frac{1}{1 + \frac{2\Delta_i -4\epsilon}{\sigma_a}} \right)^{n_i+k-2} \\ &= n_i + \frac{T}{2} \left( \frac{1}{1 + \frac{2\Delta_i -4\epsilon}{\sigma_i}} \right)^{n_i+k-2}. \end{align}\] Letting \(n_i = \max(2-k,0)+ \frac{\log T}{\log \left( 1 + \frac{2\Delta_i -4\epsilon}{\sigma_i} \right)}\) concludes the proof of Lemma 8 for the case of TS.

10.4.2 Under TS-T↩︎

From the sampling rule of TS-T, it holds that \[\begin{align} \mathbb{E}[\boldsymbol{1}[i(t)=i,\, \tilde{\mu}^*(t) \geq \mu_1 - \epsilon,\, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon),\, N_i(t) =n]] \leq \mathbb{E}_{\theta_{i,n}}\left[\mathbb{P}_t[ \tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \bar{\mathcal{E}}_{i,n}(\epsilon), N_i(t)=n]\right]. \end{align}\] Therefore, the only differences from the proof of the case of TS are \(\bar{x}^{(n)}_i\) and \(\bar{\mathcal{E}}\) instead of \(x^{(n)}_i\) and \(\mathcal{E}\), respectively. By following the same steps as under TS, we have an additional restriction in (31 ), where the last inequality holds for TS-T when \(\frac{1}{n} \leq \sigma_i\) to satisfy \(\bar{x}^{(n)}_i \leq \mu_i+ \frac{\sigma_i}{2}\). Therefore, for arm \(i\ne 1\) and arbitrary \(n_i > \max\left(n_0, \frac{1}{\sigma_i}\right)\), we have \[\begin{align} \sum_{t=n_0K+1}^T\mathbb{E}[\boldsymbol{1}[i(t)=i, \tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \bar{\mathcal{E}}_{i,n}(\epsilon)]] &\leq n_i + \sum_{t=n_0K+1}^{T}\mathbb{P}[\tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), N_i(t) \geq n_i ] \\ &\leq n_i + \sum_{t=n_0K+1}^{T}\mathbb{P}[\tilde{\mu}_i(t) \geq \mu_1 - \epsilon, \mathcal{E}_{i,N_i(t)}(\epsilon), N_i(t) \geq n_i ] \\ &\leq n_i + \sum_{t=n_0K+1}^T \frac{1}{2} \left( \frac{1}{1 + \frac{2\Delta_i -4\epsilon}{\sigma_a}} \right)^{n_i+k-2} \\ &= n_i + \frac{T}{2} \left( \frac{1}{1 + \frac{2\Delta_i -4\epsilon}{\sigma_i}} \right)^{n_i+k-2}. \end{align}\] Letting \(n_i = \max(\frac{1}{\sigma_i}, 2-k)+ \frac{\log T}{\log \left( 1 + \frac{2\Delta_i -4\epsilon}{\sigma_i} \right)}\) concludes the proof. ◻

10.5 Proof of Lemma 4 ↩︎

The proof of Lemma 4 can be easily derived from the lemmas below, which are the counterparts of Lemmas 7 and 8 in the Gaussian bandits.

Note that the regret lower bound with (4 ) is invariant under the location and scale transformation, which implies that \[\begin{gather} \inf_{({\mu, \sigma}): \mu> \mu_1}\mathrm{KL}(\mathrm{Gaussian}(\mu_i, \sigma_i); \mathrm{Gaussian}(\mu, \sigma)) \\ = \inf_{({\mu, \sigma}): \mu> \mu_1}\mathrm{KL}\left(\mathrm{Gaussian}\left(\frac{\mu_i-a}{b}, \frac{\sigma_i}{b}\right); \mathrm{Gaussian}\left(\frac{\mu-a}{b}, \frac{\sigma}{b}\right)\right). \end{gather}\] In the remaining of this proof, we consider the Gaussian bandit instance where \((\mu_1, \sigma_1) = (0,1)\) for simplicity since one can recover the original instance by the location and scale transformation, following the previous analysis [12]. Similarly to the uniform bandits, let us define two events for \(n \in \mathbb{N}\) and \(i\in[K]\) that \[\begin{align} \mathcal{M}_\epsilon(t) &= \left\{ \tilde{\mu}^*(t) \geq -\epsilon\right\}, \\ \mathcal{E}_{i,n}(\epsilon) &= \{ \hat{x}_{i,n} \leq \mu_i +\epsilon, S_{i,n} \leq n(\sigma_i^2 + \epsilon)\}. \end{align}\] In this section, \(\theta_{i,n}\) denotes \((\hat{x}_{i,n}, S_{i,n})\), which are the sufficient statistic in the Gaussian models. To begin the proof, we first provide some known results in the Gaussian bandits.

Lemma 9 (Lemma 9 in [12]). For any \(i\ne 1\), \[\mathbb{E}\left[ \sum_{t=Kn_0+ 1}^T \boldsymbol{1}[i(t)=i, \mathcal{E}_{i,n}^c(\epsilon)] \right] \leq \mathcal{O}(\sigma_i^2 \epsilon^{-2}).\]

Lemma 10 (Lemma 4 in [12]). If \(\mu > \hat{x}_{i,n}\) and \(n \geq n_0\), then \[\label{eq:32uni95hnd95main95lower} \mathbb{P}[\tilde{\mu}_i \geq \mu| \hat{x}_{i,n}, S_{i,n}] \geq A_{n,k} \left( 1 + \frac{n(\mu - \hat{x}_{i,n})^2}{S_{i,n}} \right)^{-\frac{n+k-2}{2}}\tag{32}\] and \[\label{eq:32uni95hnd95main95upper} \mathbb{P}[\tilde{\mu}_i \geq \mu|\hat{x}_{i,n}, S_{i,n}] \leq \frac{\sqrt{S_{i,n}}}{\mu - \hat{x}_{i,n}} \left(1 + \frac{n(\mu - \hat{x}_{i,n})^2}{S_{i,n}} \right)^{-\frac{n+k-3}{2}},\tag{33}\] where \[A_{n,k} = \frac{1}{2e^{1/6}\sqrt{\frac{n+k-1}{2}\pi}}.\]

Proof of Lemma 4. Let us first define an event on the truncated statistic \[\bar{\mathcal{E}}_{i,n}(\epsilon) := \left\{ \hat{x}_{i,n} \leq \mu_i +\epsilon, \bar{S}_{i,n} \leq n(\sigma_i^2 + \epsilon) \right\}.\] Similarly to the analysis of TS-T in the uniform bandits, we can decompose \((\mathrm{GO})\) as \[(\mathrm{GO}) \leq \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \boldsymbol{1}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \Delta_i \boldsymbol{1}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}^c(\epsilon)\right].\] From the definition of \(\bar{S}_{i,n} = \max(1, S_{i,n})\), it holds that \[\mathcal{E}_{i,n}(\epsilon) \subset \bar{\mathcal{E}}_{i,n}(\epsilon).\] Therefore, from Lemma 9, we have \[\begin{align} \mathbb{E}[(\mathrm{GO})] &\leq \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \mathbb{E}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \mathbb{E}\left[i(t)=i, \mathcal{E}_{i,N_i(t)}^c(\epsilon)\right] \\ & \leq \sum_{i=2}^K \sum_{t=Kn_0+1}^T \Delta_i \mathbb{E}\left[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\right] + \mathcal{O}(\sigma_1^2 \epsilon^{-2}). \addtocounter{equation}{1}{\label{eq:32uni95GO95decom95G}} \end{align}\tag{34}\] It remains to show the upper bound of the first term of (34 ). Let \(n_i> \frac{1}{\sigma_i^2}\) be arbitrary, where \(\mathcal{E}_{i,n_i}(\epsilon) = \bar{\mathcal{E}}_{i,n_i}(\epsilon)\) holds for any \(\epsilon>0\). Then, by injecting (33 ) in Lemma 10 \[\begin{align} \mathbb{E}\Bigg[\sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)=i, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), \mathcal{M}_\epsilon(t)\bigg] \Bigg] &\leq n_i + \sum_{t=Kn_0+1}^T \mathbb{P}\left[\tilde{\mu}_i(t) \geq -\epsilon, \bar{\mathcal{E}}_{i,N_i(t)}(\epsilon), N_i(t)\geq n_i\right] \\ &= n_i + \sum_{t=Kn_0+1}^T \mathbb{P}\left[\tilde{\mu}_i(t) \geq -\epsilon, \mathcal{E}_{i,N_i(t)}(\epsilon), N_i(t)\geq n_i\right] \\ &\leq n_i + \sum_{t=Kn_0+ 1}^T \frac{\sqrt{\sigma_i^2+\epsilon}}{\Delta_i - 2\epsilon} \left( 1+ \frac{(\Delta_i - 2\epsilon)^{2}}{\sigma_i^2 + \epsilon}\right)^{-\frac{n+k-3}{2}} \\ &= n_i + T \frac{\sqrt{\sigma_i^2+\epsilon}}{\Delta_i - 2\epsilon} \exp(-(n+k-3) \frac{1}{2}\log \left( 1+ \frac{(\Delta_i-2\epsilon)^2}{\sigma_i^2+\epsilon} \right)). \end{align}\] Letting \(n_i = \max\left( \sigma_i^{-2}, \frac{\log T}{\frac{1}{2}\log \left( 1+ \frac{(\Delta_i-2\epsilon)^2}{\sigma_i^2+\epsilon}\right)} + 3-k \right)\) completes the proof. ◻

10.6 Proof of Lemma 5 ↩︎

Firstly, we introduce some technical results from [12] before beginning the proof.

Lemma 11 (Some results in [12]). For \(n \geq n_0\) and \(\epsilon>0\), it holds that \[\begin{align} \mathbb{P}[-\epsilon\leq \hat{\mu}_{1,n} \leq -\epsilon/2] &\leq e^{-\frac{\epsilon^2}{8}n}, \\ \mathbb{P}[-\epsilon/2 \leq \hat{\mu}_{1,n}, S_{1,n} \geq 2n] &\leq e^{-\frac{1-\log 2}{2}n}. \end{align}\]

Lemma 12 (Lemma 10 of [12]). For \(z \geq 1/2\) \[e^{-2/3} \leq \frac{\Gamma\left(z + \frac{1}{2}\right)}{\Gamma(z)} \leq e^{1/6}\sqrt{z}.\]

Next, we introduce two functions and their corresponding integral representations to analyze the term induced by TS-T.

Definition 3. The confluent hypergeometric function of the second kind \(U(a,b,z)\), a.k.a. Tricomi’s function [46], is a solution of Kummer’s equation \[z \frac{\mathrm{d}^2 w}{\mathrm{d}z^2} + (b-z) \frac{\mathrm{d}w}{\mathrm{d}z} - aw = 0,\] which can be uniquely determined by satisfying for arbitrary small constant \(\epsilon>0\) \[U(a,b,z) \sim z^{-a}, ~~~~ z \to \infty, \,|\mathrm{ph} z | \leq \frac{3}{2}\pi - \epsilon.\] Here, \(\mathrm{ph} z\) denotes the phase of \(z\in \mathbb{C}\). It has its integral representation for \(a,b \in \mathbb{R}_{+}\) such that \(b>a\) and \(z \in \mathbb{R}_+\) as follows [47]: \[\label{eq:32uni95hyperg95def} U(a,b,z) = \frac{1}{\Gamma(a)} \int_0^{\infty} e^{-zt}t^{a-1}(1+t)^{b-a-1} \mathrm{d}t.\tag{35}\]

Definition 4. The modified Bessel function of the second kind is a standard solution of the modified Bessel’s equation \[z^2 \frac{\mathrm{d}^2 w}{\mathrm{d}z^2} + z \frac{\mathrm{d}w}{\mathrm{d}z} - (z^2+ v^2) w = 0,\] which can be uniquely determined by satisfying that \[K_v(z) \sim \sqrt{\frac{\pi}{2z}}e^{-z}, ~~~~ z \to \infty, \,|\mathrm{ph} z | < \frac{3}{2}\pi.\] It has the integral representation as follows [47]: \[\label{eq:32modifiedBessel} K_v(z) = \int_0^\infty e^{-z \cosh t} \cosh (vt) \mathrm{d}t,\tag{36}\] where \(K_v(z) = K_{-v}(z)\) holds.

Then, we provide two technical lemmas, whose proofs are given in Section 10.7.

Lemma 13. Let \(\Gamma(s, x) = \int_{x}^\infty t^{s-1}e^{-t} \mathrm{d}t\) denote the upper incomplete gamma function. Then, \[\begin{align} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{k+1}{2}} \Gamma\left( \frac{n}{2}, \frac{1}{2(1-w)} \right)\mathrm{d}w &\leq \Gamma\left( \frac{n}{2} \right) \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1+\frac{2}{n^{\frac{k+1}{2}}}}\mathrm{d}w \\ &= \Gamma\left( \frac{n}{2} \right) B\left( \frac{1}{2}, \frac{2}{n^{\frac{k+1}{2}}} \right) \end{align}\] is valid for \(k \in \{ 1, 2\}\) and \(n \geq n_0=\max(2, 4-k)\), where \(B(z_1, z_2)\) denotes the Beta function.

Lemma 14. For \(a, b, z \in\mathbb{R}\), let \(U(a,b,z)\) denote the confluent hypergeometric function of the second kind. Then, \[\begin{align} U\left( \frac{1}{2}, b, \frac{1}{2} \right) \leq \frac{2^{b}}{\Gamma\left(\frac{1}{2}\right)} \Gamma\left(b - \frac{1}{2} \right) \end{align}\] is valid for \(b \in \left\{ \frac{m}{2} : m \in \mathbb{Z}_{\geq 4}\right\}\).

Finally, we provide the numerical results of the computation of the modified Bessel function of the second kind, which is used several times in the proof.

Fact 5 (Table 2 in [48]). Let \(K_v(z)\) denote the modified Bessel function of the second kind. Then, the followings are the results of numerical computations evaluated to 6S. \[\begin{align} e^{0.24}K_0(0.24) &= 2.00835\\ e^{0.24}K_1(0.24) &= 4.98213 \end{align}\]

Proof of Lemma 5. Let us define \(\bar{\theta}_{1,n} = (\hat{\mu}_{1,n}, \bar{S}_{1,n})\). Similarly to Lemma 3 in the uniform model, let us consider the following decomposition: \[\begin{align} \sum_{t=Kn_0+1}^T \boldsymbol{1}[i(t)\ne 1, \mathcal{M}_\epsilon^c(t)] &= \sum_{n=n_0}^T \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1,\mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg] \\ &= \sum_{n=n_0}^T \sum_{m=1}^T \boldsymbol{1}\Bigg[m \leq \sum_{t=Kn_0+ 1}^T \boldsymbol{1}\bigg[i(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg]\Bigg] \\ &\leq \mathbb{E}\left[ \sum_{n=n_0}^T \sum_{m=1}^T (1-p_n(\epsilon|\bar{\theta}_{1,n}))^m \right] \\ &\leq \sum_{n=n_0}^T \mathbb{E}\left[ \frac{1-p_n(\epsilon|\bar{\theta}_{1,n})}{p_n(\epsilon|\bar{\theta}_{1,n})} \right], \end{align}\] where \(p_n(\epsilon|\bar{\theta}_{1,n}) = \mathbb{P}[\tilde{\mu}_1 \geq -\epsilon| \hat{\mu}_{1,n}, \bar{S}_{1,n}]\). Since the Student’s \(t\)-distribution is symmetric about its location parameter, \(\boldsymbol{1}[\hat{\mu}_{1,n} \geq -\epsilon]p_n(\epsilon| \bar{\theta}) \geq 1/2\) holds. Therefore, we have \[\label{eq:32uni95pn95decom95G} \mathbb{E}\left[ \frac{1-p_n(\epsilon|\bar{\theta}_{1,n})}{p_n(\epsilon|\bar{\theta}_{1,n})} \right] \leq 2\mathbb{E}\left[ \boldsymbol{1}[\hat{\mu}_{1,n} \geq - \epsilon] (1-p_n(\epsilon|\bar{\theta}_{1,n}))\right] + \mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon] }{p_n(\epsilon|\bar{\theta}_{1,n})} \right].\tag{37}\] By applying Lemma 11 to the first term in (37 ), it holds that \[\begin{align} \mathbb{E}\bigg[ &\boldsymbol{1}[\hat{\mu}_{1,n} \geq - \epsilon] (1-p_n(\epsilon| \bar{\theta}_{1,n}))\bigg] \\ &= \mathbb{P}[-\epsilon\leq \hat{\mu}_{1,n} \leq -\epsilon/2] + \mathbb{P}[-\epsilon/2 \leq \hat{\mu}_{1,n}, \bar{S}_{1,n} \geq 2n] + \mathbb{E}\left[ \boldsymbol{1}[-\epsilon/2 \leq \hat{\mu}_{1,n}, \bar{S}_{1,n} \leq 2n] (1-p_n(\epsilon| \bar{\theta}_{1,n}))\right] \\ &= \mathbb{P}[-\epsilon\leq \hat{\mu}_{1,n} \leq -\epsilon/2] + \mathbb{P}[-\epsilon/2 \leq \hat{\mu}_{1,n}, S_{1,n} \geq 2n] + \mathbb{E}\left[ \boldsymbol{1}[-\epsilon/2 \leq \hat{\mu}_{1,n}, \bar{S}_{1,n} \leq 2n] (1-p_n(\epsilon| \bar{\theta}_{1,n}))\right] \\ &\leq e^{-\frac{\epsilon^2}{8}n} + e^{- \frac{1-\log 2}{2}n} + \mathbb{E}\left[ \boldsymbol{1}[-\epsilon/2 \leq \hat{\mu}_{1,n}, \bar{S}_{1,n} \leq 2n] (1-p_n(\epsilon| \bar{\theta}_{1,n}))\right], \end{align}\] where the second equality holds from the definition of \(\bar{S}_{1,n} = \max(1, S_{1,n})\), which implies \(\{\bar{S}_{1,n}\geq 2n\} = \{\bar{S}_{1,n}=S_{1,n}\}\) for any \(n\in \mathbb{N}\). From the symmetry of \(t\)-distribution, it holds that \[\begin{align} 1 - p_n(\epsilon|\bar{\theta}_{1,n}) = \int_{-\infty}^{-\epsilon} f^t_{n+k-2}(y; \hat{x}_{1,n}, \bar{S}_{1,n}) \mathrm{d}y &= \int_{\epsilon}^{\infty} f^t_{n+k-2}(y; -\hat{x}_{1,n}, \bar{S}_{1,n}) \mathrm{d}y \\ &= \int_{2\hat{x}_{1,n}+\epsilon}^{\infty} f^t_{n+k-2}(y; \hat{x}_{1,n}, \bar{S}_{1,n}) \mathrm{d}y \\ &= \mathbb{P}[\tilde{\mu}_1 \geq 2\hat{x}_{i,n}+\epsilon| \hat{x}_{i,n}, \bar{S}_{i,n}]. \end{align}\] From (33 ) in Lemma 10, it holds that \[\mathbb{E}\left[ \boldsymbol{1}[-\epsilon/2 \leq \hat{\mu}_{1,n}, \bar{S}_{1,n} \leq 2n] (1-p_n(\epsilon| \bar{\theta}_{1,n}))\right] \leq \frac{2\sqrt{2}}{\epsilon}\left( 1+ \frac{\epsilon^2}{8} \right)^{-\frac{n+k-3}{2}}.\] Therefore, the first term in (37 ) can be bounded as \[\label{eq:32uni95pn95decom95G95rslt1} 2\mathbb{E}\left[ \boldsymbol{1}[\hat{\mu}_{1,n} \geq - \epsilon] (1-p_n(\epsilon|\bar{\theta}_{1,n}))\right] \leq 2e^{-\frac{\epsilon^2}{8}n} + 2 e^{- \frac{1-\log 2}{2}n} + \frac{4\sqrt{2}}{\epsilon}\left( 1+ \frac{\epsilon^2}{8} \right)^{-\frac{n+k-3}{2}}.\tag{38}\] Note that the last term in (37 ) was a problematic term for TS with priors \(k \geq 1\) [12]. However, we showed that such a problem could be resolved by replacing \(S_{1,n}\) with \(\bar{S}_{1,n}\).

Finally, we evaluate the last term in (37 ). From the definition of \(\bar{S}_{1,n}\), it holds that \(\boldsymbol{1}[\bar{S}_{1,n} > 1] = \boldsymbol{1}[\bar{S}_{1,n} = S_{1,n}]\) and \(\boldsymbol{1}[\bar{S}_{1,n} = 1] = \boldsymbol{1}[S_{1,n} \leq 1]\). Therefore, \[\begin{align} \mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon] }{p_n(\epsilon|\theta_{1,n})} \right] &= \mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon, \bar{S}_{1,n} > 1 ] }{p_n(\epsilon|\bar{\theta}_{1,n})} \right] + \mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon, \bar{S}_{1,n} = 1 ] }{p_n(\epsilon|\bar{\theta}_{1,n})} \right] \\ &= \underbrace{\mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon, S_{1,n} > 1 ] }{p_n(\epsilon|\theta_{1,n})} \right]}_{(\dagger_{\mathrm{G}})} + \underbrace{\mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{\mu}_{1,n} \leq - \epsilon, S_{1,n} \leq 1 ] }{p_n(\epsilon|\theta_{1,n})} \right]}_{(\diamond_{\mathrm{G}})}. \addtocounter{equation}{1}{\label{eq:32Gauss95diff95term}} \end{align}\tag{39}\] Here, the sampling distributions of \(\hat{x}_{i,n}\) and \(S_{i,n}\) are well-known as follows: \[\label{eq:32uni95gauss95stat95pdf} \hat{x}_{i,n} \sim \mathrm{Gaussian}\left(\mu_i, \frac{\sigma_i^2}{n} \right),\frac{S_{i,n}}{\sigma_i^2} \sim \chi_{n-1}^2,\tag{40}\] where \(\chi_{n-1}^2\) denotes the chi-squared distribution with degree of freedom \(n-1\). Then, from (32 ) in Lemma 10, we obtain \[(\dagger_{\mathrm{G}}) = \frac{1}{A_{n,k}} \int_{-\infty}^{-\epsilon} \sqrt{\frac{n}{2\pi}}e^{-\frac{nx^2}{2}} \int_{1}^{\infty} \left( 1 + \frac{n(x+\epsilon)^2}{s} \right)^{\frac{n+k-2}{2}} \frac{s^{\frac{n-3}{2}}e^{-\frac{s}{2}}}{2^{\frac{n-1}{2}}\Gamma\left(\frac{n-1}{2} \right)} \mathrm{d}s \mathrm{d}x\] and \[(\diamond_{\mathrm{G}}) = \frac{1}{A_{n,k}} \mathbb{P}[S_{1,n} \leq 1] \int_{-\infty}^{-\epsilon} \sqrt{\frac{n}{2\pi}}e^{-\frac{nx^2}{2}} (1+n(x+\epsilon)^2)^{\frac{n+k-2}{2}} \mathrm{d}x\]

10.6.1 Upper bound of \((\dagger_{\mathrm{G}})\)↩︎

For \(k < 1\), Lemma 7 in [12] showed that \[\begin{align} \frac{1}{A_{n,k}} \int_{-\infty}^{-\epsilon} \sqrt{\frac{n}{2\pi}}e^{-\frac{nx^2}{2}} \int_{0}^{\infty} \left( 1 + \frac{n(x+\epsilon)^2}{s} \right)^{\frac{n+k-2}{2}} \frac{s^{\frac{n-3}{2}}e^{-\frac{s}{2}}}{2^{\frac{n-1}{2}}\Gamma\left(\frac{n-1}{2} \right)} \mathrm{d}s \mathrm{d}x \leq \mathcal{O}(ne^{-n\epsilon^2}). \end{align}\] Therefore, the following result immediately follows for \(k <1\): \[(\dagger_{\mathrm{G}}) \leq \mathcal{O}(ne^{-n\epsilon^2}).\] In the remaining proof, we focus on the case of \(k=1,2\), which corresponds to the reference prior and the Jeffreys prior, respectively. Since \(x^2 \geq (x+\epsilon)^2 + \epsilon^2\) holds for \(x \leq -\epsilon\), it holds that \[\label{eq:32dG951} (\dagger_{\mathrm{G}}) \leq \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \int_{-\infty}^{-\epsilon} \sqrt{\frac{n}{2\pi}}e^{-\frac{n(x+\epsilon)^2}{2}} \int_{1}^{\infty} \left( 1 + \frac{n(x+\epsilon)^2}{s} \right)^{\frac{n+k-2}{2}} \frac{s^{\frac{n-3}{2}}e^{-\frac{s}{2}}}{2^{\frac{n-1}{2}}\Gamma\left(\frac{n-1}{2} \right)} \mathrm{d}s \mathrm{d}x\tag{41}\] Let us consider the change of variables \[(x, s) = \left( -\epsilon- \sqrt{\frac{2zw}{n}}, 2z(1-w) \right),\] which gives \[\mathrm{d}x \mathrm{d}s = \sqrt{\frac{2z}{nw}} \mathrm{d}z \mathrm{d}w.\] Then we obtain for \(k \leq 2\) \[\begin{align} (\dagger_{\mathrm{G}}) &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \int_{0}^{1} \int_{\frac{1}{2(1-w)}}^{\infty} \left( 1 + \frac{w}{1-w}\right)^{\frac{n+k-2}{2}} \sqrt{\frac{n}{2\pi}}e^{-{zw}} \frac{(z(1-w))^{\frac{n-3}{2}}e^{-z(1-w)}}{2\Gamma\left( \frac{n-1}{2} \right)} \sqrt{\frac{2z}{nw}}\mathrm{d}z \mathrm{d}w \\ &= \frac{e^{-\frac{n\epsilon^2}{2}}}{2\sqrt{\pi}A_{n,k} \Gamma\left( \frac{n-1}{2} \right)} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{k+1}{2}} \int_{\frac{1}{2(1-w)}}^{\infty} e^{-z} z^{\frac{n}{2}-1} \mathrm{d}z \mathrm{d}w \\ &= \frac{e^{-\frac{n\epsilon^2}{2}}}{2\sqrt{\pi}A_{n,k} \Gamma\left( \frac{n-1}{2} \right)} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{k+1}{2}} \Gamma\left( \frac{n}{2}, \frac{1}{2(1-w)} \right)\mathrm{d}w \addtocounter{equation}{1}{\label{eq:32uni95gauss95ceilk}}\\ &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{2\sqrt{\pi}A_{n,k} \Gamma\left( \frac{n-1}{2} \right)} \Gamma\left( \frac{n}{2} \right) B\left( \frac{1}{2}, \frac{2}{n^{\frac{k+1}{2}}} \right) \tag*{by Lemma~\ref{lem:32gauss95MI}}\\ &\leq 2ne^{-\frac{\epsilon^2}{2}n} B\left( \frac{1}{2}, \frac{2}{n^{\frac{k+1}{2}}} \right) \tag*{by Lemma~\ref{lem:32uni95hnd95gamma95bnd}}\\ &= 2ne^{-\frac{\epsilon^2}{2}n} \frac{\Gamma(1/2)\Gamma\left(\frac{2}{n^{\frac{k+1}{2}}}\right)}{\Gamma\left(\frac{1}{2}+ \frac{2}{n^{\frac{k+1}{2}}}\right)} \leq 2ne^{-\frac{\epsilon^2}{2}n} \sqrt{\pi}\Gamma\left(\frac{2}{n^{\frac{k+1}{2}}}\right) \tag*{by (\ref{eq:32uni95BetaGamma})}. \end{align}\tag{42}\] where we used \[\label{eq:32uni95BetaGamma} B(a,b) = \frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)},~~\Gamma\left( \frac{1}{2} \right) = \sqrt{\pi},~~\Gamma(x) \geq 1, \text{ for } x \in (0, 1).\tag{43}\] By the Laurent expansion of the Gamma function around \(z=0\), it holds that \[\Gamma(z) = \frac{1}{z} - \gamma + \frac{1}{2}\left( \gamma^2 + \frac{\pi}{6}\right) z - \mathcal{O}(z^2),\] where \(\gamma\) denotes the Euler–Mascheroni constant, such that \(\gamma \in (0.57, 0.58)\).

Then, for \(k \geq 1\) and \(n\geq 2\), it holds that \[\begin{align} \Gamma\left(\frac{2}{n^{\frac{k+1}{2}}}\right) &\leq \frac{1}{2}n^{\frac{k+1}{2}} - \gamma + \frac{1}{2}\left( \gamma^2 + \frac{\pi}{6} \right) \frac{2}{n^{\frac{k+1}{2}}} \\ &\leq \frac{1}{2}n^{\frac{k+1}{2}} - \gamma + \frac{1}{2}\left( \gamma^2 + \frac{\pi}{6} \right) \frac{2}{n} \\ &\leq \frac{1}{2}n^{\frac{k+1}{2}}. \end{align}\] Therefore, for \(k \in \{ 1, 2\}\), it holds that \[(\dagger_{\mathrm{G}}) \leq \mathcal{O}(n^{\frac{k +3}{2}} e^{-n\epsilon^2}).\] Note that for \(k\in (1,2)\), the integral in (42 ) is increasing function with respect to \(k \in [1,2]\), which gives for \(k \in [1,2]\) that \[(\dagger_{\mathrm{G}}) \leq \mathcal{O}\left(n^{\frac{5}{2}} e^{-n\epsilon^2}\right).\] Therefore, we have \[\label{eq:32dagger95G} (\dagger_{\mathrm{G}}) \leq \begin{cases} \mathcal{O}\left(n e^{-n\epsilon^2}\right) &\text{if } k < 1, \\ \mathcal{O}\left(n^{\frac{\lceil k \rceil +3}{2}} e^{-n\epsilon^2}\right) &\text{if } k \in [1,2], \end{cases}\tag{44}\] where \(\lceil \cdot \rceil\) denotes the ceiling function.

10.6.2 Upper bound of \((\diamond_{\mathrm{G}})\)↩︎

Similarly to (41 ), it holds that \[\begin{align} (\diamond_{\mathrm{G}}) &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \mathbb{P}[S_{1,n} \leq 1] \int_{-\infty}^{-\epsilon} \sqrt{\frac{n}{2\pi}}e^{-\frac{n(x+\epsilon)^2}{2}} (1+n(x+\epsilon)^2)^{\frac{n+k-2}{2}} \mathrm{d}x \\ &= \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \sqrt{\frac{n}{2\pi}} \mathbb{P}[S_{1,n} \leq 1] \int_{-\infty}^{0} e^{-\frac{nx^2}{2}} (1+nx^2)^{\frac{n+k-2}{2}} \mathrm{d}x \\ &= \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \sqrt{\frac{n}{2\pi}} \mathbb{P}[S_{1,n} \leq 1] \int_{0}^{\infty} e^{-\frac{nx^2}{2}} (1+nx^2)^{\frac{n+k-2}{2}} \mathrm{d}x. \end{align}\] Here, Recall the intergral representation of the confluent hypergeometric function of the second kind in (35 ), which is \[U(a,b,z) = \frac{1}{\Gamma(a)} \int_0^{\infty} e^{-zt}t^{a-1}(1+t)^{b-a-1} \mathrm{d}t.\] Therefore, by letting \(t = nx^2\), we have \[\begin{align} (\diamond_{\mathrm{G}}) &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{A_{n,k}} \sqrt{\frac{n}{2\pi}} \sqrt{\frac{1}{2n}} \mathbb{P}[S_{1,n} \leq 1] \int_{0}^{\infty} e^{-\frac{t}{2}} t^{-\frac{1}{2}} (1+t)^{\frac{n+k-2}{2}} \mathrm{d}t \\ &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{2 A_{n,k}} \sqrt{\frac{1}{\pi}} \mathbb{P}[S_{1,n} \leq 1] U\left( \frac{1}{2}, \frac{n+k+1}{2}, \frac{1}{2} \right). \end{align}\] From Lemma 14, we obtain \[\begin{align} (\diamond_{\mathrm{G}}) &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{2 A_{n,k}} \sqrt{\frac{1}{\pi}} \mathbb{P}[S_{1,n} \leq 1] \left( \frac{3\cdot 2^{\frac{n+k-1}{2}}}{\Gamma\left(\frac{1}{2}\right)} \right) \Gamma\left( \frac{n+k}{2} \right) \\ &= \frac{3e^{-\frac{n\epsilon^2}{2}}}{\pi A_{n,k} } \mathbb{P}[S_{1,n} \leq 1] 2^{\frac{n+k-3}{2}}\Gamma\left( \frac{n+k}{2} \right) \addtocounter{equation}{1}{\label{eq:32diG951}}. \end{align}\tag{45}\] For a random variable following the chi-squared distribution with the degree of freedom \(n\), it holds for \(x \in (0,1)\) that \[\mathbb{P}[X \leq nx] \leq e^{-n \frac{x-1-\log x}{2}}.\] Since \(S_{1,n} \sim \chi^2_{n-1}\) (recall that we consider the case \(\sigma_1=1\)), by letting \(x=\frac{1}{n-1}\), we obtain \[\label{eq:32chi95concen} \mathbb{P}[S_{1,n} \leq 1] \leq e^{-\frac{2-n+ (n-1)\log (n-1)}{2}} = (n-1)^{-\frac{n-1}{2}} e^{\frac{n}{2}-1}.\tag{46}\] By combining (46 ) with (45 ), we have for \(n\geq n_0= 3\) \[(\diamond_{\mathrm{G}}) \leq \frac{3e^{-\frac{n\epsilon^2}{2}}}{\pi A_{n,k} } (n-1)^{-\frac{n-1}{2}} e^{\frac{n}{2}-1} 2^{\frac{n+k-3}{2}}\Gamma\left( \frac{n+k}{2} \right) .\] From Stirling’s formula, \[\Gamma(z) \leq \sqrt{2\pi} e^{1/6} z^{z-\frac{1}{2}}e^{-z},\] we have \[\begin{align} (\diamond_{\mathrm{G}}) &\leq \frac{3e^{-\frac{n\epsilon^2}{2}}}{\pi A_{n,k} } (n-1)^{-\frac{n-1}{2}} e^{\frac{n}{2}-1} 2^{\frac{n+k-3}{2}} \sqrt{2\pi} e^{1/6} \left( \frac{n+k}{2}\right)^{\frac{n+k-1}{2}}e^{-\frac{n+k}{2}} \\ &= \frac{3e^{-\frac{n\epsilon^2}{2}}}{\sqrt{2\pi} A_{n,k} } (n-1)^{-\frac{n-1}{2}} e^{\frac{n}{2}-1} e^{1/6} (n+k)^{\frac{n+k-1}{2}}e^{-\frac{n+k}{2}} \\ &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{\sqrt{2\pi} A_{n,k}} e^{1/6} e^{-\frac{k}{2}} (n-1)^{\frac{k}{2}}\left( \frac{n+k}{n-1} \right)^{\frac{n+k-1}{2}} \\ &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{\sqrt{2\pi} A_{n,k}} e^{1/6} e^{-\frac{k}{2}} n^{\frac{k}{2}}\left( 1+ \frac{k+1}{n-1} \right)^{\frac{n+k-1}{2}} \\ &\leq \frac{e^{-\frac{n\epsilon^2}{2}}}{\sqrt{2\pi} A_{n,k}} e^{5/6} n^{\frac{k}{2}} e^{\frac{k(k+1)}{2(n-1)}} \\ &= \mathcal{O}\left(n^{\frac{k+1}{2}} e^{-n\epsilon^2}\right). \addtocounter{equation}{1}{\label{eq:32diG95rslt}} \end{align}\tag{47}\]

10.6.3 Conclusion↩︎

Therefore, by combining (44 ) and (47 ) with (39 ), we have for \(k \in \mathbb{Z}_{\leq 2}\) \[\label{eq:32uni95pn95decom95G95rslt2} \mathbb{E}\left[ \frac{\boldsymbol{1}[\hat{x}_{1,n} \leq - \epsilon] }{p_n(\epsilon|\theta_{1,n})} \right] \leq \mathcal{O}\left(n^{\frac{m'}{2}} e^{ - n\epsilon^2}\right) + \mathcal{O}\left(n^{\frac{\max(0,k+1)}{2}} e^{-n\epsilon^2 }\right),\tag{48}\] where \(m'= 2\cdot\boldsymbol{1}[k \in \mathbb{Z}_{< 1}] + (\lceil k \rceil +3)\boldsymbol{1}[k \in [1,2]]\). Therefore, by injecting (38 ) and (48 ) to (37 ), we obtain for \(k \in \mathbb{Z}_{\leq 2}\) \[\begin{align} (\mathrm{BO}) &\leq \sum_{n=n_0}^T 2e^{-\frac{\epsilon^2}{8}n} + 2e^{-\frac{1-\log 2}{2}n} + \frac{4\sqrt{2}}{\epsilon}\left( 1 + \frac{\epsilon^2}{8} \right)^{-\frac{n+k-3}{2}} + \mathcal{O}\left(n^{\frac{m'}{2}} e^{ - n\epsilon^2}\right) + \mathcal{O}\left(n^{\frac{\max(0,k+1)}{2}} e^{-n\epsilon^2 }\right) \\ & \leq \mathcal{O}(\epsilon^{-2}) + \mathcal{O}(1) + \mathcal{O}(\epsilon^{-3}) + \mathcal{O}(\epsilon^{-(m'+2)}) + \mathcal{O}(\epsilon^{-(k+3)}). \end{align}\] Letting \(m= m'+2 = 4 + \lceil k \rceil \boldsymbol{1}[k \in [1,2]]\) concludes the proof. ◻

10.7 Proofs of technical lemmas for Lemma 5 ↩︎

In this section, we provide the all proofs of Lemmas 13 and 14 based on the mathematical induction.

Proof of Lemma 13. Define \[\begin{align} g_k(n) := \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{k+1}{2}} \Gamma\left( \frac{n}{2}, \frac{1}{2(1-w)} \right)\mathrm{d}w. \end{align}\] Here, we apply mathematical induction separately for both odd and even values of \(n\) for each \(k\in \{1,2\}\). We expect that one can extend the analysis for the case of \(k=1\) to the general \(k\) by changing the parameter \(b\) of the hypergeometric function of the second kind \(U(a,b,z)\).

10.7.1 For the reference prior (\(k=1\))↩︎

Let us consider the case of the even number \(n=2m\).

10.7.1.1 (1) Even number

Since \(n_0= \max (2, 4-k)\), it is sufficient to consider \(m\geq 2\) if \(k = 1\).

10.7.1.2 (1-i) Base case \(n=4\)

From the definition of the upper incomplete gamma function, it holds that \[\Gamma(2, x) = e^{-x}(x+1).\] By letting \(t=\frac{w}{1-w}\), we have \[\begin{align} g_1(4) &= \frac{1}{2\sqrt{e}}\int_{0}^\infty \sqrt{\frac{t+1}{t}} e^{-\frac{t}{2}} \mathrm{d}t + \frac{1}{\sqrt{e}}\int_{0}^\infty \sqrt{\frac{1}{t(t+1)}} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{e}}\left(\frac{1}{2} U\left( \frac{1}{2}, 2, \frac{1}{2} \right) + U\left( \frac{1}{2}, 1, \frac{1}{2} \right)\right). \end{align}\] Here, it holds as follows [47]: \[\begin{align} U(a,b,z) - aU(a+1, b,z) - U(a,b-1,z) &= 0, \\ (b-a)U(a,b,z) + U(a-1, b,z) - zU(a,b+1,z)&=0, \end{align}\] which gives \[\label{eq:32confluent952a} U\left( \frac{1}{2}, 2, \frac{1}{2} \right) = \frac{1}{4} U\left( \frac{3}{2}, 3, \frac{1}{2} \right) + \frac{1}{2}U\left( \frac{1}{2}, 1, \frac{1}{2} \right).\tag{49}\] Let \(K_v(z)\) denote the modified Bessel function of the second kind defined in Definition 4. Then, we have the result in [47] that \[\label{eq:32bessel95confluent} U\left(v+\frac{1}{2}, 2v+1, 2z \right) = \frac{1}{\sqrt{\pi}} e^z (2z)^{-v}K_v(z),\tag{50}\] which gives \[g_1(4) = \frac{1}{4\sqrt{e}}\left( 5 e^{1/4} K_0\left(\frac{1}{4}\right) + e^{1/4} K_1 \left(\frac{1}{4}\right) \right).\]

Here, we first show that \(e^z K_0(z)\) and \(e^z K_1(z)\) are decreasing functions with respect to \(z>0\). From the definition of \(K_v(z)\) in (36 ), it holds that \[\frac{\mathrm{d}}{\mathrm{d}z} K_v(z) = -\frac{1}{2}\left( K_{v+1}(z) + K_{v-1}(z) \right),\] which gives that \[\begin{align} \frac{\mathrm{d}}{\mathrm{d}z} e^z K_0(z) &= e^z ( K_0(z) - K_1(z) ), \\ \frac{\mathrm{d}}{\mathrm{d}z} e^z K_1(z) &= -\frac{1}{2} e^z (K_0(z) - 2K_1(z) + K_2(z)). \end{align}\] From the integral representation of \(K_v(z)\) in (36 ), it holds from \(\cosh{2t} = \cosh^2{t} -1\) that \[\begin{align} K_0(z) - K_1(z) &= \int_0^\infty e^{-z\cosh{t}}(1-\cosh{t}) \mathrm{d}t < 0 \\ K_0(z) - 2K_1(z) + K_2(z) &= \int_0^\infty e^{-z\cosh{t}} (\cosh^2 t - \cosh{t}) \mathrm{d}t >0, \end{align}\] which shows that \(e^zK_0(z)\) and \(e^z K_1(z)\) are decreasing functions with respect to \(z>0\).

Then, we obtain \[\begin{align} g_1(4) &= \frac{1}{4\sqrt{e}}\left( 5 e^{1/4} K_0\left(\frac{1}{4}\right) + e^{1/4} K_1 \left(\frac{1}{4}\right) \right) \\ &\leq \frac{1}{4e^{1/2}}\left(5 e^{0.24}K_0\left(0.24 \right) + e^{0.24} K_1 \left(0.24 \right) \right). \end{align}\] By substituting the numerical computation in Fact 5, we obtain that \[\begin{align} g_1(4)&\leq \frac{1}{4e^{1/2}}\left(5 e^{0.24}K_0\left(0.24 \right) + e^{0.24} K_1 \left(0.24 \right) \right) = 2.27811 \tag*{to 6S}\\ &< \Gamma(2)B(1/2, 1/2) = \Gamma(2)\frac{\Gamma(1/2)^2}{\Gamma(1)} = \pi, \end{align}\] which concludes the base case of even \(n\) for the reference prior (\(k=1\)).

10.7.1.3 (1-ii) Induction

Assume that the following holds for some \(m \geq 2\) \[g_1(2m) \leq \Gamma(m) B\left(\frac{1}{2}, \frac{1}{m} \right) = \Gamma(m)\frac{\Gamma(1/2)\Gamma(1/m)}{\Gamma\left( \frac{1}{2} + \frac{1}{m} \right)}.\] From the definition of \(g_1(\cdot)\) and \(\Gamma(m+1,x)=m\Gamma(m,x)+x^{m}e^{-x}\), we have \[\begin{align} g_1(2(m+1)) &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1} \Gamma\left( m+1, \frac{1}{2(1-w)} \right)\mathrm{d}w \\ &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1} \bigg(m\Gamma\left(m, \frac{1}{2(1-w)} \right) + (2(1-w))^{-m} e^{-\frac{1}{2(1-w)}}\bigg)\mathrm{d}w \\ &= mg(2m) + \frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+1)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \\ &\leq \Gamma(m+1)B\left(\frac{1}{2}, \frac{1}{m} \right)+\frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+1)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w. \end{align}\] Since \(B\left(\frac{1}{2}, \frac{1}{m+1} \right) - B\left(\frac{1}{2}, \frac{1}{m} \right)\) is a decreasing function with respect to \(m > 0\), we have for \(m \geq 2\). \[\begin{align} B\left(\frac{1}{2}, \frac{1}{m+1} \right) - B\left(\frac{1}{2}, \frac{1}{m} \right) &= \Gamma\left( \frac{1}{2} \right) \left( \frac{\Gamma\left( \frac{1}{m+1} \right)}{\Gamma\left( \frac{1}{2}+\frac{1}{m+1} \right)} - \frac{\Gamma\left( \frac{1}{m} \right)}{\Gamma\left( \frac{1}{2}+\frac{1}{k} \right)} \right) \\ &\geq \lim_{s\to \infty} \Gamma\left( \frac{1}{2} \right) \left( \frac{\Gamma\left( \frac{1}{s+1} \right)}{\Gamma\left( \frac{1}{2}+\frac{1}{s+1} \right)} - \frac{\Gamma\left( \frac{1}{s} \right)}{\Gamma\left( \frac{1}{2}+\frac{1}{s} \right)} \right) \\ &= \lim_{s\to \infty} \Gamma\left( \frac{1}{s+1} \right) - \Gamma\left( \frac{1}{s} \right) =1. \end{align}\] Therefore, it is sufficient to show \[h(2(m+1)) := \frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+1)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \leq \Gamma(m+1).\] Again, by letting \(t = \frac{w}{1-w}\), \(h\) can be written as \[\begin{align} h(2(m+1)) &= \frac{1}{2^m \sqrt{e}} \int_0^{\infty} t^{-\frac{1}{2}} (t+1)^{m-\frac{1}{2}} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{e}} \frac{1}{2^m} U\left(\frac{1}{2}, m+1, \frac{1}{2} \right). \end{align}\] From Lemma 14, it holds for \(m\geq 2\) that \[\begin{align} h(2(m+1)) &\leq \sqrt{\frac{\pi}{e}} \frac{1}{2^m} \frac{2^{m+1}}{\Gamma\left( \frac{1}{2} \right)} \Gamma\left(m +\frac{1}{2} \right) \\ &= \frac{2}{\sqrt{e}} \Gamma\left(m+ \frac{1}{2}\right) \leq \Gamma(m+1), \end{align}\] which concludes the induction when \(n\) is an even number.

10.7.1.4 (2) Odd number

Although this case can be easily derived by following the same steps in the case of even numbers, we provide detailed proof for completeness.

10.7.1.5 (2-i) Base case \(n=3\)

From the definition of the upper incomplete gamma function, it holds that \[\Gamma\left(\frac{3}{2}, x\right) = \frac{\sqrt{\pi}}{2}\mathrm{erfc}(\sqrt{x}) + \sqrt{x}e^{-x},\] where \(\mathrm{erfc}(\cdot)\) denotes the complementary error function. It is known that the complementary error function is bounded for any \(x \geq 0\) as follows [49]: \[\mathrm{erfc}(x) \leq e^{-x^2},\] which gives \[\Gamma\left(\frac{3}{2}, x\right) \leq \frac{\sqrt{\pi}}{2} e^{-x} + \sqrt{x}e^{-x}.\] Then, by letting \(t= \frac{w}{1-w}\), we obtain \[\begin{align} g_1(3) &\leq \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1} \left( \frac{\sqrt{\pi}}{2} e^{-\frac{1}{2(1-w)}} + \sqrt{\frac{1}{2(1-w)}}e^{-\frac{1}{2(1-w)}}. \right)\mathrm{d}w \\ &= \int_0^\infty \frac{\sqrt{\pi}}{2\sqrt{e}} (t(t+1))^{-\frac{1}{2}} e^{-\frac{t}{2}} + \frac{1}{\sqrt{2e}} t^{-\frac{1}{2}} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \frac{\pi}{2\sqrt{e}} U\left( \frac{1}{2}, 1,\frac{1}{2}\right) + \sqrt{\frac{2}{2e}} \Gamma\left( \frac{1}{2} \right)\\ &= \frac{\pi}{2\sqrt{e}} \frac{e^{1/4}}{\sqrt{\pi}} K_0\left(\frac{1}{4}\right) + \sqrt{\frac{\pi}{e}}\tag*{by (\ref{eq:32bessel95confluent})}\\ &\leq \frac{1}{2}\sqrt{\frac{\pi}{e}} e^{0.24}K_0\left(0.24\right) + \sqrt{\frac{\pi}{e}} = 2.15458 \tag*{to 6S}\\ &< \frac{\pi}{2} \frac{\Gamma(2/3)}{\Gamma(1.165)} \leq \frac{\pi}{2} \frac{\Gamma(2/3)}{\Gamma(7/6)} = 2.29148\tag*{to 6S}\\ & < \Gamma\left( \frac{3}{2}\right) B\left( \frac{1}{2}, \frac{2}{3} \right), \addtocounter{equation}{1}{\label{eq:32base95odd}} \end{align}\tag{51}\] where we substituted the numerical computation in Fact 5 and [50] in (51 ) to 6S.

10.7.1.6 (2-ii) Induction

Assume that the following holds for some \(m \geq 1\). \[g_1(2m+1) \leq \Gamma\left(m + \frac{1}{2}\right) B\left(\frac{1}{2}, \frac{2}{2m+1} \right) = \Gamma\left(m + \frac{1}{2}\right)\frac{\Gamma\left( \frac{1}{2} \right)\Gamma\left(\frac{2}{2m+1} \right)}{\Gamma\left( \frac{1}{2} + \frac{2}{2m+1} \right)}.\] From the definition and the fact \(\Gamma(s+1,x)=m\Gamma(s,x)+x^{s}e^{-x}\), we have \[\begin{align} g_1(2m+3) &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1} \Gamma\left( m+\frac{1}{2}+1, \frac{1}{2(1-w)} \right)\mathrm{d}w \\ &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-1} \bigg(m\Gamma\left(m+\frac{1}{2}, \frac{1}{2(1-w)} \right) + (2(1-w))^{-m-\frac{1}{2}} e^{-\frac{1}{2(1-w)}}\bigg)\mathrm{d}w \\ &= mg(2m+1) + \frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+3/2)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \\ &\leq \Gamma\left(m+\frac{3}{2}\right)B\left(\frac{1}{2}, \frac{2}{2m+1} \right) +\frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+3/2)}e^{-\frac{1}{2(1-w)}} \mathrm{d}w. \end{align}\] Since \[\begin{align} B\left(\frac{1}{2}, \frac{2}{2m+3} \right) - B\left(\frac{1}{2}, \frac{2}{2m+1} \right) &= \Gamma\left( \frac{1}{2} \right) \left( \frac{\Gamma\left( \frac{2}{2m+3} \right)}{\Gamma\left( \frac{1}{2}+\frac{2}{2m+1} \right)} - \frac{\Gamma\left( \frac{2}{2m+1} \right)}{\Gamma\left( \frac{1}{2}+\frac{2}{2m} \right)} \right) \\ &\geq 1 \end{align}\] holds for \(m \geq 2\), it is sufficient to show \[h(2m+3) := \frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+3/2)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \leq \Gamma\left(m+ \frac{3}{2}\right).\] Again, by letting \(t = \frac{w}{1-w}\), \(h(\cdot)\) can be written as \[\begin{align} h(2m+3) &= \frac{1}{2^m \sqrt{e}} \int_0^{\infty} t^{-\frac{1}{2}} (t+1)^{m} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{e}} \frac{1}{2^{m+1/2}} U\left(\frac{1}{2}, m+\frac{3}{2}, \frac{1}{2} \right). \end{align}\] From Lemma 14, it holds for all \(m\geq 1\) that \[\begin{align} h(2m+3) &\leq \sqrt{\frac{\pi}{e}} \frac{1}{2^{m+1/2}} \frac{2^{m+3/2}}{\Gamma\left( \frac{1}{2} \right)} \Gamma\left( m+1\right)\\ &= \frac{2}{\sqrt{e}}\Gamma(m+1) \leq \Gamma\left(m+ \frac{3}{2}\right). \end{align}\] The proof of Lemma 13 for the case of \(k=1\) is complete.

10.7.2 For the Jeffreys prior \((k=2)\)↩︎

The proofs here shares the same steps to that for the reference prior.

10.7.2.1 (1) Even number

Since \(n_0= (2, 4-k)\), we have to consider \(n=2\) as a base case.

10.7.2.2 (1-i) Base case \(n=2\)

From the definition of the upper incomplete gamma function, it holds that \[\Gamma(1, x) = e^{-x}.\] By letting \(t=\frac{w}{1-w}\), we have \[\begin{align} g_2(2) = \frac{1}{\sqrt{e}}\int_{0}^\infty e^{-\frac{t}{2}} t^{-\frac{1}{2}} \mathrm{d}t &= \sqrt{\frac{2}{e}}\Gamma\left( \frac{1}{2} \right)\\ &\leq \sqrt{\pi} e^{-1/6}2^{1/4}\\ &\leq \Gamma\left( \frac{1}{2} \right) \frac{ \Gamma\left( \frac{1}{\sqrt{2}} \right) }{\Gamma\left( \frac{1}{2} + \frac{1}{\sqrt{2}} \right)} = \Gamma(1) B\left( \frac{1}{2}, \frac{1}{\sqrt{2}} \right), \end{align}\] where we applied Lemma 12 in the last inequality.

10.7.2.3 (1-ii) Induction

Assume that the following holds for some \(m \geq 1\) \[g_2(2m) \leq \Gamma(m) B\left(\frac{1}{2}, \frac{1}{m\sqrt{2m}} \right) .\] From the definition and the fact \(\Gamma(m+1,x)=m\Gamma(m,x)+x^{m}e^{-x}\), we have \[\begin{align} g_2(2(m+1)) &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{3}{2}} \Gamma\left( m+1, \frac{1}{2(1-w)} \right)\mathrm{d}w \\ &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{3}{2}} \bigg(m\Gamma\left(m, \frac{1}{2(1-w)} \right) + (2(1-w))^{-m} e^{-\frac{1}{2(1-w)}}\bigg)\mathrm{d}w \\ &= mg_2(2m) + \frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\left(m+\frac{3}{2}\right)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \\ &\leq \Gamma(m+1)B\left(\frac{1}{2}, \frac{1}{m\sqrt{2m}} \right)+\frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\left(m+\frac{3}{2}\right)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w. \end{align}\] Here, it holds for \(m \geq 1\) that \[B\left(\frac{1}{2}, \frac{1}{(m+1)\sqrt{2(m+1)}} \right) - B\left(\frac{1}{2}, \frac{1}{m\sqrt{2m}} \right) \geq \sqrt{2m+2}.\] Therefore, it is sufficient to show \[h(2(m+1)) := \frac{1}{2^m} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\left(m+\frac{3}{2}\right)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \leq \sqrt{2(m+1)}\Gamma(m+1).\] Again, by letting \(t = \frac{w}{1-w}\), \(h\) can be written as \[\begin{align} h(2(m+1)) &= \frac{1}{2^m \sqrt{e}} \int_0^{\infty} t^{-\frac{1}{2}} (t+1)^{m} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{e}} \frac{1}{2^m} U\left(\frac{1}{2}, m+\frac{3}{2}, \frac{1}{2} \right). \end{align}\] From Lemma 14, it holds for \(m\geq 1\) that \[\begin{align} h(2(m+1)) &\leq \sqrt{\frac{\pi}{e}} \frac{1}{2^m} \frac{2^{m+\frac{3}{2}}}{\Gamma\left( \frac{1}{2} \right)} \Gamma\left(m +1 \right) \\ &= \frac{2\sqrt{2}}{\sqrt{e}} \Gamma\left(m+ 1\right) \leq \sqrt{2(m+1)}\Gamma(m+1), \end{align}\] which concludes the induction when \(n\) is an even number.

10.7.2.4 (2) Odd number

Although this case can be easily derived by following the same steps in the case of even numbers, we provide detailed proof for completeness.

10.7.2.5 (2-i) Base case \(n=3\)

From the definition of the upper incomplete gamma function, it holds that \[\Gamma\left(\frac{3}{2}, x\right) = \frac{\sqrt{\pi}}{2}\mathrm{erfc}(\sqrt{x}) + \sqrt{x}e^{-x},\] where \(\mathrm{erfc}(\cdot)\) denotes the complementary error function. It is known that the complementary error function is bounded for any \(x \geq 0\) as follows [49]: \[\mathrm{erfc}(x) \leq e^{-x^2},\] which gives \[\Gamma\left(\frac{3}{2}, x\right) \leq \frac{\sqrt{\pi}}{2} e^{-x} + \sqrt{x}e^{-x}.\] Then, by letting \(t= \frac{w}{1-w}\), we obtain \[\begin{align} g_2(3) &\leq \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{3}{2}} \left( \frac{\sqrt{\pi}}{2} e^{-\frac{1}{2(1-w)}} + \sqrt{\frac{1}{2(1-w)}}e^{-\frac{1}{2(1-w)}}. \right)\mathrm{d}w \\ &= \int_0^\infty \frac{\sqrt{\pi}}{2\sqrt{e}} t^{-\frac{1}{2}} e^{-\frac{t}{2}} + \frac{1}{\sqrt{2e}} t^{-\frac{1}{2}}(1+t)^{\frac{1}{2}} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{2e}} \Gamma\left( \frac{1}{2} \right) + \sqrt{\frac{\pi}{2e}} U\left( \frac{1}{2}, 2,\frac{1}{2}\right)\\ &= \frac{\pi}{\sqrt{2e}} + \frac{1}{2\sqrt{2e}} \left( e^{1/4}K_0\left(\frac{1}{4}\right) + e^{1/4}K_1\left(\frac{1}{4}\right) \right)\tag*{by (\ref{eq:32confluent952a}) and (\ref{eq:32bessel95confluent})}\\ &\leq \frac{\pi}{\sqrt{2e}} + \frac{1}{2\sqrt{2e}} \left( e^{0.24}K_0\left(0.24 \right) + e^{0.24}K_1\left(0.24\right) \right) = 2.84642 \tag*{to 6S} \\ & < \Gamma\left( \frac{3}{2}\right) B\left( \frac{1}{2}, \frac{2}{3\sqrt{3}} \right) = 3.35278 \end{align}\] where we substituted the numerical computation in Fact 5.

10.7.2.6 (2-ii) Induction

Assume that the following holds for some \(m \geq 1\). \[g_2(2m+1) \leq \Gamma\left(m + \frac{1}{2}\right) B\left(\frac{1}{2}, \frac{2}{(2m+1)\sqrt{2m+1}} \right).\] From the definition and the fact \(\Gamma(s+1,x)=m\Gamma(s,x)+x^{s}e^{-x}\), we have \[\begin{align} g_2(2m+3) &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{3}{2}} \Gamma\left( m+\frac{1}{2}+1, \frac{1}{2(1-w)} \right)\mathrm{d}w \\ &= \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-\frac{3}{2}} \bigg(m\Gamma\left(m+\frac{1}{2}, \frac{1}{2(1-w)} \right)+ (2(1-w))^{-m-\frac{1}{2}} e^{-\frac{1}{2(1-w)}}\bigg)\mathrm{d}w \\ &= mg_2(2m+1) + \frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+2)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \\ &\leq \Gamma\left(m+\frac{3}{2}\right)B\left(\frac{1}{2}, \frac{2}{(2m+1)\sqrt{2m+1}} \right) +\frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+2)}e^{-\frac{1}{2(1-w)}} \mathrm{d}w. \end{align}\] Since \[\begin{align} B\left(\frac{1}{2}, \frac{2}{(2m+3)\sqrt{2m+3}} \right) - B\left(\frac{1}{2}, \frac{2}{(2m+1)\sqrt{2m+1}} \right) \geq \sqrt{2m+3} \end{align}\] holds for \(m \geq 1\), it is sufficient to show \[h(2m+3) := \frac{1}{2^{m+1/2}} \int_{0}^{1} w^{-\frac{1}{2}} (1-w)^{-(m+3/2)} e^{-\frac{1}{2(1-w)}} \mathrm{d}w \leq \sqrt{2m+3} \Gamma\left(m+ \frac{3}{2}\right).\] Again, by letting \(t = \frac{w}{1-w}\), \(h(\cdot)\) can be written as \[\begin{align} h(2m+3) &= \frac{1}{2^{m+1/2} \sqrt{e}} \int_0^{\infty} t^{-\frac{1}{2}} (t+1)^{m+\frac{1}{2}} e^{-\frac{t}{2}} \mathrm{d}t \\ &= \sqrt{\frac{\pi}{e}} \frac{1}{2^{m+1/2}} U\left(\frac{1}{2}, m+2, \frac{1}{2} \right). \end{align}\] From Lemma 14, it holds for all \(m\geq 1\) that \[\begin{align} h(2m+3) &\leq \sqrt{\frac{\pi}{e}} \frac{1}{2^{m+1/2}} \frac{2^{m+2}}{\Gamma\left( \frac{1}{2} \right)} \Gamma\left( m+\frac{3}{2}\right)\\ &= \frac{2\sqrt{2}}{\sqrt{e}}\Gamma\left(m+\frac{3}{2}\right) \leq \sqrt{2m+3}\Gamma\left(m+ \frac{3}{2}\right). \end{align}\] The proof of Lemma 13 for the case of \(k=2\) is complete. ◻

Proof of Lemma 14. Similarly to the proof of Lemma 13, we apply mathematical induction.

10.7.2.7 Base case: \(b=2\)

When \(b=2\) (\(m=4\)), it holds from (49 ) and (50 ) that \[\begin{align} U\left( \frac{1}{2}, 2, \frac{1}{2} \right) &= \frac{1}{4}U\left( \frac{3}{2}, 2, \frac{1}{2} \right) + \frac{1}{2}U\left( \frac{1}{2}, 1, \frac{1}{2} \right) \\ &= \frac{e^{1/4}}{2\sqrt{\pi}}\left( K_0\left( \frac{1}{4} \right) + K_1\left( \frac{1}{4} \right) \right) \\ &\leq \frac{1}{2\sqrt{\pi}}\left( e^{0.24}K_0\left( 0.24 \right) + e^{0.24}K_1\left( 0.24 \right) \right) = 1.97198 \tag*{to 6S}\\ &< \frac{4}{\Gamma(1/2)}\Gamma\left( \frac{3}{2}\right) = 2, \end{align}\] where we substituted the numerical computation to 6S given in Fact 5. When \(b=2+\frac{1}{2}\) (\(m=5\)), it holds that \[U\left( \frac{1}{2}, 2+\frac{1}{2}, \frac{1}{2} \right) = 2\sqrt{2} < \frac{4\sqrt{2}}{\Gamma(1/2)}\Gamma\left( 2\right) = 4\sqrt{\frac{2}{\pi}}.\]

10.7.2.8 Induction

For the confluent hypergeometric function of the second kind, the following recurrence relation holds as follows [47] \[(b-a-1)U(a,b-1,z) + (1-b-z)U(a,b,z) + zU(a, b+1,z ) = 0.\] Injecting \(a,z=\frac{1}{2}\) gives \[\begin{align} U\left( \frac{1}{2}, b+1, \frac{1}{2} \right) &= (2b-1) U\left( \frac{1}{2}, b, \frac{1}{2} \right) - (2b-3) U\left( \frac{1}{2}, b-1, \frac{1}{2} \right) \\ &\leq (2b-1) U\left( \frac{1}{2}, b, \frac{1}{2} \right). \end{align}\] Therefore, if \[U\left( \frac{1}{2}, b, \frac{1}{2} \right) \leq \frac{2^{b}}{\Gamma\left(\frac{1}{2}\right)} \Gamma\left(b- \frac{1}{2} \right)\] holds, then we obtain \[\begin{align} U\left( \frac{1}{2}, b+1, \frac{1}{2} \right) &\leq (2b-1) \frac{2^{b}}{\Gamma\left(\frac{1}{2}\right)} \Gamma\left(b- \frac{1}{2} \right) \\ &= \frac{2^{b+1}}{\Gamma\left(\frac{1}{2}\right)} \Gamma\left(b+ \frac{1}{2} \right). \end{align}\] The proof of Lemma 14 is complete. ◻

11 Proof of the Suboptimality of TS↩︎

In this section, we provide proof of the suboptimality of TS with \(k\geq 1\) for the uniform bandits with unknown supports.

Proof of Theorem 2. Since TS-T starts from playing every arms twice, \(N_i(s) \geq 2\) holds for all \(i \in \{1, 2\}\) and \(s \geq 5\). Then, it holds for \(T \geq 5\) that \[\begin{align} \mathbb{E}[\mathrm{Reg}(T)] &= \Delta_2 \mathbb{E} \left [\sum_{t=1}^T \boldsymbol{1}[i(t) = 2] \right] \\ &\geq \Delta_2 \mathbb{E} \left[ \sum_{t=5}^T \boldsymbol{1}[i(t)=2, N_1(t) = 2] \right]. \end{align}\] Since \(N_1(t)\) denotes the number of playing arm \(1\) until round \(t\), if an event \(\{ i(s) \ne 2, N_1(s) =2 \}\) occurs for some \(s\geq 5\), then \(N_1(t) > 2\) holds for \(t > s\). Therefore, for any \(t\geq 5\), \[\begin{align} \{i(t) = 2, N_1(t) = 2 \} &\Leftrightarrow \{ \forall s \in [1, t-4] : i(s+4) = 2 \} \\ &\Leftrightarrow \{ \forall s \in [1, t-4] :\tilde{\mu}_1(s+4) < \mu_2 \}. \end{align}\] By letting \(T' = T - 4\), we have \[\begin{align} \mathbb{E}\left[\sum_{t=5}^T \boldsymbol{1}[i(t)=2, N_1(t) = 2] \right] &= \mathbb{E}\left[ \sum_{t=5}^{T} \boldsymbol{1}\left[\forall s \in [1, t-4] :\tilde{\mu}_1(s+4) < \mu_2 \right] \right] \\ &= \mathbb{E}_{x^{(1)},x^{(2)}}\left[ \sum_{s=1}^{T'} \left(\mathbb{P}\left[\tilde{\mu}_1 \leq \mu_2 \,\middle\vert\, x^{(1)}_1, x^{(2)}_1\right]\right)^s \right]. \end{align}\] Since \(\tilde{\mu}_1|\tilde{\sigma}_1 \sim \mathrm{Uni}_{\mu\sigma}(\hat{\mu}_{1,2}, \tilde{\sigma}_1-\hat{\sigma}_{1,2})\), if \(\hat{\mu}_{1,2} + \frac{\tilde{\sigma}_1-\hat{\sigma}_{1,2}}{2} \leq \mu_2\) holds, then \(\tilde{\mu}_1 \leq \mu_2\) always holds since \(\tilde{\mu}_1\) is generated from the fixed posterior distribution. Therefore, we have \[\begin{align} \mathbb{P}\left[\tilde{\mu}_1 \leq \mu_2 \,\middle\vert\, x^{(1)}_1, x^{(2)}_1\right] &\geq \boldsymbol{1}[\hat{\mu}_{1,2} \leq \mu_2] \mathbb{P}\left[\tilde{\sigma}_1 \leq 2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2} \,\middle\vert\, x^{(1)}_1, x^{(2)}_1\right], \end{align}\] since \(\tilde{\sigma}_1 \geq \hat{\sigma}_{1,2}\) holds. Therefore, we obtain that \[\begin{align} \mathbb{P}\left[\tilde{\sigma}_1 \leq 2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2} \,\middle\vert\, x^{(1)}_1, x^{(2)}_1\right] &= \boldsymbol{1}[\hat{\mu}_{1,2} \leq \mu_2] \int_{\hat{\sigma}_{1,2}}^{(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} k(k+1) \hat{\sigma}_{1,2}^k \frac{s-\hat{\sigma}_{1,2}}{s^{k+2}} \mathrm{d}s \\ &= \boldsymbol{1}[\hat{\mu}_{1,2} \leq \mu_2] \Bigg(1 - (k+1)\left( \frac{\hat{\sigma}_{1,2}}{2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} \right)^k \\ &+ k\left( \frac{\hat{\sigma}_{1,2}}{2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} \right)^{k+1} \Bigg) \\ &\geq \boldsymbol{1}[\hat{\mu}_{1,2} \leq \mu_2] \left(1 - (k+1)\left( \frac{\hat{\sigma}_{1,2}}{2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} \right)^k \right) \\ &\geq \boldsymbol{1}[x^{(2)}_1 \leq \mu_2] \left(1 - (k+1)\left( \frac{\hat{\sigma}_{1,2}}{2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} \right)^k \right) \tag*{\text{by x^{(2)}_1 \geq \hat{\mu}_{1,2}}} \end{align}\] For simplicity, let us define \[\begin{align} q_n(k) = q(k|x^{(1)}_1, x^{(2)}_1) &= \boldsymbol{1}[x^{(2)}_1 \leq \mu_2] \left(1 - (k+1)\left( \frac{\hat{\sigma}_{1,2}}{2(\mu_2-\hat{\mu}_{1,2}) + \hat{\sigma}_{1,2}} \right)^k \right) \\ &= \boldsymbol{1}[x^{(2)}_1 \leq \mu_2] \left(1 - (k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k \right). \end{align}\] Then, it holds that \[\begin{align} \mathbb{E}_{x^{(1)},x^{(2)}}\left[ \sum_{s=1}^{T'} \left(\mathbb{P}\left[\tilde{\mu}_1 \leq \mu_2 \,\middle\vert\, x^{(1)}_1, x^{(2)}_1\right]\right)^s \right] &\geq \mathbb{E}_{x^{(1)},x^{(2)}}\left[ \sum_{s=1}^{T'} \left(q_n(k)\right)^s \right] \\ &= \mathbb{E}_{x^{(1)},x^{(2)}}\left[ \left(1-(q_n(k))^{T'}\right)\frac{q_n(k)}{1-q_n(k)} \right]\\ &\geq \frac{1}{2}\mathbb{E}_{x^{(1)},x^{(2)}}\left[ \boldsymbol{1}[x^{(2)}_1 \leq \mu_2, \, (q_n(k))^{T'} \leq 1/2] \frac{q_n(k)}{1-q_n(k)} \right] \\ &\geq \frac{1}{2}\mathbb{E}_{x^{(1)},x^{(2)}}\left[ \frac{ \boldsymbol{1}\left[x^{(2)}_1 \leq \mu_2, \, (q_n(k))^{T'} \leq 1/2\right] }{(k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k } \right] - \frac{1}{2}. \end{align}\] Here, it holds that \[\begin{align} (q_n(k))^{T'} \leq 1/2 &\Leftrightarrow \left(1 - (k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k \right)^{T'} \leq \frac{1}{2} \\ &\Leftrightarrow 1 - (k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k \leq 2^{-\frac{1}{T'}} \\ &\Leftrightarrow 1-2^{-\frac{1}{T'}}\leq (k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k \\ &\Leftarrow \frac{\log 2}{T'} \leq (k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k. \end{align}\] From Lemma 6 with \(n=2\), it holds that \[\begin{align} \mathbb{E}_{x^{(1)},x^{(2)}}\left[ \frac{ \boldsymbol{1}\left[x^{(2)}_1 \leq \mu_2, \, (q_n(k))^{T'} \leq 1/2\right] }{(k+1)\left( \frac{x^{(2)}_1-x^{(1)}_1}{2(\mu_2-x^{(1)}_1)} \right)^k } \right] &= \iint\limits_{\substack{ a_1 \leq y \leq z \leq \mu_2, \\ \frac{\log 2}{(k+1)T'} \leq \left( \frac{z-y}{2(\mu_2-y)} \right)^k}} 2\sigma_2^{-2} \frac{(2(\mu_2 -y))^k}{(k+1)(z-y)^k}\mathrm{d}z \mathrm{d}y \\ &= \frac{2}{\sigma_2^2}\int_{a_1}^{\mu_2} \int_{y+2(\mu_2-y)B_k}^{\mu_2} \frac{(2(\mu_2 -y))^k}{(k+1)(z-y)^k} \mathrm{d}z \mathrm{d}y, \end{align}\] where we denoted \(B_k=\left( \frac{\log 2}{T' (k+1)} \right)^{1/k}\). Then, by direct computation, we obtain for \(k=1\) \[\begin{align} \frac{2}{\sigma_2^2}\int_{a_1}^{\mu_2} \int_{y+2(\mu_2-y)A_1}^{\mu_2} \frac{2(\mu_2 -y)}{2(z-y)} \mathrm{d}z \mathrm{d}y &= \frac{1}{\sigma_2^2}\int_{a_1}^{\mu_2} 2(\mu_2-y)\log\left( \frac{2T'}{\log 2} \right) \mathrm{d}y \\ &=\frac{1}{\sigma_2^2} \left(\mu_2 - a_1 \right)^2 \log\left( \frac{2T'}{\log 2} \right) \\ &= \frac{1}{4}\log\left( \frac{2T'}{\log 2} \right) \addtocounter{equation}{1}{\label{eq:32B95k1}} \end{align}\tag{52}\] and for \(k\geq 2\) that \[\begin{align} \frac{2}{\sigma_2^2}\int_{a_1}^{\mu_2} \int_{y+2(\mu_2-y)B_k}^{\mu_2} \frac{(2(\mu_2 -y))^k}{(k+1)(z-y)^k} \mathrm{d}z \mathrm{d}y &= \frac{2}{(k^2-1)\sigma_2^2} \int_{a_1}^{\mu_2} 2(\mu_2-y) \left( \frac{1}{A^{k-1}} - 2^{k-1} \right) \mathrm{d}y\\ &= \frac{2}{(k^2-1)\sigma_2^2} \left(\mu_2 - a_1 \right)^2 \left( \frac{1}{B_k^{k-1}} - 2^{k-1} \right) \\ &= \frac{1}{2(k^2-1)} \left( \left( \frac{(k+1)T'}{\log 2} \right)^{\frac{k-1}{k}} - 2^{k-1} \right), \addtocounter{equation}{1}{\label{eq:32B95kk}} \end{align}\tag{53}\] where (52 ) and (53 ) hold from the assumption \[a_1 = a_2,~~~~\text{and}~~~~(\mu_2, \sigma_2) = \left( \frac{a_2+b_2}{2} ,b_2 - a_2\right).\] Note that for \(T' \geq 1\) and \(k\geq 2\), \(B_k < \frac{1}{2}\) holds. ◻

12 Numerical Validation in Gaussian Bandits↩︎

In this section, we present simulation results to validate the theoretical analysis of TS-T in Gaussian bandits (with unknown location and scale parameters). To provide a baseline for comparison, we present the results of asymptotically optimal UCB-based policies, CHK-UCB for the Gaussian bandits [51] where “CHK” is the initials of the authors following the notation in the original paper.

Following the previous study [51], we considered a \(6\)-armed Gaussian bandit instance with parameters \(\boldsymbol{\mu}=(10, 9, 8, 7, -1, 0)\) and \(\boldsymbol{\sigma} = (2\sqrt{2} , 1, 1 , \sqrt{0.5} , 1 , 2)\). In Figure 3, the solid lines denote the averaged regret over 10,000 independent runs of the policy that was found to be optimal in terms of the regret lower bound with (4 ), whereas the dashed lines denote that of the suboptimal policies. The dotted lines denote the asymptotic regret lower bound. Recall that the Jeffreys prior (\(k=2\)) coincides with the uniform prior with the location-rate parameterizations (\(\mu, \sigma^{-1}\)).

Based on the theoretical results of TS and TS-T, one can expect that TS and TS-T in the Gaussian bandits will show a similar tendency to that in simulations of the uniform bandits. As we expect, TS with the uniform prior \(\pi_{\mathrm{u}}^{{\mu, \sigma}}\) shows the best performance, while TS with two invariant priors shows the suboptimal performance in Figure 3 (a). One can see the similar behavior of TS-T in the Gaussian bandits in Figure 3 (b), where the performance of the reference prior significantly improves and seems to achieve the optimality.

References↩︎

[1]

Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6 (1): 4–22, 1985.

[2]

Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17 (2): 122–142, 1996.

[3]

Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems, volume 24, 2011.

[4]

William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25 (3/4): 285–294, 1933.

[5]

Robert E Kass and Larry Wasserman. The selection of prior distributions by formal rules. Journal of the American Statistical Association, 91 (435): 1343–1370, 1996.

[6]

Christian P. Robert. The Bayesian choice: from decision-theoretic foundations to computational implementation. Springer, 2nd edition, 2007.

[7]

Pierre Simon Laplace. Théorie analytique des probabilités. Courcier, 1820.

[8]

Gauri Sankar Datta and Malay Ghosh. On the invariance of noninformative priors. The Annals of Statistics, 24 (1): 141–159, 1996.

[9]

Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International Conference on Algorithmic Learning Theory, pages 199–213, 2012.

[10]

Nathaniel Korda, Emilie Kaufmann, and Remi Munos. Thompson sampling for 1-dimensional exponential family bandits. In Advances in Neural Information Processing Systems, 2013.

[11]

Malay Ghosh. Objective priors: An introduction for frequentists. Statistical Science, 26 (2): 187–202, 2011.

[12]

Junya Honda and Akimichi Takemura. Optimality of Thompson sampling for Gaussian bandits depends on priors. In International Conference on Artificial Intelligence and Statistics, 2014.

[13]

Jongyeong Lee, Junya Honda, Chao-Kai Chiang, and Masashi Sugiyama. Optimality of Thompson sampling with noninformative priors for Pareto bandits. In International Conference on Machine Learning, 2023.

[14]

James O Berger and José M Bernardo. On the development of the reference prior method. Bayesian Statistics, 4 (4): 35–60, 1992.

[15]

Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. : Minimax optimal Thompson sampling. In International Conference on Machine Learning, pages 5074–5083, 2021.

[16]

Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Annual Conference on Learning Theory, pages 39–1, 2012.

[17]

Wesley Cowan and Michael N Katehakis. An asymptotically optimal policy for uniform bandits of unknown support, 2015.

[18]

Robert Tibshirani. Noninformative priors for one parameter of many. Biometrika, 76 (3): 604–608, 1989.

[19]

Anna Nicolaou. Bayesian intervals with good frequentist behaviour in the presence of nuisance parameters. Journal of the Royal Statistical Society: Series B (Methodological), 55 (2): 377–390, 1993.

[20]

Gauri Sankar Datta and Rahul Mukerjee. Probability Matching Priors: Higher Order Asymptotics: Higher Order Asymptotics, volume 178. Springer Science & Business Media, 2004.

[21]

David Blackwell and RV Ramamoorthi. A Bayes but not classically sufficient statistic. The Annals of Statistics, 10 (3): 1025–1026, 1982.

[22]

DS Moore. Maximum likelihood and sufficient statistics. The American Mathematical Monthly, 78 (1): 50–52, 1971.

[23]

Nima Hamidi and Mohsen Bayati. On worst-case regret of linear Thompson sampling, 2020.

[24]

Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling. Journal of the Association for Computing Machinery, 64 (5): 1–24, 2017.

[25]

Arvind Agarwal and Hal Daumé. A geometric view of conjugate priors. Machine Learning, 81: 99–113, 2010.

[26]

Jerzy Neyman. Su un teorema concernente le cosiddette statistiche sufficienti. Istituto Italiano degli Attuari, 1936.

[27]

Paul R Halmos and Leonard J Savage. Application of the Radon-Nikodym theorem to the theory of sufficient statistics. The Annals of Mathematical Statistics, 20 (2): 225–241, 1949.

[28]

Harold Jeffreys. Theory of probability and inference. Cambridge University Press, London. MR0745621, 3rd edition, 1961.

[29]

Peter Orbanz. Functional conjugacy in parametric Bayesian models. Technical report, Technical report, Univ. Cambridge, 2009.

[30]

Roger M Hill. Applying Bayesian methodology with a uniform prior to the single period inventory model. European Journal of Operational Research, 98 (3): 555–562, 1997.

[31]

Anne Randi Syversveen. Noninformative Bayesian priors. interpretation and problems with construction and applications. Preprint statistics, 3 (3): 1–11, 1998.

[32]

Erich L Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2nd edition, 2006.

[33]

Shun-ichi Amari. Information geometry and its applications, volume 194. Springer, 2016.

[34]

Christian P Robert, Nicolas Chopin, and Judith Rousseau. Rejoinder: Harold Jeffreys’s theory of probability revisited. Statistical Science, 24 (1): 191–194, 2009.

[35]

Mark J Schervish. Theory of statistics. Springer Science & Business Media, 2012.

[36]

Gauri Sankar Datta and Malay Ghosh. Some remarks on noninformative priors. Journal of the American Statistical Association, 90 (432): 1357–1363, 1995.

[37]

Jose M Bernardo. Reference posterior distributions for Bayesian inference. Journal of the Royal Statistical Society: Series B (Methodological), 41 (2): 113–128, 1979.

[38]

BL Welch and HW Peers. On formulae for confidence points based on integrals of weighted likelihoods. Journal of the Royal Statistical Society: Series B (Methodological), 25 (2): 318–329, 1963.

[39]

Gauri Sankar Datta and Trevor J Sweeting. Probability matching priors. Handbook of Statistics, 25: 91–114, 2005.

[40]

Thomas J DiCiccio, Todd A Kuffner, and G Alastair Young. A simple analysis of the exact probability matching prior in the location-scale model. The American Statistician, 71 (4): 302–304, 2017.

[41]

Rahul Mukerjee and Malay Ghosh. Second-order probability matching priors. Biometrika, 84 (4): 970–975, 1997.

[42]

HW Peers. On confidence points and bayesian probability points in the case of several parameters. Journal of the Royal Statistical Society: Series B (Methodological), 27 (1): 9–16, 1965.

[43]

James O Berger, José M Bernardo, and Dongchu Sun. The formal definition of reference priors. The Annals of Statistics, 37 (2): 905–938, 2009.

[44]

Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration is fast and optimal. In International Conference on Machine Learning, 2023.

[45]

Charles Riou and Junya Honda. Bandit algorithms based on Thompson sampling for bounded reward distributions. In International Conference on Algorithmic Learning Theory, pages 777–826. PMLR, 2020.

[46]

Francesco Tricomi. Sulle funzioni ipergeometriche confluenti. Annali di Matematica Pura ed Applicata, 26 (1): 141–175, 1947.

[47]

Frank WJ Olver, Daniel W Lozier, Ronald F Boisvert, and Charles W Clark. NIST handbook of mathematical functions hardback and CD-ROM. Cambridge university press, 2010.

[48]

George Neville Watson. A treatise on the theory of Bessel functions, volume 3. The University Press, 1922.

[49]

M.K. Simon and D. Divsalar. Some new twists to problems involving the Gaussian probability integral. IEEE Transactions on Communications, 46 (2): 200–210, 1998. .

[50]

Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1964.

[51]

Wesley Cowan, Junya Honda, and Michael N Katehakis. Normal bandits of unknown means and variances. The Journal of Machine Learning Research, 18 (1): 5638–5665, 2017.

JL is now affiliated with Seoul National University.↩︎
This does not necessarily imply that this approach cannot provide the optimal solution to our problem. Therefore, one might be able to show its suboptimality in a similar way to Theorem 2 or set adaptive inflation \(\rho_t\) to achieve the regret lower bounds in (3 ) and (4 ) asymptotically although it would be more difficult than our approach in the multiparameter bandit models.↩︎
Although the reference priors are invariant under the transformation that preserves the group order of parameters in general [8], it is invariant under any one-to-one transformation in the LS family [11].↩︎
For instance, in the case of the Gaussian distribution with \(\theta = (\mu, \sigma)\), we can set \(\theta_{(1)} = \mu\) and \(\theta_{(2)} = \sigma\) when our main objective is to estimate \(\mu\).↩︎
Note that some papers call a prior the \(k\)-th order matching prior when a remainder is \(\mathcal{O}(n^{-k/2})\) [39]. Here, we follow the notations used in [11], [40], and [41]↩︎

The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models