\section{Introduction}
\input{sections/1intro.tex}

\section{Preliminaries}\label{sec: preliminaries}
\input{sections/2prelim.tex}

\section{Thompson sampling and probability matching priors}\label{sec: TS}
\input{sections/3ts.tex}

\section{Main results}\label{sec: main}
\input{sections/4main.tex}

\section{Experiments}\label{sec: experiments}
\input{sections/5exp.tex}

\section{Proof outline of optimal results}\label{sec: optimality}
\input{sections/6pf.tex}

\section{Conclusion}\label{sec: conclusion}
We considered the MAB problems under the Pareto distribution that has a heavy tail and follows the power-law.
While most previous research on TS has focused on one-dimensional or light-tailed distributions, we focused on the Pareto distribution characterized by unknown scale and shape parameters.
By sequentially sampling parameters via their marginalized and conditional posterior distributions, we can realize an efficient sampling procedure.
We showed that TS with the appropriate choice of priors achieves a problem-dependent optimal regret bound in such a setting for the first time.
Although the Jeffreys prior and the reference prior are shown to be suboptimal under the direct implementation of TS, we showed that they can achieve the optimal regret bound if we add a truncation procedure.
Experimental results support our theoretical results, which show the optimality of conservative priors and the effectiveness of the truncation procedure for the Jeffreys prior and the reference prior.

\section*{Acknowledgement}
JL was supported by JST SPRING, Grant Number JPMJSP2108.
CC and MS were supported by the Institute for AI and Beyond, UTokyo.



\subsection{Notations}
We consider the stochastic $K$-armed bandit problem where the rewards are generated from Pareto distributions with fixed parameters.
An agent chooses an arm $a$ in $[K]:=\{1, \ldots, K \}$ at each round $t \in \mathbb{N}$ and observes an independent and identically distributed reward from $\mathrm{Pa}(\kappa_a, \alpha_a)$, where $\mathrm{Pa}({\kappa, \alpha})$ denotes the Pareto distribution parameterized by scale $\kappa >0$ and shape $\alpha>0$.
This has the density function of form
\begin{equation}\label{eq: pdfPar}
  f_{{\kappa, \alpha}}^{\mathrm{Pa}}(x) = \frac{\alpha \kappa^\alpha}{x^{\alpha+1}}\mathbbm{1}[x \geq \kappa],
\end{equation}
where $\mathbbm{1}[\cdot]$ denotes the indicator function.
We consider a bandit model where parameters $\theta_a = (\kappa_a, \alpha_a) \in \mathbb{R}_{+} \times (1, \infty)$ are unknown to the agent.
We denote the mean of a random variable following $\mathrm{Pa}(\theta_a)$ by $\mu_a = \mu(\theta_a) := \frac{\kappa_a \alpha_a}{\alpha_a -1}$.
Note that $\alpha >1$ is a necessary condition of an arm to have a finite mean, which is required to define the sub-optimality gap $\Delta_a := \max_{i\in [K]}\mu_i - \mu_a$.
We assume without loss of generality that arm $1$ has the maximum mean for simplicity, i.e., $\mu_1 = \max_{i \in [K]} \mu_i$.
Let $j(t)$ be the arm played at round $t\in\mathbb{N}$ and $N_a(t)=\sum_{s=1}^{t-1}\mathbbm{1}[j(s)=a]$ denote the number of rounds the arm $a$ is played until round~$t$.
Then, the regret at round $T$ is given as
\begin{equation*}
    \mathrm{Reg}(T) = \sum_{t=1}^T \Delta_{j(t)} = \sum_{a=2}^K \Delta_a N_a(T+1).
\end{equation*}
Let $r_{a,n}$ be the $n$-th reward generated from the arm $a$.
In the Pareto distribution, the maximum likelihood estimators (MLEs) of ${\kappa, \alpha}$ for arm $a$ given $n$ rewards and their distributions are given as follows~\citep{malik1970estimation}:
\begin{align*}
    \hat{\kappa}_a(n) = \min_{s \in [n]} r_{a,s} \sim \mathrm{Pa}(\kappa_a, n\alpha_a), ~~~~
    \hat{\alpha}_a(n) = \frac{n}{ \sum_{s=1}^{n} \log(r_{a,s}) - n\log \hat{\kappa}_a(n)} \sim \mathrm{IG}(n-1, n\alpha_a), \numberthis{\label{eq: MLEdist}}
\end{align*}
where $\mathrm{IG}(n, \alpha)$ denotes the inverse-gamma distribution with shape $n>0$ and scale $\alpha>0$.
Note that \citet{malik1970estimation} further showed the stochastic independence of $\hat{\alpha}(n)$ and $\hat{\kappa}(n)$.

\subsection{Asymptotic lower bound}
\citet{burnetas1996optimal} provided a problem-dependent lower bound of the expected regret such that any uniformly fast convergent policy, which is a policy satisfying $\mathrm{Reg}(T) = o(t^\alpha)$ for all $\alpha \in (0,1)$, must satisfy
\begin{equation}\label{eq: lowerbound}
     \liminf_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T}
    \geq \sum_{a=2}^K \frac{\Delta_a}{\inf_{\theta: \mu(\theta) > \mu_1} \mathrm{KL}(\mathrm{Pa}(\kappa_a, \alpha_a), \mathrm{Pa}(\theta))},
\end{equation}
where $\mathrm{KL}(\cdot, \cdot)$ denotes the Kullback-Leibler (KL) divergence.
Notice that the bandit model $(\theta_a)_{a\in[K]}$ is considered as a fixed constant in the problem-dependent analysis.

The KL divergence between Pareto distributions is given as
\begin{align*}
    \mathrm{KL}(\mathrm{Pa}(\kappa_1, \alpha_1),\mathrm{Pa}(\kappa_2, \alpha_2)) = \begin{cases}
    \log\left(\frac{\alpha_1}{\alpha_2}\right) + \alpha_2 \log\left(\frac{\kappa_1}{\kappa_2}\right) + \frac{\alpha_2}{\alpha_1} - 1 &\text{if } \kappa_2 \leq \kappa_1, \\
    \infty &\text{otherwise}.
    \end{cases}
\end{align*}
Here the divergence sometimes becomes infinity since the scale parameter $\kappa$ determines the support of the Pareto distribution.
We denote the numerator in (\ref{eq: lowerbound}) for $a \ne 1$ by
\begin{align*}
    \mathrm{KL}_{\mathrm{inf}}(a) &:= \inf_{\theta: \mu(\theta) > \mu_1} \mathrm{KL}(\mathrm{Pa}(\kappa_a, \alpha_a), \mathrm{Pa}(\theta))
    \\  &= \inf_{\theta\in \Theta_a} \log \frac{\alpha_a}{\alpha} +  \alpha \log \frac{\kappa_a}{\kappa} + \frac{\alpha}{\alpha_a} -1,
\end{align*}
where
\begin{equation}\label{eq: thetaset}
    \Theta_a  = \left\{ (\kappa, \alpha) \in (0, \kappa_a] \times (0,\infty) : \mu({\kappa, \alpha}) > \mu_1 \right\}.
\end{equation}
Notice that $\Theta_a$ allows parameters whose expected rewards are infinite ($\alpha \in (0,1]$), although we consider a bandit model with $\alpha_a >1$ for all $a\in[K]$ so that the sub-optimality gap $\Delta_a$ becomes finite.
This implies that $\mathrm{KL}_{\mathrm{inf}}(a)$ does not depend on whether the agent considers the possibility that an arm has the infinite expected reward or not.
Then, we can simply rewrite the lower bound in (\ref{eq: lowerbound}) as
\begin{equation*}
     \liminf_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \geq \sum_{a=2}^K \frac{\Delta_a}{\mathrm{KL}_{\mathrm{inf}}(a)}.
\end{equation*}
The following lemma shows the closed form of this infimum, whose proof is given in Appendix~\ref{sec: L1proof}.
\begin{restatable}{lemma}{lemKLinf}\label{lem: KLinf}
For any arm $a \ne 1$, it holds that
\begin{equation*}
        \mathrm{KL}_{\mathrm{inf}}(a) = \log\left(\alpha_a\frac{\mu_1-\kappa_a}{\mu_1}\right) + \frac{1}{\alpha_a}\frac{\mu_1}{\mu_1-\kappa_a} -1.
\end{equation*}
\end{restatable}

\subsection{Relation with bounded moment models}
In MAB literature, several algorithms based on the upper confidence bound (UCB) were proposed to tackle heavy-tailed models with infinite variance under additional assumptions on moments~\citep{bubeck2013bandits}.
One major assumption is that the moment of any arm $a$ satisfies $\mathbb{E}[|r_{a,n}|^{\gamma}] \leq v$ for some fixed $\gamma \in [1,2)$ and known $v<\infty$~\citep{bubeck2013bandits}.
Note that the $\gamma$-th raw moment of the density function of $X$ following $\mathrm{Pa}({\kappa, \alpha})$ is given as 
\begin{equation*}
    \mathbb{E}\left[X^\gamma \right] = 
    \begin{cases}
        \infty & \alpha \leq \gamma, \\
        \frac{\alpha \kappa^\gamma}{\alpha - \gamma} & \alpha > \gamma,
    \end{cases}
\end{equation*}
which implies that the Pareto models and the bounded moment models are not a subset of each other.

Recently, \citet{agrawal2021regret} proposed an asymptotically optimal KL-UCB based algorithm that requires solving the optimization problem at every round.
Since the bounded moment model only covers certain Pareto distributions in general, the known optimality result of KL-UCB does not necessarily imply the optimality in the sense of (\ref{eq: lowerbound}).
\subsection{Sampling procedure}
Let $\mathcal{F}_t := ( j(s), r_{j(s), N_{j(s)}(s)})_{s=1}^{t-1}$ be the history until round $t$.
Under the prior $\frac{\alpha^{-k}}{\kappa}$ with $k\in\mathbb{Z}$, the marginalized posterior distribution of the shape parameter of arm $a$ is given as
\begin{equation}\label{eq: pdfalpha}
    \alpha_a \mid \mathcal{F}_t \sim \mathrm{Erlang}\left(N_a(t)-k, \frac{N_a(t)}{\hat{\alpha}_a(N_a(t))}\right),
\end{equation}
where $\mathrm{Erlang}(s, \beta)$ denotes the Erlang distribution with shape $s$ and rate $\beta$.
Note that we require $\bar{n} \geq \max\{ 2, k+1\}$ initial plays to avoid improper posteriors and MLE of $\alpha$.
When the shape parameter $\alpha_a$ is given as $\beta$, the cumulative distribution function (CDF) of the conditional posterior of $\kappa_a$ is given as~
\begin{equation}\label{eq: cdfkappa}
    \mathbb{P}\left[\kappa_a \leq x \mid \mathcal{F}_t, \alpha_a=\beta \right] = \left( \frac{x}{\hat{\kappa}_a(N_a(t))}\right)^{\beta N_a(t)},
\end{equation}
if $0 < x \leq \hat{\kappa}_a(N_a(t))$.
Since one can derive the posteriors following the same steps as \citet{Pareto_inference}, the detailed derivation is postponed to Appendix~\ref{sec: derivation_posterior}.
At round $t$, we denote the sampled scale and shape parameters of arm $a$ by $\tilde{\kappa}_a(t)$ and $\tilde{\alpha}_a(t)$, respectively, and the corresponding mean reward by $\tilde{\mu}_a(t) := \mu(\tilde{\kappa}_a(t), \tilde{\alpha}_a(t))$.
We first sample the shape parameter from the marginalized posterior in (\ref{eq: pdfalpha}).
Then, we sample the scale parameter given the sampled shape parameter from the CDF of the conditional posterior in (\ref{eq: cdfkappa}) by using inverse transform sampling.
TS based on this sequential procedure, which we call Sequential Thompson Sampling ($\mathrm{STS}$), can be formulated as Algorithm~\ref{alg: STS}.

In Theorem~\ref{thm: RegSubOopt} given in the next section, $\mathrm{STS}$ with the Jeffreys prior and the reference prior turns out to be suboptimal in view of the lower bound in (\ref{eq: lowerbound}).
Their suboptimality is mainly due to the behavior of the posterior in (\ref{eq: pdfalpha}) when $\hat{\alpha}_1(n)$ is overestimated for small $N_1(t)=n$.
To overcome such issues, we propose the $\mathrm{STS}\text{-}\mathrm{T}$ policy, a variant of $\mathrm{STS}$ with \underline{t}runcation, where we replace $\hat{\alpha}(n)$ with $\bar{\alpha}(n) := \min\left( n, \hat{\alpha}(n) \right)$ in (\ref{eq: pdfalpha}).
Note that such a truncation procedure is especially considered in the posterior sampling by (\ref{eq: pdfalpha}) and (\ref{eq: cdfkappa}).
We show that $\mathrm{STS}\text{-}\mathrm{T}$ with the Jeffreys prior and the reference prior can achieve the optimal regret bound in Theorem~\ref{thm: RegOptTruncation}.

\subsection{Interpretation of the prior parameter $k$}\label{sec: interpretation}
The Erlang distribution is a special case of the Gamma distribution, where the shape parameter is a positive integer.
If a random variable $X$ follows $\mathrm{Erlang}(s,\beta)$, then it has the density of form
\begin{equation}\label{eq: pdf_erlang}
    f_{s, \beta}^{\mathrm{Er}}(x) = \frac{\beta^s}{\Gamma(s)}x^{s-1}e^{-\beta x} \mathbbm{1}[x\in\mathbb{R}_{+}],
\end{equation}
where $s \in \mathbb{N}$ and $\beta>0$ denote the shape and rate parameter, respectively.
Then, the CDF evaluated at $x>0$ is given as
\begin{equation} \label{eq: def_inc_gamma}
    F_{s,\beta}^{\mathrm{Er}}(x) = \frac{\int_0^{\beta x} t^{s-1 } e^{-t}\mathrm{d} t}{\Gamma(s)} = \frac{\gamma(s, \beta x)}{\Gamma(s)},
\end{equation}
where $\gamma(\cdot, \cdot)$ denotes the lower incomplete gamma function.
Since $\gamma(s+1, x) = s\gamma(s,x) -x^s e^{-x}$ holds, one can observe that for any $x >0$
\begin{equation}\label{eq: CDF_dec}
    F_{s,\beta}^{\mathrm{Er}}(x) \geq F_{s+1,\beta}^{\mathrm{Er}}(x).
\end{equation}
From the sampling procedure of $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$, $\tilde{\mu}$ depends on $\tilde{\kappa}$ only when $\tilde{\alpha} > 1$ holds since $\tilde{\alpha} \leq 1$ results in $\tilde{\mu}(\cdot, \tilde{\alpha}) = \infty$. 
Therefore, for any $\beta > 1$ in (\ref{eq: cdfkappa}), $\tilde{\kappa}$ will concentrate on $\hat{\kappa}$ for sufficiently large $N_a(t)=n$.
Thus, $\tilde{\mu}$ will be mainly determined by $\tilde{\alpha}$ and $\hat{\kappa}$, where the choice of $k$ affects the sampling of $\tilde{\alpha}$ by (\ref{eq: pdfalpha}).
From (\ref{eq: CDF_dec}), one could see that the probability of sampling small $\tilde{\alpha}$ increases as shape $n-k$ decreases.
Therefore, $\tilde{\mu}$ of suboptimal arms would increase as $k$ increases for the same $n$.
In other words, the probability of sampling large $\tilde{\mu}$ becomes large as $k$ increases.
Therefore, TS with large $k$ becomes a conservative policy that could frequently play currently suboptimal arms. 
In contrast, priors with small $k$ yield an optimistic policy that focuses on playing the current best arm.



\section{Notations}
Tables~\ref{tab: 1}--\ref{tab: 4} summarize the symbols used in this paper.

\begin{table}[!ht]
\caption{Notations for the bandit problem.}
\label{tab: 1}
\centering
\begin{tabular}{ll}
    \toprule
      Symbol  &  Meaning\\
     \midrule
     $K$ & the number of arms. \\
     $T$ & time horizon. \\ 
     $j(t)$ & the index of the played arm at round $t$. \\
     $k\in\mathbb{Z}$ & prior parameter, see Section~\ref{sec: TS} for details. \\
     $\bar{n} =\max(2, k+1)$ & initial plays to avoid improper posteriors. \\
     $N_a(t)$ & the number of playing arm $a$ until round $t$.\\
     $r_{a,n}$ & $n$-th reward generated from the arm $a$.\\
     $\mu(\theta)$ &  the expected value of the random variable following $\mathrm{Pa}(\theta)$.\\
     $\mu_a = \mu(\theta_a)$ & the expected rewards of arm $a$. \\
     $\Delta_a$ & sub-optimality gap of arm $a$.\\
     $\delta_a = \frac{\Delta_a}{2}$ for $a\ne 1$ & a half of sub-optimality gap of arm $a$.\\
     $\delta_1 := \min_{a\ne 1} \delta_a$ & defined as the minimum of sub-optimality gap.\\
     $\mathcal{F}_t=(j(s),r_{j(s),N_{j(s)}})_{s=1}^{t-1}$ & the history until round $t$. \\
     $\mathbb{P}_t[\cdot]:=\mathbb{P}[\cdot | \mathcal{F}_t]$ & conditional probability given $\mathcal{F}_t$.\\
     $g_a(c, \alpha)$ & KL-divergence from $\mathrm{Pa}\left( \frac{\kappa_a}{c},\alpha \right)$ to $\mathrm{Pa}(\kappa_a, \alpha_a)$ for $c \geq 1$.\\
     $h_a(c,\boldsymbol{\mu}) = h_a(c)$ & the upper bound of $\alpha$ satisfying $\mu\left( \frac{\kappa_a}{c},\alpha \right) \geq \mu_1$ for $c\geq 1$. \\
\end{tabular}
\end{table}
\begin{table}[!ht]
\caption{Notations for probability distributions and estimators}
\label{tab: 2}
\centering
\resizebox{\columnwidth}{!}{\begin{tabular}{ll}
    \toprule
      Symbol  &  Meaning\\
     \midrule
    $\mathrm{Pa}({\kappa, \alpha})$ & Pareto distribution with the scale $\kappa >0$ and shape $\alpha >0$. \\
      $f_{{\kappa, \alpha}}^{\mathrm{Pa}}(x)$ & density function of $\mathrm{Pa}({\kappa, \alpha})$.\\
      $\mathrm{Erlang}(s,\beta)$ & Erlang distribution with the shape $s >0$ and rate $\beta>0$. \\
      $f_{s,\beta}^{\mathrm{Er}}(x)$ &  density function of $\mathrm{Erlang}(s,\beta)$. \\
      $F_{s,\beta}^{\mathrm{Er}}(x)$ &  CDF of $\mathrm{Erlang}(s,\beta)$ evaluated at $x>0$. \\
        $\mathrm{IG}(s, \beta)$ & Inverse Gamma distribution with shape $s>0$ and scale $\beta>0$. \\
        $F_n(x)$ & CDF of the chi-squared distribution with $n$ degree of freedom.\\
      $\Gamma(s)$ & Gamma function. \\
      $\gamma(s,x)$ & the lower incomplete gamma function.\\
      $\Gamma(s,x)$ & the upper incomplete gamma function.\\
      \midrule
      $\hat{\kappa}_a(n),\,\hat{\alpha}_a(n)$ & MLEs of the scale and shape parameter of arm $a$ after $n$ observations, defined in (\ref{eq: MLEdist}). \\
      $\tilde{\kappa}_a(t),\,\tilde{\alpha}_a(t)$ & sampled parameters at round $t$ from posterior  distribution in (\ref{eq: cdfkappa}) and (\ref{eq: pdfalpha}).\\
      $\bar{\alpha}_a(n)=\max(\hat{\alpha}_a(n), n)$ & truncated estimator of the shape parameter. \\
      $\alpha_{a,n}$ & a temporary notation that can be replaced by both $\hat{\alpha}_a(n)$ ($\mathrm{STS}$) and $\bar{\alpha}_a(n)$ ($\mathrm{STS}\text{-}\mathrm{T}$). \\
      $\hat{\mu}_a(n) = \mu(\hat{\kappa}_a(n),\hat{\alpha}_a(n))$ & computed mean rewards by the MLEs after $n$ observation.\\
      $\tilde{\mu}_a(t) = \mu(\tilde{\kappa}_a(t),\tilde{\alpha}_a(t))$ & computed mean rewards by sampled parameters $\tilde{\kappa}_a(t)$ and $\tilde{\alpha}_a(t)$ at round $t$.\\
      $\theta_a=(\kappa_a, \alpha_a)$ & tuple of true parameters of arm  $a\in[K]$. \\
      $\hat{\theta}_{a,n} = (\hat{\kappa}_a(n), \hat{\alpha}_a(n))$ & tuple of MLEs of arm $a$ after $n$ observations.\\
      $\bar{\theta}_{a,n} = (\hat{\kappa}_a(n), \bar{\alpha}_a(n))$ & tuple of estimators with a truncation procedure of arm $a$ after $n$ observations. \\
      $\theta_{a,n} = (\hat{\kappa}_a(n), \alpha_{a,n})$ & a temporary notation that can be replaced by both $\hat{\theta}_{a,n}$ ($\mathrm{STS}$) and $\bar{\theta}_{a,n}$ ($\mathrm{STS}\text{-}\mathrm{T}$).\\
\end{tabular}}
\end{table}

\begin{table}[!ht]
\caption{Notations for the regret analysis}
\label{tab: 3}
\centering
\resizebox{\columnwidth}{!}{\begin{tabular}{ll}
    \toprule
      Symbol  &  Meaning\\
     \midrule
      $D_{a,k}(\epsilon)$ & a function contributes to the main term of regret analysis defined in (\ref{eq: defDa}). \\
        $\mathcal{K}_{a,n}(\epsilon)$ & an event where MLE of $\kappa$ is close to its true value at round $t$ after $n$ observations.\\
        $\mathcal{A}_{a,n}(\epsilon)$& an event where MLE of $\alpha$ is close to its true value at round $t$ after $n$ observations.\\
        $\mathcal{E}_{a,n}(\epsilon)$& intersection of $\mathcal{K}_{a,n}(\epsilon)$ and $\mathcal{A}_{a,n}(\epsilon)$. \\
        $\mathcal{M}_\epsilon(t)$ & an event where sampled mean of the optimal arm is close to its true mean reward at round $t$. \\
        $p_n(x | \theta_{1,n})$ & probability of $\{\tilde{\mu}_1(t) \leq \mu_1 - x\}$ after $n$ observation of arm $1$ given $\theta_{1,n}$.\\ 
       
        $G_k(x;n)$ & another expression of the CDF of the Erlang distribution in (\ref{eq: Gkdef}). \\
\end{tabular}}
\end{table}

\begin{table}[!ht]
\caption{Notations for (deterministic) constants}
\label{tab: 4}
\centering
\resizebox{\columnwidth}{!}{\begin{tabular}{ll}
    \toprule
      Symbol  &  Meaning\\
     \midrule
        $\varepsilon_a$ & problem-dependent constants to satisfy $\hat{\mu}_a(n) \in [\mu_a - \delta_a, \mu_a + \delta_a]$ on $\mathcal{E}_{a,n}(\epsilon)$ for any $\epsilon \leq \varepsilon_a$. \\
        $\epsilon_{a,l}(\epsilon)$, $\epsilon_{a,l}(\epsilon)$ & constants to control a deviation of $\hat{\alpha}_a(\epsilon)$ under the event $\mathcal{A}_{a,n}(\epsilon)$. \\
        $\rho_{\theta_1}(\epsilon), \bar{\rho}=\rho_{\theta_1}(\epsilon/2)$ & a difference from its true shape parameter $\alpha_1$ to satisfy $\mu(\kappa_a, \alpha+\rho_{\mu_1}(\epsilon)) \geq \mu_1 - \frac{\epsilon}{2}$. \\ 
        $C_1(\mu_1, \epsilon, n) = C_{1,n}$ & a constant smaller than $1$ in (\ref{eq: Gkdef}).\\
        $C_2(\mu_1, \epsilon, k)$ & an uniform bound of $p_n(\epsilon|\cdot)$ under $\mathcal{K}_{1,n}^c(\epsilon) \cap \mathcal{A}_{1,n}(\epsilon/2)$. \\
        $c_{\mu_1}(\epsilon)$ & a small constant with $\mathcal{O}(\epsilon^{-2})$. \\
\end{tabular}}
\end{table}

\newpage

\section{Proof of Lemma~\ref{lem: KLinf}}\label{sec: L1proof}
\lemKLinf*
\begin{proof}
Recall the definition
\begin{equation*}
    \mathrm{KL}_{\mathrm{inf}}(a) = \mathrm{KL}_{\mathrm{inf}}(\mathrm{Pa}(\theta_a), \mathrm{Pa}(\theta)) := \inf_{\theta\in \Theta_a} \log \frac{\alpha_a}{\alpha} +  \alpha \log \frac{\kappa_a}{\kappa} + \frac{\alpha}{\alpha_a} -1,
\end{equation*}
where $\theta = (\kappa, \alpha)$ and $\Theta_a$ defined in (\ref{eq: thetaset}).

Here, we consider the partition of $\Theta_a$, 
\begin{align*}
    \Theta_a^{(1)} &= \left\{ (\kappa, \alpha) \in (0, \kappa_a] \times (0,1] : \mu({\kappa, \alpha}) > \mu_1 \right\} = (0, \kappa_a] \times (0,1] \\
    \Theta_a^{(2)} &= \left\{ (\kappa, \alpha) \in (0, \kappa_a] \times (1,\infty) : \mu({\kappa, \alpha})=\frac{\kappa\alpha}{\alpha-1} > \mu_1 \right\}, \numberthis{\label{eq: thetaset2}}
\end{align*}
where $\Theta_a^{(1)} \cup \Theta_a^{(2)} = \Theta_a$.
Therefore, it holds that
\begin{equation*}
    \mathrm{KL}_{\mathrm{inf}}(a) = \min\left(\inf_{\theta\in \Theta_a^{(1)}} \log \frac{\alpha_a}{\alpha} +  \alpha \log \frac{\kappa_a}{\kappa} + \frac{\alpha}{\alpha_a} -1, \inf_{\theta\in \Theta_a^{(2)}} \log \frac{\alpha_a}{\alpha} +  \alpha \log \frac{\kappa_a}{\kappa} + \frac{\alpha}{\alpha_a} -1 \right).
\end{equation*}
For $({\kappa, \alpha}) \in \Theta_a^{(1)}$, $\mu({\kappa, \alpha}) = \infty$ holds regardless of $\kappa$.
Therefore, we obtain
\begin{align*}
    \inf_{\theta \in \Theta_a^{(1)}} \log \frac{\alpha_a}{\alpha} +  \alpha \log \frac{\kappa_a}{\kappa} + \frac{\alpha}{\alpha_a} -1 &= \inf_{\alpha \in (0,1]} \log \frac{\alpha_a}{\alpha} + \frac{\alpha}{\alpha_a} -1 \\
    & = \log \alpha_a + \frac{1}{\alpha_a } -1,
\end{align*}
where the last equality holds since $\log x + \frac{1}{x} - 1$ is an increasing function for $x \geq 1$.

Let $\frac{\kappa_a}{\kappa} = c \geq 1$ to make KL divergence from $\mathrm{Pa}(\theta_a)$ to $\mathrm{Pa}({\kappa, \alpha})$ be well-defined.
From its definition of $\Theta_a^{(2)}$ in (\ref{eq: thetaset2}), any $\theta = ({\kappa, \alpha}) \in \Theta_a^{(2)}$ satisfies $\frac{\kappa\alpha}{\alpha-1} \geq \mu_1$, i.e., 
\begin{equation*}
    \frac{\kappa_a \alpha}{c(\alpha-1)} \geq \mu_1 \Leftrightarrow \alpha \leq \frac{c \mu_1}{c\mu_1 - \kappa_a} =:h_a(c,\boldsymbol{\mu}) = h_a(c).
\end{equation*}
Note that it holds that
\begin{equation*}
    h_a(1) = \frac{\mu_1}{\mu_1-\kappa_a} \leq  \frac{\mu_a}{\mu_a-\kappa_a} = \alpha_a
\end{equation*}
since $\frac{x}{x-y}$ is decreasing with respect to $x \geq y$.
Then, we can rewrite the infimum of KL divergence as
\begin{equation*}
    \mathrm{KL}_{\mathrm{inf}}(a) = \min \left(\log \alpha_a + \frac{1}{\alpha_a} -1, \inf_{c \geq 1} \inf_{\alpha \leq  h_a(c)}  g_a(\alpha, c) \right),
\end{equation*}
where $ g_a(\alpha, c) := \log \frac{\alpha_a}{\alpha} +  \alpha \log c + \frac{\alpha}{\alpha_a} -1$ satisfying
\begin{equation}\label{eq: derivativef}
    \frac{\partial  g_a(\alpha, c)}{\partial \alpha} = \frac{1}{\alpha_a} + \log c - \frac{1}{\alpha}.
\end{equation}
Then, the inner infimum can be obtained when $\alpha = \frac{\alpha_a}{1+\alpha_a \log c}$ holds if $\frac{\alpha_a}{1+\alpha_a \log c} < h_a(c)$, where $g_a\left(\frac{\alpha_a}{1+\alpha_a \log c}, c\right) = \log(1+\alpha_a \log c)$.

Let $c_{a}^* \geq 1$ be a deterministic constant such that 
\begin{equation}\label{eq: castar}
  h_a(c_{a}^*)  = \frac{c_{a}^* \mu_1}{c_{a}^* \mu_1 - \kappa_a} = \frac{\alpha_a}{1+\alpha_a \log c_{a}^*} \Leftrightarrow (\mu_1\alpha_a ) c_{a}^*\log c_{a}^* + (\mu_1 - \alpha_a \mu_1)c_{a}^* = -\alpha_a \kappa_a
\end{equation}
so that $h_a(c) \geq \frac{\alpha_a}{1+\alpha_a \log c}$ holds for any $c \geq c_{a}^*$.
Since the solution of $ax\log(x) + bx = -c$ is given as $\exp\left(W\left(- \frac{ce^{b/a}}{a}\right) - \frac{b}{a}\right)$ for principal branch of Lambert W function $W(\cdot)$, one can obtain $c_{a}^*$ by solving the equality in (\ref{eq: castar}), which is
\begin{equation}\label{eq: ca*}
    c_{a}^* = \exp\left(W\left(-\frac{\kappa_a}{\mu_1} e^{\frac{1}{\alpha_a}-1}\right) + 1 - \frac{1}{\alpha_a}\right). 
\end{equation}
Notice that $\frac{\kappa_a}{\mu_1} e^{\frac{1}{\alpha_a}-1} \leq \frac{\kappa_a}{\mu_a}e^{\frac{1}{\alpha_a}-1}  \leq \left( 1-\frac{1}{\alpha_a} \right)e^{-\left( 1- \frac{1}{\alpha_a}\right)} \leq e^{-1}$ holds so that $c_{a}^*$ is a real value.
Here, we consider the principal branch to ensure $c_{a}^* \geq 1$ since the solution on other branches, $W_{-1}(\cdot)$, is less than $1$, which is out of our interest.

Let $A_a = 1- \frac{1}{\alpha_a}$, which is positive as $\alpha_a > 1$ and $B_a = \frac{\kappa_a}{\mu_1} \leq \frac{\kappa_a}{\mu_a} = \frac{\alpha_a -1}{\alpha_a} = A_a$.
Then, we can rewrite $c_{a}^*$ as
\begin{equation*}
    c_{a}^* = e^{A_a} e^{W(-B_ae^{-A_a})} = e^{A_a} e^{-A_a} \frac{-B_a}{W(-B_a e^{-A_a})}. \hspace{3em} \because e^{W(x)} = \frac{x}{W(x)} 
\end{equation*}
Since the principal branch of Lambert W function, $W(x)$, is increasing for $x \geq - \frac{1}{e}$, we have
\begin{equation*}
  0> W(-B_ae^{-A_a}) \geq W(-B_ae^{-B_a}) = -B_a,
\end{equation*}
which implies that $c_{a}^* \geq 1$.
Therefore, the infimum of $g_a$ can be written as
\begin{align*}
   \inf_{c \geq 1} \inf_{\alpha \leq  h_a(c)}  g_a(\alpha, c) &= \min \left( \inf_{c \in [1, c_{a}^*]} g_a(h_a(c),c), \inf_{c \geq c_{a}^*} \log(1+\alpha_a \log c)  \right) \\
    &= \min \left( \inf_{c \in [1, c_{a}^*]} g_a(h_a(c),c), \log(1+\alpha_a \log c_{a}^*)  \right),
\end{align*}
where we follow the convention that the infimum over the empty set is defined as infinity.

By substituting $c_a^*$ in (\ref{eq: ca*}), we obtain
\begin{equation*}
    \log(1+\alpha_a \log c_{a}^*)  = \log \left(\alpha_a + W\left(-\frac{\kappa_a}{\mu_1} e^{\frac{1}{\alpha_a}-1}\right) \right).
\end{equation*}
Let us consider the following inequalities:
\begin{align*}
  \log \left(\alpha_a + W\left(-\frac{\kappa_a}{\mu_1} e^{\frac{1}{\alpha_a}-1}\right) \right) &\geq \log \left(\alpha_a + W\left(-\frac{\kappa_a}{\mu_a} e^{\frac{1}{\alpha_a}-1}\right) \right) \\
  &= \log \left(\alpha_a + W\left(\frac{1-\alpha_a}{\alpha_a} e^{\frac{1}{\alpha_a}-1}\right) \right) \\
  &= \log \left( \alpha_a + \frac{1}{\alpha_a} -1 \right), \numberthis{\label{eq: KLinfcstar}}
\end{align*}
where the first inequality holds since the principal branch of Lambert W function $W(x)$ is increasing and negative with respect to $x \in \left[ -1/e, 0 \right)$.

It remains to find the closed form of $\inf_{c \in [1, c_{a}^*]} g_a(h_a(c),c)$.
From the definition of $h_a(c) = \frac{c\mu_1}{c\mu_1 -\kappa_a}$, we have $h_a'(c) = -\frac{\mu_1 \kappa_a}{(c\mu_1 - \kappa_a)^2}$ and
\begin{align*}
    \frac{\partial  g_a(h_a(c), c)}{\partial c} &= \frac{\partial}{\partial c} \left( \log \frac{\alpha_a}{h_a(c)} + h_a(c) \log c + \frac{h_a(c)}{\alpha_a} - 1 \right) \hspace{2em} \because g_a(x, c) = \log \frac{\alpha_a}{x} + x \log c + \frac{x}{\alpha_a} - 1 \\
    &= - \frac{h_a'(c)}{h_a(c)} + h_a'(c) \log c + \frac{h_a(c)}{c} + \frac{1}{\alpha_a}h_a'(c) \\
    &= \frac{\kappa_a}{c(c\mu_1 - \kappa_a)} - \frac{\mu_1 \kappa_a}{(c\mu_1 -\kappa_a)^2} \log c + \frac{\mu_1}{c\mu_1 -\kappa_a} - \frac{\kappa_a \mu_1}{\alpha_a (c\mu_1 -\kappa_a)^2} \\
    &=  \frac{\kappa_a}{c(c\mu_1 - \kappa_a)} - \frac{\mu_1 \kappa_a}{(c\mu_1 -\kappa_a)^2} \log c + \mu_1 \frac{c\mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a}}{(c\mu_1 -\kappa_a)^2}. \numberthis{\label{eq: derivativeKLC}}
\end{align*}
Since the first term in (\ref{eq: derivativeKLC}) is positive for $c\geq 1$ and $\mu_1 \geq \mu_a > \kappa_a$, let us consider the last two terms for $c \in [1, c_{a}^*]$,
\begin{align*}
    - \frac{\mu_1 \kappa_a}{(c\mu_1 -\kappa_a)^2} \log c + \mu_1 \frac{c\mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a}}{(c\mu_1 -\kappa_a)^2} &= \frac{\mu_1}{(c\mu_1-\kappa_a)^2} \left( c\mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a} - \kappa_a \log c \right) \\
    &= \frac{\mu_1}{(c\mu_1-\kappa_a)^2} \left( \mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a} + (c-1)\mu_1 -\kappa_a \log c \right) \\
    &= \frac{\mu_1}{(c\mu_1-\kappa_a)^2} \left( \mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a} + \mu_1\left ( c -\frac{\kappa_a}{\mu_1} \log c -1 \right) \right).
\end{align*}
Here, 
\begin{equation*}
     \mu_1 - \kappa_a - \frac{\kappa_a}{\alpha_a} \geq \mu_a  - \kappa_a - \frac{\kappa_a}{\alpha_a} = \frac{\kappa_a \alpha_a}{\alpha_a-1} - \kappa_a - \frac{\kappa_a}{\alpha_a} = \frac{\kappa_a}{\alpha_a(\alpha_a-1)} > 0,
\end{equation*}
and $c -\frac{\kappa_a}{\mu_1} \log c -1$ is increasing with respect to $c$ so that $c -\frac{\kappa_a}{\mu_1} \log c -1 \geq 0$ for $c \geq 1$.
Therefore, $\frac{\partial }{\partial c}g_a(h_a(c), c)$ is positive for $c \geq 1$, i.e., $g_a(h_a(c), c)$ is an increasing function with respect to $c \geq 1$.

Thus, we have for $c \in [1, c_{a}^*]$,
\begin{equation*}
    \inf_{c \in [1, c_{a}^*]} g_a(h_a(c),c) = g_a\left( h_a(1), 1\right) = g_a\left( \frac{\mu_1}{\mu_1 - \kappa_a}, 1 \right) = \log\left(\alpha_a\frac{\mu_1-\kappa_a}{\mu_1}\right) + \frac{1}{\alpha_a}\frac{\mu_1}{\mu_1-\kappa_a} -1.
\end{equation*}
Denote $X_a = \alpha_a\frac{\mu_1-\kappa_a}{\mu_1} \in [1, \alpha_a)$ where $X_a=1$ happens only when $\mu_a = \mu_1$.
Then, we have for $\alpha_a >1$
\begin{equation*}
    \log (X_a) + \frac{1}{X_a} -1 \leq \log \alpha_a + \frac{1}{\alpha_a} -1 \leq \log \left( \alpha_a + \frac{1}{\alpha_a} -1 \right) \leq \log(1+\alpha_a \log c_{a}^*),
\end{equation*}
where the last inequality comes from the result in (\ref{eq: KLinfcstar}).
Therefore, we have
\begin{align*}
    \mathrm{KL}_{\mathrm{inf}}(a) &= \min \left(\log \alpha_a + \frac{1}{\alpha_a} - 1, \inf_{c \in [1, c_{a}^*]} g_a(h_a(c),c) , \log(1+\alpha_a \log c_{a}^*) \right) \\
    &= \log\left(\alpha_a\frac{\mu_1-\kappa_a}{\mu_1}\right) + \frac{1}{\alpha_a}\frac{\mu_1}{\mu_1-\kappa_a} -1,
\end{align*}
which concludes the proof.
\end{proof}


\section{Proofs of lemmas for Theorems~\ref{thm: RegOpt} and~\ref{thm: RegOptTruncation}}\label{sec: Opt}
In this section, we provide the proof of lemmas for the main results.

To avoid redundancy, we use a temporary notation $\alpha_{a,n}$ when the same result holds for both $\hat{\alpha}_a(n)$ and $\bar{\alpha}_a(n)$.
When $\alpha_{a,n}$ notation is used, one can replace it with either $\hat{\alpha}_a(n)$ or $\bar{\alpha}_a(n)$ depending on which policy we are considering.
For example, it holds that
\begin{align*}
    \alpha_{a,n} \leq 1 \Leftrightarrow  \begin{cases}
    \hat{\alpha}_a(n) \leq 1  &\text{under $\mathrm{STS}$ policy}, \\
    \bar{\alpha}_a(n) \leq 1  &\text{under $\mathrm{STS}\text{-}\mathrm{T}$ policy}.
    \end{cases}
\end{align*}
Similarly, we use the notation $\theta_{a,n} := (\hat{\kappa}_a(n), \alpha_{a,n})$ when it can be replaced by both $\hat{\theta}_{a,n} = (\hat{\kappa}_a(n), \hat{\alpha}_a(n))$ and $\bar{\theta}_{a,n} = (\hat{\kappa}_a(n), \bar{\alpha}_a(n))$ for any arm $a \in[K]$ and $n \in \mathbb{N}$.
Based on $\theta_{a,n}$ notation, we provide an inequality on the posterior probability that the sampled mean is smaller than a given value with proofs in Appendix~\ref{sec: tmusmall}.
\begin{restatable}{lemma}{lemtmu}~\label{lem: tmusmall}
For any arm $a \in [K]$ and fixed $t \in \mathbb{N}$, let $N_a(t) =n$.
For any positive $\xi \leq \frac{y}{y - \kappa_a}$ and $k \in \mathbb{Z}$, it holds that
\begin{align*}
  \mathbbm{1}[\hat{\kappa}_a(n) \leq y]\mathbb{P}[\tilde{\mu}_a(t) \leq y| \theta_{a,n}] \leq \int_{\xi}^\infty f_{n-k, \frac{n}{\alpha_{a,n}}}^{\mathrm{Er}}(x) \mathrm{d} x + \bigg( \frac{y}{\mu((\kappa_a, \xi))} \bigg)^{n} \int_{1}^\xi f_{n-k, \frac{n}{\alpha_{a,n}}}^{\mathrm{Er}}(x) \mathrm{d} x,
\end{align*}
where $f_{s, \beta}^{\mathrm{Er}}(\cdot)$ denotes the probability density function of the Erlang distribution with shape $s\in \mathbb{N}$ and rate $\beta>0$.
\end{restatable}

Based on $\theta_{1,n}$ notation, we denote the probability of sample from the posterior distribution after $n$ times playing is smaller than $\mu_1 - x$ by
\begin{equation}\label{eq: pndef}
    p_n(x | \theta_{1,n}) := \mathbb{P}[\tilde{\mu}_1 \leq \mu_1 - x | \hat{\kappa}_1(n), \alpha_{1,n}].
\end{equation}
Let $K(\epsilon) = (\kappa_1 + \epsilon, \mu_1 - \epsilon)$ be an open interval on $\mathbb{R}$.
The Lemma~\ref{lem: pn_cases} below shows the upper bound of $p_n$ conditioned on ${\theta}_{1,n}$.
\begin{restatable}{lemma}{lempn}\label{lem: pn_cases}
Given $\epsilon >0$, define a positive problem-dependent constant $\rho = \rho_{\theta_1}(\epsilon):= \frac{\kappa_1\epsilon}{2(\mu_1-\epsilon/2 - \kappa_1)(\mu_1-\kappa_1)}$.
If $n \geq \bar{n}=\max(2, k+1)$, then for $k \in \mathbb{Z}_{\geq 0}$
\begin{align*}
  p_n(\epsilon|\theta_{1,n})
  \leq
    \begin{cases}
    e^{-n}, & \mathrm{if}~\hat{\kappa}_1(n) \geq \mu_1 - \epsilon, \\
   
    h(\mu_1, \epsilon,n), & \mathrm{if}~ \hat{\kappa}_1(n) \in K(\epsilon), \alpha_{1,n} \leq \alpha_1 + \rho,\\
     C_1(\mu_1,\epsilon, n)G_k(1/\alpha_{1,n};n)  + 1-G_k(1/\alpha_{1,n};n) & \mathrm{if}~ \hat{\kappa}_1(n) \in K(\epsilon), \alpha_{1,n} \geq \alpha_1 + \rho,
    \end{cases}
\end{align*}
where
\begin{align*}
     h(\mu_1, \epsilon,n) &:= e^{-n \frac{3\epsilon}{4\mu_1}} \left( 1- \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)} \right) + \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)} \\
     C_1(\mu_1,\epsilon, n) &:= \left( \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon/2} \right)^{n} \leq e^{-n \frac{\epsilon}{2\mu_1 - \epsilon}} < 1.\\
     G_k(x; n) &:= F^{\mathrm{Er}}_{n-k, nx}(\alpha_1 + \rho) \numberthis{\label{eq: Gkdef}}
\end{align*}
for $F^{\mathrm{Er}}$ defined in (\ref{eq: def_inc_gamma}).
Here, $c_{\mu_1}(\epsilon) = \zeta - \log(1+\zeta) = \mathcal{O}(\epsilon^{-2})$ and $\zeta = \frac{\epsilon}{4\mu_1 - 2\epsilon} \in (0,1)$ are deterministic constants of $\mu_1$ and $\epsilon$.
\end{restatable}
Notice that $\mu((\kappa_1, \alpha_1 + \rho)) = \mu_1 - \epsilon/2$ holds and
there exists a problem-dependent constant $C_2(\mu_1, \epsilon, k)< 1$ such that for any $n \geq \bar{n} = \max(2, k+1)$ and $\epsilon >0$
\begin{equation}\label{eq: upperbound}
     h(\mu_1, \epsilon,n)  \leq 1-C_2(\mu_1, \epsilon, k).
\end{equation}

\subsection{Proof of Lemma~\ref{lem: difficult}}\label{app: lem5}
Let us start by stating a well-known fact that is utilized in the proof.
\begin{fact}\label{eq: fact_IG}
When $X \sim \mathrm{Erlang}(n, \beta)$ with rate parameter $\beta$, then $\frac{1}{X}$ follows the inverse gamma distribution with shape $n \in \mathbb{N}$ and scale $\beta\in \mathbb{R}_{+}$, i.e., $\frac{1}{X} \sim \mathrm{IG}(n, \beta)$.
\end{fact}
\lemdifficult*
\begin{proof}
Let us consider the following decomposition that holds under both $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$:
\begin{align*}
    \sum_{t=K\bar{n} +1}^T \mathbbm{1}[j(t)\ne 1,\mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t)] \hspace{-9em} &\\
    &= \sum_{n=\bar{n}}^T \sum_{t=K\bar{n} + 1}^T \mathbbm{1}\bigg[j(t)\ne 1,\mathcal{K}_{1,N_1(t)}^c(\epsilon),\mathcal{M}_\epsilon^c(t), N_1(t) =n\bigg] \\
    &= \sum_{n=\bar{n}}^T \sum_{m=1}^T \mathbbm{1}\Bigg[m \leq \sum_{t=K\bar{n} + 1}^T \mathbbm{1}\bigg[j(t)\ne 1, \mathcal{M}_\epsilon^c(t), \mathcal{K}_{1,N_1(t)}^c(\epsilon), N_1(t) =n\bigg]\Bigg].
\end{align*}
Notice that
\begin{equation*}
    m \leq \sum_{t=K\bar{n} + 1}^T \mathbbm{1}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t), N_1(t) =n]
\end{equation*}
implies that $\tilde{\mu}_1(t) \leq \mu_1 -\epsilon$ occurred $m$ times in a row on $\{t: \mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t), N_1(t) =n \}$.
Thus, we have
\begin{align*}
    \mathbb{E}\Bigg[  \sum_{t=K\bar{n} +1}^T \mathbbm{1}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t)] \Bigg] &\leq \mathbb{E}\left[  \sum_{n=\bar{n}}^T \sum_{m=1}^T \mathbbm{1}[\mathcal{K}_{1,n}^c(\epsilon)] p_n(\epsilon|{\theta}_{1,n})^m \right] \\
    &\leq \sum_{n=\bar{n}}^T \mathbb{E}\left[ \mathbbm{1}\left[\mathcal{K}_{1,n}^c(\epsilon)\right] \frac{p_n(\epsilon|{\theta}_{1,n})}{1-p_n(\epsilon|{\theta}_{1,n})} \right] \numberthis{\label{eq: pn_decom}}
\end{align*}
for $p_n(\cdot|\cdot)$ defined in (\ref{eq: pndef}).
From now on, we fix $n \geq \bar{n}$ and drop the argument $n$ of $\hat{\kappa}_1(n)$, $\hat{\alpha}_1(n)$ and $\bar{\alpha}_1(n)$ for simplicity.

\paragraph{Under $\mathrm{STS}$ with $k \in \mathbb{Z}_{\geq 2}$:}
By applying Lemma~\ref{lem: pn_cases} and (\ref{eq: upperbound}) under $\mathrm{STS}$ with $k \in \mathbb{Z}_{\geq 0}$, we can decompose the expectation in (\ref{eq: pn_decom}) as
\begin{align*}
    \mathbb{E}\left[ \mathbbm{1}\left[\mathcal{K}_{1,n}^c(\epsilon)\right] \frac{p_n(\epsilon|\hat{\theta}_{1,n})}{1-p_n(\epsilon|\hat{\theta}_{1,n})} \right] \leq  
    \mathbb{P}[\hat{\kappa}_1 \geq \mu_1 - \epsilon] \frac{e^{-n}}{1-e^{-n}} &+ \mathbb{P}[\hat{\kappa}_1 \in K(\epsilon), \hat{\alpha}_1 < \alpha_1 + \rho] \frac{ h(\mu_1, \epsilon,n) }{C_2(\mu_1, \epsilon, k)}   \\
    &\hspace{1em}+ \underbrace{\mathbb{E}_{\hat{\theta}_{1,n}}\left[\frac{\mathbbm{1}[\hat{\kappa}_1\in K(\epsilon), \hat{\alpha}_1 > \alpha_1 + \rho]}{G_k(1/\hat{\alpha}_1 ;n)(1-C_{1,n})}\right]}_{(\divideontimes)}, \numberthis{\label{eq: pn_sum_STS}}
\end{align*}
where we denoted $C_{1,n} = C_1(\mu_1, \epsilon, n)$.
For simplicity, let us define $z := \frac{1}{\hat{\alpha}_1}$ where $z \sim \mathrm{Erlang}(n-1, n\alpha_1)$ holds from Fact~(\ref{eq: fact_IG}) since $\hat{\alpha}_1 \sim \mathrm{IG}(n-1, n\alpha_1)$ in (\ref{eq: MLEdist}).
From the independence of $\hat{\kappa}$ and $\hat{\alpha}$ and distributions of $z$ and $\hat{\alpha}$ in (\ref{eq: pdf_erlang}) and (\ref{eq: MLEdist}), respectively, we have
\begin{align*}
    (\divideontimes) &= \int_0^{\frac{1}{\alpha_1 + \rho}} z^{n-2} e^{-n\alpha_1 z}\frac{(n\alpha_1)^{n-1}}{\Gamma(n-1) } \int_{\hat{\kappa}_1 \in K(\epsilon)} \frac{f^{\mathrm{Pa}}_{\kappa_1, n\alpha_1}(\hat{\kappa}_1)}{G_k(z;n)(1-C_{1,n})} \mathrm{d} \hat{\kappa}_1 \mathrm{d} z \\
    &= \mathbb{P}[\hat{\kappa}_1 \in K(\epsilon)] \int_0^{\frac{1}{\alpha_1 + \rho}} \frac{z^{n-2} e^{-n\alpha_1 z} }{G_k(z;n)(1-C_{1,n})} \frac{(n\alpha_1)^{n-1}}{\Gamma(n-1)}\mathrm{d} z.
\end{align*}
By substituting the CDF in (\ref{eq: def_inc_gamma}), we obtain
\begin{align*}
    G_k(z;n) &= F^{\mathrm{Er}}_{n-k, nz}(\alpha_1 + \rho) \\
    &=\frac{1}{\Gamma(n-k)}\int_0^{n(\alpha_1 + \rho)z} e^{-t}t^{n-k-1} \mathrm{d} t \\
    &\geq \frac{e^{-n(\alpha_1 + \rho)z}}{\Gamma(n-k)}  \int_0^{n(\alpha_1 + \rho)z} t^{n-k-1} \mathrm{d} t 
  \\ &= \frac{e^{-n(\alpha_1 + \rho)z}}{\Gamma(n-k+1)} (n(\alpha_1 + \rho)z)^{n-k}. \numberthis{\label{eq: Gkbnd}}
\end{align*}
Therefore,
\begin{align*}
    \frac{(\divideontimes)}{\mathbb{P}[\hat{\kappa} \in K(\epsilon)]} &\leq 
    \int_0^{\frac{1}{\alpha_1 + \rho}} \frac{\Gamma(n-k+1)}{(n(\alpha_1 + \rho)z)^{n-k}(1-C_{1,n})} e^{n(\alpha_1 + \rho)z} \frac{(n\alpha_1)^{n-1}}{\Gamma(n-1)} z^{n-2} e^{-n\alpha_1 z} \mathrm{d} z \\
    &=  \frac{\Gamma(n-k+1)}{\Gamma(n-1)(1-C_{1,n})} (\alpha_1 + \rho)^{k-1} \left( \frac{\alpha_1}{\alpha_1 + \rho} \right)^{n-1} n^{k-1} \int_0^{\frac{1}{\alpha_1 + \rho}} z^{k-2} e^{n\rho z} \mathrm{d} z \\
    &\leq \frac{\Gamma(n-k+1)}{\Gamma(n-1)(1-C_{1,n})} (\alpha_1 + \rho)^{k-1} e^{-\frac{\rho}{\alpha_1 + \rho}(n-1)}  \frac{n^{k-1}}{(n\rho)^{k-2}} \int_0^{\frac{1}{\alpha_1 + \rho}} (n\rho z)^{k-2} e^{n\rho z} \mathrm{d} z. \numberthis{\label{eq: A1bnd}}
\end{align*}
By letting $n\rho z = y$, we can bound the integral in (\ref{eq: A1bnd}) as
\begin{align*}
    \frac{n^{k-1}}{(n\rho)^{k-2}} \int_0^{\frac{1}{\alpha_1 + \rho}} (n\rho z)^{k-2} e^{n\rho z} \mathrm{d} z &=  \rho^{-(k-1)} \int_0^{\frac{n\rho}{\alpha_1 + \rho}} y^{k-2} e^{y} \mathrm{d} y \\
    &\leq  \rho^{-(k-1)} e^{n \frac{\rho}{\alpha_1 + \rho}} \int_0^{\frac{n\rho}{\alpha_1 + \rho}} y^{k-2}\mathrm{d} y \numberthis{\label{eq: integral}} \\
    &=  \frac{e^{n \frac{\rho}{\alpha_1 + \rho}}}{k-1} \left( \frac{n}{\alpha_1 + \rho} \right)^{k-1}, \quad \text{ if } k \in \mathbb{Z}_{\geq 2}\numberthis{\label{eq: intgrslt}}
\end{align*}
where (\ref{eq: intgrslt}) holds only for $k \in \mathbb{Z}_{\geq 2}$ since the integral in (\ref{eq: integral}) diverges for $k \in \mathbb{Z}_{\leq 1}$.

By applying (\ref{eq: intgrslt}) to (\ref{eq: A1bnd}), we obtain for $k \in \mathbb{Z}_{\geq 2}$ 
\begin{align*}
    (\divideontimes) &\leq 
    \mathbb{P}[\hat{\kappa} \in K(\epsilon)]  \frac{e^{\frac{\rho}{\alpha_1 + \rho}}}{1-C_{1,n}} \frac{n^{k-1}}{k-1}\frac{\Gamma(n-k+1)}{\Gamma(n-1)} \hspace{3em}\\
    &\leq \frac{e^{1-\frac{\epsilon \alpha_1}{\kappa + \epsilon}n}}{1-C_{1,n}} \frac{\Gamma(n-k+1)}{\Gamma(n-1)} \frac{n^{k-1}}{k-1} = \mathcal{O}(ne^{-n\epsilon}),\hspace{-1em}\numberthis{\label{eq: a1_1}}
\end{align*}
where (\ref{eq: a1_1}) can be obtained by Lemma~\ref{lem: eKbound} and $\frac{\rho}{\alpha_1 + \rho} < 1$.
By combining (\ref{eq: a1_1}) with (\ref{eq: pn_sum_STS}) and (\ref{eq: pn_decom}), we obtain for $k\in \mathbb{Z}_{\geq 2}$
\begin{align*} 
    \mathbb{E}\left[  \sum_{t=K\bar{n} +1}^T \mathbbm{1}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t)] \right] 
    &\leq \sum_{n=\bar{n}}^T \bigg(\frac{e^{-n}}{1-e^{-n}}+ \frac{e^{-n \frac{3\epsilon}{4\mu_1}} + \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)}}{C_2(\mu_1, \epsilon, k)} 
    + (\divideontimes) \bigg)\\
    & \leq \sum_{n=\bar{n}}^T  \mathcal{O}(e^{-n}) + \mathcal{O}(e^{-n\epsilon}) + \mathcal{O}(e^{-n\epsilon^2}) + \mathcal{O}(ne^{- n\epsilon}) \\
  & = \mathcal{O}(1) + \mathcal{O}(\epsilon^{-1}) + \mathcal{O}(\epsilon^{-2}) + \mathcal{O}(\epsilon^{-2}),
\end{align*}
which concludes the proof under $\mathrm{STS}$ with $k \in \mathbb{Z}_{\geq 2}$.

\paragraph{Under $\mathrm{STS}\text{-}\mathrm{T}$ with $k \in \mathbb{Z}_{\geq 0}$:}
Under $\mathrm{STS}\text{-}\mathrm{T}$, we have the following inequality instead of (\ref{eq: pn_sum_STS}):
\begin{align*}
    \mathbb{E}\left[ \mathbbm{1}\left[\mathcal{K}_{n}^c(\epsilon)\right] \frac{p_n(\epsilon|\bar{\theta}_{1,n})}{1-p_n(\epsilon|\bar{\theta}_{1,n})} \right]\leq  
    \mathbb{P}[\hat{\kappa}_1 \geq \mu_1 - \epsilon] \frac{e^{-n}}{1-e^{-n}} &+ \mathbb{P}[\hat{\kappa}_1 \in K(\epsilon), \bar{\alpha}_1 < \alpha_1 + \rho] \frac{ h(\mu_1, \epsilon,n) }{C_2(\mu_1, \epsilon, k)}   \\
    &\hspace{1em} + \underbrace{\mathbb{E}_{\bar{\theta}_{1,n}} \left[\frac{\mathbbm{1}[\hat{\kappa}_1 \in K(\epsilon), \bar{\alpha}_1 \in (\alpha_1 + \rho, n]]}{G_k(1/\bar{\alpha}_1 ;n)(1-C_{1,n})}\right]}_{(\star)}. \numberthis{\label{eq: pn_sum_STSR}}
\end{align*}
From $\mathbbm{1}[\bar{\alpha}_1(n) < n]= \mathbbm{1}[\bar{\alpha}_1(n) = \hat{\alpha}_1(n)]$, it holds that
\begin{align*}
    (\star) &= \mathbb{E}_{\hat{\theta}_{1,n}}\left[\frac{\mathbbm{1}[\hat{\kappa}_1 \in K(\epsilon), \hat{\alpha}_1 \in (\alpha_1 + \rho, n)]}{G_k(1/\hat{\alpha}_1 ;n)(1-C_{1,n})} \right] + \mathbb{E}_{\bar{\theta}_{1,n}}\left[\frac{\mathbbm{1}[\hat{\kappa}_1 \in K(\epsilon), \bar{\alpha}_1 =n ]}{G_k(1/\bar{\alpha}_1 ;n)(1-C_{1,n})} \right].
\end{align*}
Since $\mathbbm{1}[\bar{\alpha}_1(n) = n]=\mathbbm{1}[\hat{\alpha}_1(n) \geq n]$ holds and $\hat{\kappa}$ and $\hat{\alpha}$ are independent, we have for $z= \frac{1}{\hat{\alpha}_1} \sim \mathrm{Erlang}(n-1, n\alpha_1)$
\begin{align*}
    \frac{(\star)}{\mathbb{P}[\hat{\kappa}_1 \in K(\epsilon)]} &\leq \underbrace{\int_{\frac{1}{n}}^{\frac{1}{\alpha_1 + \rho}} \frac{z^{n-2} e^{-n\alpha_1 z} }{G_k(z;n)(1-C_{1,n})} \frac{(n\alpha_1)^{n-1}}{\Gamma(n-1)}\mathrm{d} z}_{(\dagger)} + \underbrace{\frac{1}{G_k(1/n;n)(1-C_{1,n})} \mathbb{P}\left[ \frac{1}{\hat{\alpha}_1} \leq \frac{1}{n}\right]}_{(\diamond)}, \numberthis{\label{eq: star}}
\end{align*}
where the same techniques on $(\divideontimes)$ can be applied to derive an upper bound of $(\dagger)$.
By following the same steps as (\ref{eq: A1bnd}) and (\ref{eq: integral}), we obtain
\begin{equation*}
    \int_{\rho}^{\frac{n\rho}{\alpha + \rho}} y^{k-2}\mathrm{d} y \leq \begin{cases} 
    \left( \frac{n\rho}{\alpha+\rho} \right)^{k-1}, & \mathrm{if}~k \in \mathbb{Z}_{\geq 2}, \\
    \log\left( \frac{n}{\alpha + \rho} \right), & \mathrm{if}~k = 1, \\
    \rho^{k-1}/(1-k), &\mathrm{if}~ k \in \mathbb{Z}_{k \leq 0},
    \end{cases}
\end{equation*}
as a counterpart of the integral in (\ref{eq: integral}).
By following the same steps as (\ref{eq: intgrslt}) and (\ref{eq: a1_1}), we have
\begin{equation}\label{eq: integral_restricted}
    (\dagger) \leq \begin{cases} 
    \frac{\Gamma(n-k+1)}{\Gamma(n-1)} \frac{e n^{k-1}}{k-1}, &\mathrm{if}~k \in \mathbb{Z}_{\geq 2}, \\
    (n-1)\log\left( \frac{n}{\alpha + \rho} \right) , &\mathrm{if}~k = 1, \\
    \frac{\Gamma(n-k+1)}{\Gamma(n-1)} \frac{e}{(1-k)(\alpha+\rho)^{1-k}} , &\mathrm{if}~k \in \mathbb{Z}_{k \leq 0}. \\
    \end{cases}
\end{equation}
Note that the probability term in $(\diamond)$ is the same as the CDF of the $\mathrm{Erlang}(n-1, n\alpha_1)$ with rate $n\alpha_1$ evaluated at $\frac{1}{n}$ since $\hat{\alpha}_1 \sim \mathrm{IG}(n-1, n\alpha_1)$ from (\ref{eq: MLEdist}).
Thus, we have
\begin{align*}
    (\diamond) &= \frac{1}{1-C_{1,n}}\frac{1}{G_k(1/n;n)} \frac{\gamma(n-1,\alpha_1)}{\Gamma(n-1)}\\
    &\leq \frac{e^{\alpha_1 + \rho}}{1-C_{1,n}}\frac{\Gamma(n-k+1)}{(\alpha_1+\rho)^{n-k}} \frac{\gamma(n-1,\alpha_1)}{\Gamma(n-1)} \hspace{1em} \text{by (\ref{eq: Gkbnd})}\\
    &\leq \frac{e^{\alpha_1+\rho}}{1-C_{1,n}}\frac{\Gamma(n-k+1)}{\Gamma(n-1)} \frac{\alpha_1^{n-1}}{(\alpha_1 + \rho)^{n-k}} \numberthis{\label{eq: incgam}} \\
    &\leq  \frac{e^{\alpha_1+\rho}}{1-C_{1,n}} \frac{\Gamma(n-k+1)}{\Gamma(n-1)}\frac{1}{(\alpha_1+\rho)^{1-k}} \\
    &= \mathcal{O}(n^{2-k}), \numberthis{\label{eq: diamon_result}}
\end{align*}
where (\ref{eq: incgam}) holds from $\gamma(s, x) \leq x^{s}$ for any $s \geq 1$ and $x >0$.
Therefore, by combining (\ref{eq: integral_restricted}) and (\ref{eq: diamon_result}) with (\ref{eq: star}) and $\mathbb{P}[\hat{\kappa} \in K(\epsilon)] = \mathcal{O}(e^{-n\epsilon})$, we have
\begin{equation*}
    (\star) \leq \begin{cases}
        \mathcal{O}(ne^{-n\epsilon}), & \mathrm{if}~k \in \mathbb{Z}_{\geq 2}\\
        \mathcal{O}(n\log(n)e^{-n\epsilon}), & \mathrm{if}~k=1, \\
        \mathcal{O}(n^{2-k}e^{-n\epsilon}), & \mathrm{if}~k \in \mathbb{Z}_{\leq 0}. \numberthis{\label{eq: a1_2}}
    \end{cases}
\end{equation*}
By combining (\ref{eq: a1_2}) with (\ref{eq: pn_sum_STSR}) and (\ref{eq: pn_decom}), we obtain for $k\in \mathbb{Z}_{\geq 0}$
\begin{align*} 
    \mathbb{E}\bigg[  \sum_{t=K\bar{n} +1}^T \mathbbm{1}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}^c(\epsilon), \mathcal{M}_\epsilon^c(t)] \bigg] & \leq \sum_{n=\bar{n}}^T \bigg(\frac{e^{-n}}{1-e^{-n}}+ \frac{e^{-n \frac{3\epsilon}{4\mu_1}} + \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)}}{C_2(\mu, \epsilon, k)} 
    + (\star) \bigg)\\
    &\leq \sum_{n=\bar{n}}^T \bigg( \mathcal{O}(e^{-n}) + \mathcal{O}(e^{-n\epsilon}) + \mathcal{O}\left(e^{-n\epsilon^2}\right) \\
    &\hspace{12em}+ \mathcal{O}\left(\psi(n,k) e^{-n\epsilon}\right) \bigg) \\
  &= \mathcal{O}(1) + \mathcal{O}(\epsilon^{-1}) + \mathcal{O}(\epsilon^{-2}) + \mathcal{O}\left(\epsilon^{-\max(2, 3-k)}\right),
\end{align*}
where 
\begin{equation*}
    \psi(n,k) = n \mathbbm{1}[k \geq 2] + n\log(n)\mathbbm{1}[k=1] + n^{2-k} \mathbbm{1}[ k \leq 0].
\end{equation*}
Note that the analysis on term $(\star)$ also holds for $\mathrm{STS}\text{-}\mathrm{T}$ with $k \in \mathbb{Z}_{<0}$.
However, differently from the case of $k \in \{ 0, 1\}$, priors with $k \in \mathbb{Z}_{<0}$ have additional problems in Lemma~\ref{lem: pn_cases} under the event $\{\hat{\kappa}_1 \in K(\epsilon), \bar{\alpha}_{1}(n) \leq \alpha_1 + \rho\}$, where the upper bound becomes a constant $\frac{1}{2}$.
\end{proof}

\subsection{Proof of Lemma~\ref{lem: mainreg}}\label{app: lem6}
Firstly, we state a well-known fact that is utilized in the proof. 
\begin{fact}~\label{fact1}
When $X \sim\mathrm{Erlang}(n, \beta)$ with rate parameter $\beta$, then $2\beta X$ follows the chi-squared distribution with $2n$ degree of freedom, i.e., $2\beta X \sim \chi_{2n}^2$.
\end{fact}

\lemmainreg*

\begin{proof}
From the sampling rule, it holds that
\begin{align*}
  \sum_{t=\bar{n} K+1}^T \mathbb{P}\left[j(t)=a, \tilde{\mu}_1(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon)\right]
    &\leq  \sum_{t=\bar{n} K+1}^T \mathbb{P}\left[j(t)=a, \tilde{\mu}_a(t) \geq \mu_1 -\epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon)\right].
\end{align*}
Fix a time index $t$ and denote $\mathbb{P}_t[\cdot] = \mathbb{P}[\cdot \mid \mathcal{F}_t]$ and $N_a(t) =n$.
To simplify notations, we drop the argument $t$ of $\tilde{\kappa}_a(t), \tilde{\alpha}_a(t)$ and $\tilde{\mu}_a(t)$ and the argument $n$ of $\hat{\kappa}_a(n), \hat{\alpha}_a(n), \bar{\alpha}_a(n)$.

Since $\tilde{\kappa}_a \in (0, \hat{\kappa}_a]$ holds from its posterior distribution, if $\tilde{\alpha}_a \geq \frac{ \mu_1 - \epsilon}{ \mu_1 - \epsilon-\hat{\kappa}_a}$ holds, then $\tilde{\mu}_a = \frac{\tilde{\kappa}_a \tilde{\alpha}_a}{\tilde{\alpha}_a -1} \leq  \mu_1 - \epsilon$ holds for any $\tilde{\kappa}_a$.
Recall that $f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(\cdot)$ denotes a density function of $\mathrm{Erlang}\left(n-k , \frac{n}{\alpha_{a,n}}\right)$ with rate parameter $\frac{n}{\alpha_{a,n}}$, which is the marginalized posterior distribution of $\tilde{\alpha}$ under $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$.
From the CDF of $\tilde{\kappa}$ in (\ref{eq: cdfkappa}), if $\hat{\kappa}_a < \mu_1 - \epsilon$, then
\begin{align*}
    \mathbb{P}_t\left[\tilde{\mu}_a \geq \mu_1 - \epsilon\right] &= \mathbb{P}_t\left[\tilde{\alpha}_a \leq 1\right] +\mathbb{P}_t\left[\tilde{\kappa}_a \geq \frac{\tilde{\alpha}_a-1}{\tilde{\alpha}_a} (\mu_1 - \epsilon) \cap \tilde{\alpha}_a \in \left(1, \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}_a} \right) \right] \\
     &=\int_{0}^1 f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{1}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}}f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathbb{P}_t\left[\tilde{\kappa}_a \geq \frac{x-1}{x} (\mu_1 - \epsilon) \right] \mathrm{d} x\\
    &=\int_{0}^1 f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{1}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}}f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( 1 - \left( \frac{x-1}{\hat{\kappa} x} (\mu_1 - \epsilon) \right)^{nx} \right) \mathrm{d} x\\
    &= \int_{0}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x - \int_{1}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}}f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa} x} (\mu_1 - \epsilon) \right)^{nx}\mathrm{d} x.
\end{align*}
Since $\frac{x}{x-y}$ is increasing with respect to $y < x$ and $\hat{\kappa} \leq \kappa+ \epsilon$ holds on $\mathcal{E}$, we have for $\mathcal{E}$
\begin{equation*}
    \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}} \leq  \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - (\kappa + \epsilon)}.
\end{equation*}
Let 
\begin{equation} \label{eq: defeta}
    \eta_a(\epsilon) = \frac{\kappa_a (\Delta_a - \epsilon) - \epsilon \mu_a }{(\mu_a-\kappa_a)(\mu_1 - \kappa_a - 2\epsilon ) } > 0
\end{equation}
be a deterministic constant that depends only on the model and $\epsilon$ and satisfies
\begin{align*}
    \alpha_a - \eta_a(\epsilon) &= \frac{\mu_a}{\mu_a -\kappa_a} - \frac{\kappa_a (\Delta_a - \epsilon) - \epsilon \mu_a }{(\mu_a-\kappa_a)(\mu_1 - \kappa_a - 2\epsilon ) }  \\
    &= \frac{\mu_a \mu_1 - \kappa_a \mu_a -2\epsilon \mu_a - \kappa_a (\mu_1 -\mu_a - \epsilon) + \epsilon \mu_a }{(\mu_a-\kappa_a)(\mu_1 - \kappa_a - 2\epsilon ) } \\
    &= \frac{\mu_1 (\mu_a - \kappa_a) - \epsilon(\mu_a - \kappa_a)}{(\mu_a-\kappa_a)(\mu_1 - \kappa_a - 2\epsilon )}\\
    &= \frac{\mu_1 - \epsilon}{\mu_1 - \kappa_a - 2\epsilon}.
\end{align*}
Since $\eta_a(\epsilon)>0$, it holds that for any $\epsilon \in (0, \varepsilon_a)$
\begin{equation*}
   
  \alpha_a - \eta_{a}(\epsilon) = \frac{\mu_1 - \epsilon}{\mu_1 - \kappa_a - 2\epsilon} \leq \frac{\mu_a}{\mu_a - \kappa_a} = \alpha_a.
\end{equation*}
Note that $\frac{\mu}{\mu - \kappa}=\alpha$ holds and the change of $\mu$ to $\mu'$ with fixed $\kappa$ that is $\frac{\mu'}{\mu' - \kappa}$, implies how the value of the shape parameter $\alpha'$ should be to satisfy $\mu((\kappa, \alpha')) = \mu'$.
For example, $\theta= (\kappa_a + \varepsilon_a, \alpha_a)$ satisfies $\mu(\theta) \leq \mu_a + \frac{\delta_a}{2}$.
Thus, if $\mu((\kappa_a+\varepsilon_a, \alpha)) = \mu_1 - \epsilon > \mu_a + \frac{\delta_a}{2}$, then $\alpha$ should be smaller than $\alpha_a$.
Hence, we have
\begin{align*}
    \mathbbm{1}[\mathcal{E}_{a,n}(\epsilon)]\mathbb{P}_t\bigg[\tilde{\mu}_a &\geq \mu_1 - \epsilon\bigg] \\
    &\leq \mathbbm{1}[\mathcal{E}_{a,n}(\epsilon)] \bigg( \int_{0}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x  \\
    & \hspace{9em} - \int_{1}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}}f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa} x} (\mu_1 - \epsilon) \right)^{nx}\mathrm{d} x \bigg)\\
    &\leq \mathbbm{1}[\mathcal{E}_{a,n}(\epsilon)]\int_{0}^{\frac{\mu_1 - \epsilon}{\mu_1 - \epsilon - \hat{\kappa}}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x \numberthis{\label{eq: tmusmall}}\\
    &\leq \mathbbm{1}[\mathcal{E}_{a,n}(\epsilon)]  \int_{0}^{\alpha_a -\eta_a(\epsilon)} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x = \mathbbm{1}[\mathcal{E}_{a,n}(\epsilon)]  \mathbb{P}_t[ \tilde{\alpha}_a(t) \leq \alpha_a - \eta_a(\epsilon)]. \numberthis{\label{eq: overestimationtmu1}}
\end{align*}
Therefore, by taking expectation and using Fact~\ref{fact1}, we have
\begin{align*}
    \mathbb{P}\left[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon) \right] &\leq \mathbb{P}[ \tilde{\alpha}_a \leq \alpha_a - \eta_a(\epsilon), \mathcal{E}_{a,n}(\epsilon)], \\
    &= \mathbb{P}\left[ Z \leq \frac{2n}{\alpha_{a,n}}\left( \alpha - \eta_a(\epsilon) \right), \mathcal{E}_{a,n}(\epsilon)\right] \numberthis{\label{eq: l7bungi}}
\end{align*}
where $Z$ is a random variable following the chi-squared distribution with $2(n-k)$ degrees of freedom, i.e., $Z \sim \chi_{2n-2k}^2$.

\subsubsection{Under $\mathrm{STS}$}~\label{sec: L7STS}
Here, we first consider the case of $\mathrm{STS}$ where we replace $\alpha_{a,n}$ with $\hat{\alpha}_a(n)$.

Since $\hat{\alpha}_a \in [\alpha_a - \epsilon_{a,l}, \alpha_a + \epsilon_{a,u}] $ holds on $\mathcal{E}_{a,n}(\epsilon)$, we have
\begin{equation}\label{eq: haonE}
    \frac{1}{\alpha_a} - \epsilon \left( 1 + \frac{1}{\kappa_a} \right)=\frac{1}{\alpha_a + \epsilon_{a,u}}\leq \frac{1}{\hat{\alpha}_a} \leq \frac{1}{\alpha_a - \epsilon_{a,l}} =  \frac{1}{\alpha_a} + \epsilon
\end{equation}
by the definition of $\epsilon_{a,l}(\epsilon)$ and $\epsilon_{a,u}(\epsilon)$ in (\ref{eq: epslu}).

By replacing $\alpha_{a,n}$ with $\hat{\alpha}_a(n)$ in (\ref{eq: l7bungi}) and applying (\ref{eq: haonE}), we have
\begin{align*}
     \mathbb{P}\left[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon) \right] &\leq \mathbb{P}\left[ Z \leq \frac{2n}{\hat{\alpha}_a}\left( \alpha_a - \eta_a(\epsilon) \right), \mathcal{E}_{a,n}(\epsilon)\right] \\
     &\leq \mathbb{P}\left[ Z \leq 2n\left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right)\right] \\
     &= \mathbb{P}\left[ Z \leq 2(n-k) \frac{n}{n-k}\left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right)\right]. \numberthis{\label{eq: tildealpha}}
\end{align*}

\paragraph{Priors with $k \in\mathbb{Z}_{\leq 0}$.}
Let us first consider the case $k \in\mathbb{Z}_{\leq 0}$, where we have $\frac{n}{n-k} \leq 1$.
It holds that
\begin{align*}
     \mathbb{P}\left[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon) \right] &\leq \mathbb{P}\left[ Z \leq 2(n-k) \frac{n}{n-k}\left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right)\right] \\
     &\leq \mathbb{P}\left[ Z \leq 2(n-k)\left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right)\right].
\end{align*}
Note that the definition of $\varepsilon_a$ in Theorem~\ref{thm: RegOpt} is set to satisfy $\left( \frac{1}{\alpha} +\epsilon \right)\left( \alpha - \eta_a(\epsilon) \right)<1$ for any $\epsilon \leq \varepsilon_a$.
Thus, we can apply Lemma~\ref{lem: chicramer}, which shows
\begin{equation}\label{eq: overestimationtmu2}
    \mathbb{P}\left[ Z \leq 2(n-k)\left( 1 - \frac{\eta_a(\epsilon)}{\alpha_a} + \epsilon (\alpha_a -\eta_a(\epsilon) ) \right)\right] \leq e^{-(n-k) D_{a,k}(\epsilon)},
\end{equation}
where
\begin{multline}\label{eq: defDa}
    D_{a,k}(\epsilon) := -\log\left( 1 - \frac{\eta_a(\epsilon)}{\alpha_a} + (\max(0, k) + 1)\epsilon (\alpha_a -\eta_a(\epsilon) )\right) \\ - \frac{\eta_a(\epsilon)}{\alpha_a} +(\max(0, k)+1) \epsilon (\alpha_a -\eta_a(\epsilon) )
\end{multline}
is a finite constant that only depends on the model parameters, $\epsilon$, and prior parameter $k$.

For arbitrary $n_a > 0$, applying (\ref{eq: overestimationtmu2}) to (\ref{eq: l7bungi}) gives
\begin{align*}
  \sum_{t=\bar{n} K+1}^T \mathbb{E}[\mathbbm{1} [j(t)=a, \tilde{\mu}_1(t) \geq \mu_1 -  \epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon) ]] \hspace{-5em}& \\
  &\leq \sum_{t=\bar{n} K+1}^T\mathbb{P}[j(t)=a, \tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon)] \\
    &\leq n_a +  \sum_{t=\bar{n} K+1}^{T}\mathbb{P}[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon), N_a(t) \geq n_a ] \\
    &\leq n_a + \sum_{t=\bar{n} K+1}^T e^{-(n_a-k) D_{a,k}(\epsilon)}  \\
    &\leq n_a + \sum_{t=\bar{n} K+1}^T e^{-n_a D_{a,k}(\epsilon)} = n_a + Te^{- n_a D_{a,k}(\epsilon)}.
\end{align*}
Letting $n_a = \frac{\log T }{D_{a,k}(\epsilon)}$ concludes the cases of priors with $k \in \mathbb{Z}_{\leq 0}$.

\paragraph{Priors with $k \in \mathbb{Z}_{>0}$}
Next, consider the case $k \in \mathbb{Z}_{>0}$.
Recall that we first play every arm $k+1$ times if $k >0$, which implies that $n - k >0$.
For $n \geq \frac{1}{\alpha \epsilon} + k + 1$, it holds that
\begin{equation}\label{eq: positivek2}
    \frac{n}{n-k}\left( \frac{1}{\alpha} +\epsilon \right) \leq \frac{1}{\alpha} + (k+1)\epsilon.
\end{equation}
By applying (\ref{eq: positivek2}) to (\ref{eq: l7bungi}), we have for $n \geq \frac{1}{\alpha \epsilon} + k + 1$,
\begin{align*}
    \mathbb{P}[ \tilde{\alpha}_a \leq \alpha_a - \eta_a(\epsilon), \mathcal{E}_{a,N_a(t)}(\epsilon)] \leq \mathbb{P}\left[ Z \leq 2(n-k)\left( 1 - \frac{\eta_a(\epsilon)}{\alpha_a} + (k+1)\epsilon (\alpha_a -\eta_a(\epsilon) ) \right)\right].
\end{align*}
Similarly, by applying Lemma~\ref{lem: chicramer}, one can see that for $n \geq  \frac{1}{\alpha_a \epsilon} + k + 1$
\begin{equation}\label{eq: overestimationtmu3}
  \mathbb{P}[ \tilde{\alpha}_a \leq \alpha_a - \eta_a(\epsilon), \mathcal{E}_{a,N_a(t)}(\epsilon)] \leq e^{-(n-k)D_{a,k}(\epsilon)},
\end{equation}
where $D_{a,k}(\epsilon)$ is defined in (\ref{eq: defDa}).

When $k \in \mathbb{Z}_{>0}$, let $n_a \geq \frac{1}{\alpha_a \epsilon} + k + 1 $ be arbitrary. By applying (\ref{eq: overestimationtmu3}) to (\ref{eq: l7bungi}) again, we have 
\begin{align*}
  \sum_{t=\bar{n} K+1}^T \mathbb{E}[\mathbbm{1} [j(t)=a, \tilde{\mu}_1(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon) ]] \hspace{-10em}&\\ &\leq \sum_{t=\bar{n} K+1}^T\mathbb{P}[j(t)=a, \tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon)] \\
    &\leq n_a +  \sum_{t=\bar{n} K+1}^{T}\mathbb{P}[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,N_a(t)}(\epsilon), N_a(t) \geq n_a ] \\
    &\leq n_a + \sum_{t=\bar{n} K+1}^T e^{-(n_a-k) D_{a,k}(\epsilon)} = n_a + Te^{- (n_a-k) D_{a,k}(\epsilon)}.
\end{align*}
Letting $n_a = k+1 + \frac{1}{\alpha_a \epsilon} + \frac{\log T }{D_{a,k}(\epsilon)}$ concludes the cases of priors with $k > 0$.

\subsubsection{Under $\mathrm{STS}\text{-}\mathrm{T}$}
Here, we consider the case of $\mathrm{STS}\text{-}\mathrm{T}$ where we replace $\alpha_{a,n}$ with $\bar{\alpha}_a(n) = \min(\hat{\alpha}_a(n), n)$.
From the definition of $\bar{\alpha}_a(n)$, it holds that for $\epsilon \leq \varepsilon_a$
\begin{equation*}
    \forall n \geq \alpha_a + 1 :  \mathbbm{1}[\bar{\alpha}_a(n) = \hat{\alpha}_a(n), \mathcal{A}_{a,n}(\epsilon) ] = 1.
\end{equation*}
Therefore, for $n \geq \alpha_a + 1$, the analysis on $\mathrm{STS}$ can be applied to $\mathrm{STS}\text{-}\mathrm{T}$ directly.

Let us consider the case where $\bar{\alpha}_a(n) = n < \alpha_a + 1$ holds under the condition $\mathcal{A}_{a,n}(\epsilon)$.
By replacing $\alpha_{a,n}$ with $n$ in (\ref{eq: l7bungi}) and following the same steps as in (\ref{eq: l7bungi}) and (\ref{eq: overestimationtmu2}), we have for any $k \in \mathbb{Z}$,
\begin{align*}
    \mathbb{P}\left[\tilde{\mu}_a(t) \geq \mu_1 - \epsilon, \mathcal{E}_{a,n}(\epsilon) \right] &\leq \mathbb{P}\left[ Z \leq \frac{2n}{n}\left( \alpha_a - \eta_a(\epsilon) \right), \mathcal{E}_{a,n}(\epsilon)\right] \\
     &\leq \mathbb{P}\left[ Z \leq 2(n-k) \frac{1}{n-k}\left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right), \mathcal{E}_{a,n}(\epsilon)\right] \\ 
     &\leq \mathbb{P}\left[ Z \leq 2(n-k) \left( \frac{1}{\alpha_a} +\epsilon \right)\left( \alpha_a - \eta_a(\epsilon) \right), \mathcal{E}_{a,n}(\epsilon)\right] \\
     &\leq e^{-(n-k) D_{a,k}(\epsilon)},
\end{align*}
where $D_{a,k}(\epsilon)$ defined in (\ref{eq: defDa}).
Therefore, the same result follows by the analysis in Section~\ref{sec: L7STS}.

\subsubsection{Asymptotic behavior of $D_{a,k}(\epsilon)$}
Finally, we show that $\lim_{\epsilon \to 0} D_{a,k}(\epsilon) = \mathrm{KL}_{\mathrm{inf}}(a)$.
From their definitions of $\eta_a(\epsilon)$ in (\ref{eq: defeta}) and $\Delta_a = \mu_1 - \mu_a$, we have
\begin{align*}
    \lim_{\epsilon \to 0}\eta_a(\epsilon) &= \lim_{\epsilon \to 0} \frac{\kappa_a(\Delta_a -\epsilon) - \epsilon \mu_a}{(\mu_a - \kappa_a)(\mu_1 - \kappa_a - 2\epsilon)}
    \\ &=\frac{\kappa_a \Delta_a}{(\mu_a - \kappa_a)(\mu_1 - \kappa_a)} =  \frac{\kappa_a (\mu_1 - \mu_a)}{(\mu_a - \kappa_a)(\mu_1 - \kappa_a)} = (\alpha_a - 1 )\frac{\mu_1 -\mu_a}{\mu_1 -\kappa_a}.
\end{align*}
Then, it holds that
\begin{align*}
  \lim_{\epsilon \to 0} 1 - \frac{\eta_a(\epsilon)}{\alpha_a} &= 1 - \left( \frac{\alpha_a - 1}{\alpha_a} \frac{\mu_1 - \mu_a}{\mu_1 - \kappa_a} \right) \\
  &= \frac{\alpha_a (\mu_1 -\kappa_a) - (\alpha_a-1)(\mu_1 -\mu_a)}{\alpha_a(\mu_1 -\kappa_a)} \\
  &= \frac{\alpha_a(\mu_a - \kappa_a) + \mu_1 - \mu_a}{\alpha_a(\mu_1 - \kappa_a)} \\ 
  &=  \frac{\mu_a}{\mu_a - \kappa_a} \frac{(\mu_a - \kappa_a) }{\alpha_a(\mu_1 - \kappa_a)} + \frac{\mu_1 - \mu_a }{\alpha_a(\mu_1 - \kappa_a)} \hspace{2em} \because \alpha_a = \frac{\mu_a}{\mu_a - \kappa_a}\\
  &= \frac{\mu_1}{\alpha_a(\mu_1 - \kappa_a)} =: \frac{1}{X_a},
\end{align*}
Therefore, from the definition of $D_{a,k}(\epsilon)$ in (\ref{eq: defDa})
\begin{align*}
    \lim_{\epsilon \to 0} D_{a,k}(\epsilon)&= \lim_{\epsilon \to 0} \bigg[
    -\log\left( 1 - \frac{\eta_a(\epsilon)}{\alpha_a} + (\max(0, k) + 1) (\alpha_a -\eta_a(\epsilon) )\epsilon\right) \\ 
    &\hspace{11em}- \frac{\eta_a(\epsilon)}{\alpha_a} +(\max(0, k)+1)  (\alpha_a -\eta_a(\epsilon) ) \epsilon\bigg] \\
    &= - \log (1- \lim_{\epsilon \to 0} \frac{\eta_a(\epsilon)}{\alpha_a}) - \lim_{\epsilon \to 0} \frac{\eta_a(\epsilon)}{\alpha_a}\\
    &= -\log \frac{1}{X_a} + \frac{1}{X_a} - 1 = \log X_a +  \frac{1}{X_a} - 1 \\
    &= \log\left( \alpha_a \frac{\mu_1 - \kappa_a}{\mu_1} \right) + \frac{\mu_1}{\alpha_a(\mu_1 -\kappa_a)} - 1 = \mathrm{KL}_{\mathrm{inf}}(a),
\end{align*}
where the last equality comes from Lemma~\ref{lem: KLinf}.
\end{proof}

\subsection{Proof of Lemma~\ref{lem: korda}}\label{app: lem7}
Firstly, we state two well-known facts that are utilized in the proof. 
\begin{fact}~\label{fact2}
When $X \sim\mathrm{Pa}(\kappa, \alpha)$ with the scale parameter $\kappa \in \mathbb{R}$ and rate parameter $\alpha \in \mathbb{R}_{+}$, then $\log\left( \frac{X}{\kappa} \right)$ follows the exponential distribution with rate $\alpha$, i.e., $\log\left( \frac{X}{\kappa} \right) \sim \mathrm{Exp}(\alpha)$.
\end{fact}
\begin{fact}~\label{fact3}
Let $X_1, \ldots, X_n$ be identically independently distributed with the exponential distribution with the rate parameter $\alpha$, i.e., $X_i \stackrel{\text{i.i.d.}}{\sim} \mathrm{Exp}(\alpha)$ for any $i \in [n]$.
Then, their sum follows the Erlang distribution with the shape parameter $n\in\mathbb{N}$ and rate parameter $\alpha$, i.e., $\sum_{i=1}^n X_i \sim \mathrm{Erlang}(n, \alpha)$. 
\end{fact}

\lemkordaused*

\begin{proof}
When one considers the Pareto distribution with known scale parameter $\kappa$ that belongings to the one-dimensional exponential family, the posterior on the shape parameter $\alpha^{\mathrm{one}} >0$ after observing $n=N_1(t)$ rewards is given for $k \in \mathbb{Z}$
\begin{equation}\label{eq: betapost}
    \alpha^{\mathrm{one}}~|~\mathcal{F}_t \sim \mathrm{Erlang}\left(n-k+1, X_n \right),
\end{equation}
where $X_n = \sum_{s=1}^n \log(r_{1, s}) - n \log (\kappa_1)$.
Note that $X_n \sim \mathrm{Erlang}(n, \alpha_1)$ from Facts~\ref{fact2} and~\ref{fact3}.
Let $\tilde{\alpha}_1^{\mathrm{one}}$ be a sample from the posterior distribution in (\ref{eq: betapost}).
Then, for one-dimensional Pareto bandits, it holds from (\ref{eq: def_inc_gamma}) that
\begin{equation*}
    \mathbb{P}[\tilde{\mu}_1(t) \leq \mu_1 - \epsilon| \mathcal{F}_t] = \mathbb{P}\left[ \tilde{\alpha}_1^{\mathrm{one}} \geq \beta \,\middle\vert\,  \mathcal{F}_t \right] = \frac{\Gamma\left(n-k+1, \beta  X_n \right)}{\Gamma(n-k+1)},
\end{equation*}
where we denoted $\beta = \frac{\mu_1 - \epsilon}{\mu_1-\epsilon -\kappa_1}$ satisfying $\mu(\kappa_1, \beta) = \mu_1 - \epsilon$.
Therefore, Lemma~\ref{lem: kordaresult} can be written as
\begin{align*}
    \sum_{t=1}^T \mathbb{E}\left[ \mathbbm{1} \left[ j(t)\ne 1, \mathcal{M}_\epsilon^c(t)\right] \right] &= \sum_{t=1}^T \sum_{n=1}^T \mathbb{E}\left[ \mathbbm{1} \left[ j(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) = n \right] \right] \\
    &=  \sum_{t=1}^T \sum_{n=1}^T \mathbb{E}\left[\mathbb{P}\left[ j(t)\ne 1, \mathcal{M}_\epsilon^c(t), N_1(t) = n \,\middle\vert\,  \mathcal{F}_t \right] \right] \\
    &= \sum_{t=1}^T \sum_{n=1}^T \int_0^\infty \frac{\Gamma(n+1, \beta x)}{\Gamma(n+1)} \frac{\alpha_1^n}{\Gamma(n)}x^{n-1} e^{-\alpha_1 x} \mathrm{d} x \leq \mathcal{O}(\epsilon^{-1}),
\end{align*}
where we injected the density function of the Erlang distribution into the last equality.

On the other hand, for two-parameter Pareto bandits where the scale parameter is unknown, it holds by the law of total expectation that
\begin{align*}
    \mathbb{E}[\mathbbm{1}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}(\epsilon), \mathcal{M}_\epsilon^c(t)]] &= \mathbb{E}_{\hat{\kappa}_1, \hat{\alpha}_1}\left[ \mathbb{P}[j(t)\ne 1, \mathcal{K}_{1,N_1(t)}(\epsilon), \mathcal{M}_{\epsilon}^c(t) | \mathcal{F}_t] \right] \\
    &= \mathbb{E}_{\hat{\kappa}_1, \hat{\alpha}_1}\left[ \mathbbm{1}[\mathcal{K}_{1,N_1(t)}(\epsilon)]\mathbb{P}[j(t)\ne 1,\mathcal{M}_{\epsilon}^c(t) | \mathcal{F}_t] \right],
\end{align*}
where the last equality holds since $\mathcal{K}$ is determined by the history $\mathcal{F}_t$.

From Lemma~\ref{lem: tmusmall} with $y = \mu_1 -\epsilon $, it holds for any $\xi \leq \frac{\mu_1 -\epsilon}{\mu_1-\epsilon - \kappa_1} = \beta$ that
\begin{align*}
    \mathbbm{1}[\mathcal{K}_{1,n}(\epsilon)]\mathbb{P}[\tilde{\mu}_1(t) \leq \mu_1 - \epsilon| \mathcal{F}_t] \hspace{-8em}& \\
    &\leq  \mathbbm{1}[\mathcal{K}_{1,n}(\epsilon)] \left( \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \int_{1}^{\xi} f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{\xi}^\infty f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x \right)\\
    &\leq \mathbbm{1}[\mathcal{K}_{1,n}(\epsilon)] \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1- \frac{\Gamma\left(n-k, \frac{n}{\alpha_{1,n}}\xi\right)}{\Gamma(n-k)}\right) + \frac{\Gamma\left(n-k, \frac{n}{\alpha_{1,n}}\xi\right)}{\Gamma(n-k)} \right) \numberthis{\label{eq: cvx}}
\end{align*}
which is a convex combination of $1$ and $\left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n$.
Therefore, RHS of (\ref{eq: cvx}) increases as $\frac{\Gamma\left(n-k, \frac{n}{\alpha_{1,n}}\xi\right)}{\Gamma(n-k)}$ increases.
From the definition of $\Gamma(n,x)$, it holds that $\Gamma(n, x) \geq \Gamma(n, x+y)$ for any positive $y>0$ and $\Gamma(n+1, x) = n\Gamma(n,x) + x^n e^{-x}$.
Since $\frac{n}{\hat{\alpha}_1(n)} \leq \frac{n}{\bar{\alpha}_1(n)}$ holds for any $n \in \mathbb{N}$, it holds for $k \in \mathbb{Z}_{\geq 0}$ that
\begin{equation*}
    \frac{\Gamma\left(n-k, \frac{n}{\bar{\alpha}_1(n)}\xi\right)}{\Gamma(n-k)}  \leq \frac{\Gamma\left(n-k, \frac{n}{\hat{\alpha}_1(n)}\xi\right)}{\Gamma(n-k)} \leq \frac{\Gamma\left(n, \frac{n}{\hat{\alpha}_1(n)}\xi\right)}{\Gamma(n)}.
\end{equation*}

Let us denote $Y_n := \frac{n}{\hat{\alpha}_1(n)} = \sum_{i=1}^n \log (r_{1,s}) - n \log(\hat{\kappa}_1(n))$, which follows the Erlang distribution with shape $n-1$ and rate $\alpha_1$~\citep{malik1970estimation}.
By taking expectation with respect to $\hat{\kappa}_1(n)$, we have for any $\xi \leq \beta$ that
\begin{align*}
  \mathbb{E}_{\hat{\kappa}_1}[ \mathbbm{1}[\mathcal{K}_{1,n}(\epsilon)]\mathbb{P}[\tilde{\mu}_1(t) \leq \mu_1 - \epsilon| \mathcal{F}_t] ] \hspace{-8em}& \\
  &\leq \int_{\kappa_1}^{\kappa_1+\epsilon}  \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1- \frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)}\right) + \frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)} \right) \mathbb{P}[\hat{\kappa}_1(n) = x] \mathrm{d} x  \\
  &= \mathbb{P}[\mathcal{K}_{1,n}(\epsilon)] \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1-\frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)} \right) + \frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)} \right) \\
  &= \left(1 - \left( \frac{\kappa_1}{\kappa_1 + \epsilon} \right)^{n\alpha_1} \right) \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1- \frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)} \right) + \frac{\Gamma\left(n, \xi Y_n\right)}{\Gamma(n)} \right),
\end{align*}
where we used $\hat{\kappa}_1(n) \sim \mathrm{Pa}(\kappa_1, n\alpha_1)$ in (\ref{eq: MLEdist}) for the last equality.

Therefore, under the two-parameter Pareto distribution, the following holds for any $\xi \leq \beta$ under both $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$ with $k\in \mathbb{Z}_{\geq 0}$ that
\begin{multline*}
  \mathbb{E}_{\hat{\kappa}_1,\hat{\alpha}_1}[ \mathbbm{1}[\mathcal{K}_{1,n}(\epsilon)]\mathbb{P}[\tilde{\mu}_1(t) \leq \mu_1 - \epsilon| \mathcal{F}_t] ] \\ 
    \leq \left(1 - \left( \frac{\kappa_1}{\kappa_1 + \epsilon} \right)^{n\alpha_1} \right) \int_0^{\infty} \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1- \frac{\Gamma\left(n, \xi y\right)}{\Gamma(n)} \right) + \frac{\Gamma\left(n, \xi y\right)}{\Gamma(n)} \right) \frac{\alpha_1^{n-1}}{\Gamma(n-1)}y^{n-2} e^{-\alpha_1 y} \mathrm{d} y.
\end{multline*}
Therefore, Lemma~\ref{lem: kordaresult} concludes the proof for any $n \in \mathbb{N}$, by carefully selecting $\xi \leq \beta$ satisfying
\begin{multline*}
    \left(1 - \left( \frac{\kappa_1}{\kappa_1 + \epsilon} \right)^{n\alpha_1} \right) \int_0^{\infty} \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi))}\right)^n \left( 1- \frac{\Gamma\left(n, \xi y\right)}{\Gamma(n)} \right) + \frac{\Gamma\left(n, \xi y\right)}{\Gamma(n)} \right) \frac{\alpha_1^{n-1}}{\Gamma(n-1)}y^{n-2} e^{-\alpha_1 y} \mathrm{d} y \\
    \leq \int_0^\infty \frac{\Gamma(n+1, \beta y)}{\Gamma(n+1)} \frac{\alpha_1^n}{\Gamma(n)}y^{n-1} e^{-\alpha_1 y} \mathrm{d} y .
\end{multline*}
Note that when we consider $\mathrm{STS}$ with $k=-1$, we have to find $\xi' \leq \beta$ such that
\begin{align*}
    \left(1 - \left( \frac{\kappa_1}{\kappa_1 + \epsilon} \right)^{n\alpha_1} \right)  \hspace{-7em}& \\ 
    &\times \int_0^{\infty} \left(  \left( \frac{\mu_1 - \epsilon}{\mu((\kappa_1, \xi'))}\right)^n \left( 1- \frac{\Gamma\left(n+1, \xi' y\right)}{\Gamma(n+1)} \right) + \frac{\Gamma\left(n+1, \xi' y\right)}{\Gamma(n+1)} \right) \frac{\alpha_1^{n-1}}{\Gamma(n-1)}y^{n-2} e^{-\alpha_1 y} \mathrm{d} y \\
    &\hspace{15em}\leq \int_0^\infty \frac{\Gamma(n+1, \beta y)}{\Gamma(n+1)} \frac{\alpha_1^n}{\Gamma(n)}y^{n-1} e^{-\alpha_1 y} \mathrm{d} y .
\end{align*}
From $\Gamma(n, x) \geq \Gamma(n, x+y)$ for any positive $x, y>0$ and $\xi' \leq \beta$, we have for any $x > 0$ that
\begin{equation*}
    \frac{\Gamma\left(n+1, \xi' x \right)}{\Gamma(n+1)} \geq  \frac{\Gamma(n+1, \beta x)}{\Gamma(n+1)}.
\end{equation*}
Therefore, for $k \in \mathbb{Z}_{\leq -1}$, we might not be able to apply the results by \citet{KordaTS}.
\end{proof}

\subsection{Proof of Lemma~\ref{lem: minor}}\label{sec: minor}
We first state two lemmas on the event $\mathcal{K}$ and $\mathcal{A}$.
\begin{restatable}{lemma}{lemeKbound}\label{lem: eKbound}
For any algorithm and $a\in [K]$, it holds that for all $\epsilon >0$, $t >0 $, and $n \in \mathbb{N}$
\begin{equation*}
    \mathbb{P}\left[\mathcal{K}_{a,N_a(t)}^c(\epsilon), N_a(t)=n\right]  \leq \exp\left( -\frac{\alpha_a \epsilon}{\kappa_a+\epsilon}  n \right).
\end{equation*}
\end{restatable}
\begin{restatable}{lemma}{lemeAbound}\label{lem: eAbound}
For any algorithm and for any $a\in [K]$, it holds that for all $\epsilon \in \left(0, \frac{\kappa_a}{\alpha_a( \kappa_a+1)}\right)$ and $t >0$, and $n\geq \bar{n}$
\begin{equation*}
  \mathbb{P}\left[\mathcal{A}_{a,N_a(t)}^c(\epsilon), \mathcal{K}_{a,N_a(t)}(\epsilon), N_a(t)=n\right] \leq 2\exp\left( -\frac{\alpha_a^2 \epsilon^2}{4}n \right),
\end{equation*}
\end{restatable}

\lemminor*

\begin{proof}
From the Lemmas~\ref{lem: eKbound} and~\ref{lem: eAbound}, one can see that for $n \geq \bar{n}$,
\begin{align*}
    \mathbb{P}\left[ \mathcal{E}_{a,N_a(t)}^c(\epsilon), N_a(t)=n \right] &= \mathbb{P}\left[\mathcal{K}_{a,N_a(t)}^c(\epsilon), N_a(t)=n\right] + \mathbb{P}\left[\mathcal{A}_{a,N_a(t)}^c(\epsilon) , \mathcal{K}_{a,N_a(t)}(\epsilon), N_a(t)=n \right] \\
    &\leq \exp\left( -\frac{ \alpha_a \epsilon}{\kappa_a+\epsilon}n \right) + 2 \exp\left( -\frac{\alpha_a^2 \epsilon^2}{4}n \right).
\end{align*}
Since $\left\{j(t)=a, \mathcal{E}_{a,n}^c(\epsilon), N_a(t)=n \right\}$ occurs only once for any $n \in \mathbb{N}$, it holds that
\begin{align*}
    \sum_{t= \bar{n} K + 1}^T \mathbb{E}\left[\mathbbm{1}\left[ j(t)=a, \mathcal{E}^c_{a,N_a(t)}(\epsilon) \right] \right] &= 
     \sum_{t= \bar{n} K + 1}^T \sum_{n=\bar{n}}^{T} \mathbb{E}\left[\mathbbm{1}\left[ j(t)=a, \mathcal{E}^c_{a,N_a(t)}(\epsilon), N_a(t) =n \right] \right] \\
    &\leq \sum_{n=\bar{n}}^{\infty} \mathbb{E}\left[\mathbbm{1}\left[ \mathcal{E}_{a,N_a(t)}^c(\epsilon), N_a(t) =n\right]\right] \\
    & = \sum_{n=\bar{n}}^{\infty} \mathbb{P}\left[\mathcal{K}_{a,N_a(t)}^c(\epsilon), N_a(t) =n\right] \\
    & \hspace{3em}+ \mathbb{P}\left[\mathcal{A}_{a,N_a(t)}^c(\epsilon) \cap \mathcal{K}_{a,N_a(t)}(\epsilon), N_a(t) =n \right] \\
    &\leq\sum_{n=\bar{n}}^{\infty} \exp\left( -\frac{ \alpha_a \epsilon}{\kappa_a+\epsilon}n \right) + 2 \exp\left( -\frac{ \alpha_a^2 \epsilon^2}{4}n \right).
\end{align*}
Since $\exp(-an)$ with $a >0$ is a decreasing function with respect to $n$, it holds that
\begin{equation*}
    \sum_{n=2}^{\infty} \exp(-an) \leq \int_{1}^{\infty} \exp(-an) \mathrm{d} n = \frac{\exp(-a)}{a},
\end{equation*}
which concludes the proof.
\end{proof}


\subsubsection{Proof of Lemma~\ref{lem: eKbound}}
\lemeKbound*
\begin{proof}
Since $\hat{\kappa}_a(n) \sim \mathrm{Pa}(\kappa_a, n\alpha_a)$ holds for any $n \in \mathbb{N}$ in (\ref{eq: MLEdist}), it holds that
\begin{align*}
    \mathbb{P}\left[ \mathcal{K}^c_{a,N_a(t)}, N_a(t) =n \right] &= \mathbb{P}\left[ \hat{\kappa}_a(N_a(t)) \geq \kappa_a + \epsilon, N_a(t) =n \right] \\
    &= \left( \frac{\kappa_a}{\kappa_a + \epsilon} \right)^{n\alpha_a} \leq \exp\left( -\frac{ \alpha_a \epsilon}{\kappa_a + \epsilon }  n \right),
\end{align*}
which concludes the proof.
\end{proof}

\subsubsection{Proof of Lemma~\ref{lem: eAbound}}                  
\lemeAbound*
\begin{proof}
Fix a time index $t$ and denote $\mathbb{P}_t[\cdot] = \mathbb{P}[\cdot \mid \mathcal{F}_t]$ and $N_a(t) =n$.
To simplify notations, we drop the argument $n$ of $\hat{\kappa}_a(n)$ and $\hat{\alpha}_a(n)$. 

Let $r_{a,k}'$ be the $k$-th order statistics of $(r_{a,s})_{s=1}^n$ for arm $a$ such that $r_{a,1}' \leq r_{a,2}' \ldots \leq r_{a,n}'$.
From the definition of MLE of $\alpha_a$,
\begin{align*}
    \mathbb{P}[\hat{\alpha}_a \leq \alpha_a - \epsilon_{a,l}(\epsilon), \mathcal{K}_{a,N_a(t)}(\epsilon), N_a(t)=n ] &\leq \mathbb{P} \left[\frac{n}{\sum_{s=1}^n \log r_{a,s}' - n \log r_{a,1}'} \leq \alpha_a -\epsilon_{a,l}(\epsilon)  \right] \\
    &= \mathbb{P}\left[\frac{n}{\alpha_a -\epsilon_{a,l}(\epsilon)} \leq  \sum_{s=1}^{n} \log \frac{r_{a,s}'}{r_{a,1}'} \right] \\
    &= \mathbb{P}\left[\frac{n}{\alpha_a -\epsilon_{a,l}(\epsilon)} \leq n \log \frac{\kappa}{r_{a,1}'} + \sum_{s=1}^{n} \log \frac{r_{a,s}'}{\kappa}\right] \\
    &\leq \mathbb{P}\left[\frac{n}{\alpha_a -\epsilon_{a,l}(\epsilon)} \leq  \sum_{s=1}^{n} \log \frac{r_{a,s}}{\kappa_a} \right] \\ 
    &\leq \mathbb{P}\left[\epsilon \leq \frac{1}{n} \sum_{s=1}^{n} \log \frac{r_{a,s}}{\kappa_a} -\frac{1}{\alpha_a} \right],
\end{align*}
where the first equality holds from the definition of MLEs in (\ref{eq: MLEdist}), the second inequality holds since any sample generated from the Pareto distribution cannot be smaller than its scale parameter $\kappa$, and the last inequality holds from the definition of $\epsilon_{a,l}(\epsilon)$ in (\ref{eq: epslu}).

Similarly, one can derive that
\begin{align*}
        \mathbb{P}[\hat{\alpha}_a \geq \alpha_a + \epsilon_{a,u}(\epsilon) , \mathcal{K}_{a,N_a(t)}(\epsilon) , N_a(t)=n] &\leq \mathbb{P} \left[ \sum_{s=1}^n \log \frac{r_{a,s}}{\kappa_a} \leq \frac{n}{\alpha_a + \epsilon_{a,u}(\epsilon)} + n\log \frac{r_1'}{\kappa} \cap \mathcal{K}\right] \\
        &\leq \mathbb{P} \left[ \sum_{s=1}^n \log \frac{r_{a,s}}{\kappa} \leq \frac{n}{\alpha_a + \epsilon_{a,u}(\epsilon)} + n\log \frac{\kappa_a + \epsilon}{\kappa_a} \right] \\
        &\leq \mathbb{P} \left[ \sum_{s=1}^n \log \frac{r_{a,s}}{\kappa_a} \leq \frac{n}{\alpha_a + \epsilon_{a,u}(\epsilon)} + \frac{n \epsilon}{\kappa_a} \right] \\
        &\leq \mathbb{P} \left[ \frac{1}{n}\sum_{s=1}^n \log \frac{r_{a,s}}{\kappa_a} - \frac{1}{\alpha_a} \leq -\epsilon \right],
\end{align*}
where the second inequality holds since $r_{a,1}' = \hat{\kappa}_a \leq \kappa_a + \epsilon$ holds on $\mathcal{K}_{a,n}$, the third inequality from $\log(1+x) \leq x $ for $x>-1$, and the last inequality comes from the definition of $\epsilon_{a,u}(\epsilon)$.
From Fact~\ref{fact2}, $y_{a,s} := \log \left( \frac{r_{a,s}}{\kappa_a} \right) \sim \mathrm{Exp} (\alpha_a)$ and the last probability can be considered as a deviation of the sum of exponentially distributed random variables.

For the exponential distribution $\mathrm{Exp}(\alpha)$, we say that Bernstein's condition with parameter $b$ holds if
\begin{equation*}
    \mathbb{E}\left[M_k\right] \leq \frac{1}{2}k! \frac{1}{\alpha^2} b^{k-2} \quad \text{ for } k =3, 4, \ldots,
\end{equation*}
where $M_k$ implies the $k$-th central moment.
For $\mathrm{Exp}(\alpha_a)$, it holds that
\begin{equation*}
    \mathbb{E}\left[M_k\right] = \frac{!k}{\alpha_a^k} \leq \frac{k!}{2} \frac{1}{\alpha_a^2} \left( \frac{1}{\alpha_a}\right)^{k-2},
\end{equation*}
where $!k$ is the subfactorial of $k$ such that $!k \leq \frac{k!}{e} + \frac{1}{2} \leq \frac{k!}{2}$ for $k\geq 3$.
Hence, the exponential distribution with parameter $\alpha_a$ satisfies Bernstein's condition with parameter $\frac{1}{\alpha_a}$, so that it is subexponential with parameters $\left( \frac{2}{\alpha_a^2} , \frac{2}{\alpha_a} \right)$.
Therefore, by applying Lemma~\ref{lem: subexp}, we have
\begin{equation*}
    \mathbb{P}\left( \abs{\frac{1}{n} \sum_{s=1}^n y_{a,s} - \frac{1}{\alpha_a}} \geq \epsilon \right) \leq 2 \exp \left( - \frac{n}{4}\min \{ \alpha_a^2 \epsilon^2, \alpha_a \epsilon \}\right). 
\end{equation*}

Note that it holds for $\epsilon < \frac{\kappa_a}{\alpha_a(\kappa_a+1)}$ that
\begin{align*}
    \mathbb{P}[\hat{\alpha}_a \leq \alpha_a - \epsilon_{a,l}(\epsilon) \cap \mathcal{K}_{a,n} ] &\leq \mathbb{P}\left( \frac{1}{n} \sum_{s=1}^n y_{a,s} - \frac{1}{\alpha_a} \geq \epsilon \right)\\
    \mathbb{P}[\hat{\alpha}_a \geq \alpha_a + \epsilon_{a,u}(\epsilon) \cap \mathcal{K}_{a,n} ]&\leq \mathbb{P}\left( \frac{1}{n} \sum_{s=1}^n y_{a,s} - \frac{1}{\alpha_a} \leq -\epsilon \right),
\end{align*}
for $\epsilon_{a,l}(\epsilon) = \frac{\epsilon \alpha_a^2}{1+\epsilon \alpha_a}$ and $\epsilon_{a,u}(\epsilon) = \frac{\epsilon \alpha_a^2(\kappa_a+1)}{\kappa_a - \epsilon\alpha_a(\kappa_a+1)}$, which satisfy $\lim_{\epsilon \to 0} \max\{ \epsilon_{a,l}(\epsilon), \epsilon_{a,u}(\epsilon) \} = 0_+$.
Hence, by recovering the original notations, we obtain
\begin{align*}
    \mathbb{P}[\mathcal{A}_{a,N_a(t)}^c(\epsilon), \mathcal{K}_{a,N_a(t)}(\epsilon), N_a(t) =n]&=\mathbb{P}[\hat{\alpha}_a(n) \leq \alpha_a - \epsilon_{a,l}(\epsilon) , \mathcal{K}_{a,N_a(t)}, N_a(t)=n ] \\
    &\hspace{1em}+  \mathbb{P}[\hat{\alpha}_a(n) \geq \alpha_a + \epsilon_{a,u}(\epsilon), \mathcal{K}_{a, N_a(t)}, N_a(t)=n ] \\
    &\leq 2\exp \left( - \frac{\alpha^2_a \epsilon^2}{4}n \right),
\end{align*}
for $\epsilon < \frac{1}{\alpha_a}$ with $\alpha_a >1$.
\end{proof}

\subsection{Proof of Lemma~\ref{lem: tmusmall}}\label{sec: tmusmall}
\lemtmu*
\begin{proof}
Fix a time index $t$ with $N_a(t) =n$ and denote $\mathbb{P}_t[\cdot] = \mathbb{P}[\cdot \mid \mathcal{F}_t]$.
To simplify notations, we drop the argument $n$ of $\hat{\kappa}_a(n)$ and $\hat{\alpha}_a(n)$ and the argument $t$ of $\tilde{\alpha}_k(t)$, $\tilde{\alpha}_a(t)$, and $\tilde{\mu}_a(t)$.

When $\hat{\kappa}_a < y$ holds, $\tilde{\mu}_a \leq y$ can hold regardless of the value of $\tilde{\kappa}_a$ if $\hat{\kappa}_a \frac{\tilde{\alpha}_a}{\tilde{\alpha}_a-1} \leq y$ holds since $\tilde{\kappa}_a \in (0, \hat{\kappa}_a]$ holds from its posterior distribution in (\ref{eq: cdfkappa}).
Hence, if $\hat{\kappa}_a < y$, then
\begin{equation}\label{eq: tmuy1}
  \tilde{\alpha}(t) \geq \frac{y}{y-\hat{\kappa}_a} \implies \tilde{\mu}_a \leq y.
\end{equation}
When $1 < \tilde{\alpha}(t) < \frac{y}{y-\hat{\kappa}_a}$,
\begin{equation}\label{eq: tk}
    \tilde{\mu}_a = \tilde{\kappa}_a \frac{\tilde{\alpha}_a}{\tilde{\alpha}_a-1} \leq y  \, \Leftrightarrow  \, \tilde{\kappa}_a \leq y \frac{\tilde{\alpha}_a-1}{\tilde{\alpha}_a} .
\end{equation}

Since $\tilde{\alpha}_a \leq 1$ implies $\tilde{\mu}_a = \infty$, from (\ref{eq: tmuy1}) and (\ref{eq: tk}), it holds that
\begin{align*}
    \mathbb{P}_t[\tilde{\mu}_a \leq y]& = \int_{1}^{\frac{y}{y - \hat{\kappa}_a}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathbb{P}_t\left[\tilde{\kappa}_a \leq \frac{x-1}{x}y\right] \mathrm{d} x + \int_{\frac{y}{y - \hat{\kappa}_a}}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x \\
    &= \int_{1}^{\frac{y}{y-\hat{\kappa}_a}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa}_a x} y \right)^{nx} \mathrm{d} x + \int_{\frac{y}{y-\hat{\kappa}_a}}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x, \numberthis{\label{eq: tmucase1}}
\end{align*}
where we denoted $\mathbb{P}_t[\cdot] = \mathbb{P}[\cdot | \mathcal{F}_t]$ and recovered the CDF in (\ref{eq: cdfkappa}) in (\ref{eq: tmucase1}).
Take any finite $y' > y$ and let $\xi := \frac{y'}{y'-\kappa_a}< \frac{y}{y-\kappa_a}$ such that $\mu((\kappa_a, \xi)))=y'$.
Since $\frac{a}{a-b}$ is decreasing with respect to $a > b >0$, one can see that
\begin{align*}
    \mathbb{P}_t[\tilde{\mu}_a \leq y] &= \int_{1}^{\frac{y}{y-\hat{\kappa}_a}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa}_a x} y \right)^{nx} \mathrm{d} x + \int_{\frac{y}{y-\hat{\kappa}_a}}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x \\
    &\leq \int_{1}^{\frac{y'}{y'-\hat{\kappa}_a}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa}_a x} y \right)^{nx} \mathrm{d} x + \int_{\frac{y'}{y'-\hat{\kappa}_a}}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x
    \\
    &\leq \int_{1}^{\frac{y'}{y'-\kappa}} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa}_a x} y \right)^{nx} \mathrm{d} x + \int_{\frac{y'}{y'-\kappa}}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x\\
    &\leq \int_{1}^{\xi} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \left( \frac{x-1}{\kappa x} y \right)^{n} \mathrm{d} x + \int_{\xi}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x\numberthis{\label{eq: star_5}}\\
    &\leq \left( \frac{\xi-1}{\kappa \xi} y\right)^{n} \int_{1}^{\xi} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{\xi}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x \numberthis{\label{eq: star_6}}\\
    &= \left( \frac{y}{\mu((\kappa, \xi))}\right)^{n} \int_{1}^{\xi} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{\xi}^{\infty} f_{n-k, \frac{n}{\alpha_{a,n}}}^{\text{Er}}(x) \mathrm{d} x,
\end{align*}
where (\ref{eq: star_5}) comes from $\hat{\kappa}_a \geq \kappa$ and we used the increasing property of $\frac{x-1}{x}$ in (\ref{eq: star_6}).
\end{proof}




\subsection{Proof of Lemma~\ref{lem: pn_cases}}

\lempn*

\begin{proof}
Similarly to other proofs, fix $t$ and let $N_1(t) =n$.
To simplify notations, we drop the argument $t$ of $\tilde{\kappa}_1(t), \tilde{\alpha}_1(t)$ and $\tilde{\mu}_1(t)$ and the argument $n$ of $\hat{\kappa}_1(n), \hat{\alpha}_1(n), \bar{\alpha}_1(n)$.

\paragraph{Case 1. On $\{\hat{\kappa}_1 \geq \mu_1 - \epsilon\}$}
Under the condition $\{\hat{\kappa}_1 \geq \mu_1 - \epsilon\}$, the event $\{ \tilde{\mu}_1 \leq \mu_1 - \epsilon \}$ is eventually determined by the value of $\tilde{\kappa}$ since $\{\tilde{\kappa}_1 \in (\mu_1 - \epsilon, \hat{\kappa}_1]\}$ is a sufficient condition to $\{\tilde{\mu}_1 > \mu_1 - \epsilon\}$.
Therefore, if $\hat{\kappa}_1 \geq \mu_1 - \epsilon$, then
\begin{equation*}
     p_n(\epsilon|{\theta}_{1,n}) = \int_{1}^{\infty} f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \left( \frac{\mu_1 - \epsilon}{\hat{\kappa}_1} \frac{x-1}{x}\right)^{nx} \mathrm{d} x.
\end{equation*}
Then, 
\begin{align*}
    \mathbbm{1}[\hat{\kappa}_1 \geq \mu_1 -  \epsilon]p_n(\epsilon|{\theta}_{1,n}) &=  \mathbbm{1}[\hat{\kappa}_1 \geq \mu_1 - \epsilon] \left( \int_{1}^{\infty} f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \left( \frac{\mu_1 -\epsilon}{\hat{\kappa}_1} \frac{x-1}{x}\right)^{nx} \mathrm{d} x \right) \\
    &\leq \mathbbm{1}[\hat{\kappa}_1 \geq \mu_1 - \epsilon]\int_{1}^{\infty} f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \left( 1- \frac{1}{x} \right)^{nx} \mathrm{d} x \\
    &  \leq \mathbbm{1}[\hat{\kappa}_1(n) \geq \mu_1 - \epsilon] \int_{1}^{\infty} f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x)   e^{-n} \mathrm{d} x   \\
    &\leq \mathbbm{1}[\hat{\kappa}_1(n) \geq \mu_1 - \epsilon] e^{-n},
\end{align*}
where the second inequality holds from $\mu_1 -\epsilon \leq \hat{\kappa}_1$.

\paragraph{Case 2. On $\{\hat{\kappa}_1 \in K(\epsilon), \alpha_{1,n} \leq \alpha_1 + \rho\}$}
By applying Lemma~\ref{lem: tmusmall} with $y=\mu_1 - \epsilon$, we have for any $\xi \leq \frac{\mu_1- \epsilon}{\mu_1 -\epsilon - \kappa_1}$ that
\begin{align*}
    \mathbbm{1}[\hat{\kappa}_1 < \mu_1 - \epsilon, \alpha_{1,n} \leq \alpha + \rho]p_n(\epsilon|{\theta}_{1,n}) &\leq \left( \frac{\mu_1 -\epsilon}{\mu((\kappa_1, \xi))} \right)^{n} \int_{1}^\xi f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x   + \int_{\xi}^\infty f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x \\
    &\leq \left( \frac{\mu_1 -\epsilon}{\mu((\kappa_1, \xi))} \right)^{n} \int_{0}^\xi f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x + \int_{\xi}^\infty f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x. \numberthis{\label{eq: L9case2_1}}
\end{align*}
Let us define $\bar{\rho} := \rho_{\theta}(\epsilon/2)$.
Then, it satisfies $\mu((\kappa_1, \alpha_1+\bar{\rho})) = \mu_1 - \frac{\epsilon}{4}$ and
\begin{equation*}
    \alpha_1 + \bar{\rho} = \frac{\mu -\epsilon/4}{\mu -\epsilon/4 -\kappa_1} < \frac{\mu -\epsilon}{\mu -\epsilon -\kappa_1},
\end{equation*}
where the inequality holds from the decreasing property of the function $\frac{x}{x-y}$ with respect to $x>y$.
By replacing $\xi$ with $\alpha_1 + \bar{\rho}$ in (\ref{eq: L9case2_1}), we have
\begin{align*}
  \mathbbm{1}[\hat{\kappa}_1 &< \mu_1 - \epsilon, \alpha_{1,n} \leq \alpha_1 + \rho]p_n(\epsilon|\bar{\theta}_{1,n}) \\ 
  &\leq \mathbbm{1}[\hat{\kappa}_1 < \mu_1 - \epsilon, \alpha_{1,n} \leq \alpha_1 + \rho] \bigg( \left( \frac{\mu_1 - \epsilon}{\mu_1 -\epsilon/4} \right)^n  \int_{0}^\xi f_{n-k, \frac{n}{\alpha_{1,n}}}^{\text{Er}}(x) \mathrm{d} x
    + \int_{\alpha_1 + \bar{\rho}}^\infty f_{n-k, \frac{n}{\alpha_{1,n}(n)}}^{\text{Er}}(x) \mathrm{d} x \bigg) \\
    &\leq \mathbbm{1}[\hat{\kappa}_1 < \mu_1 - \epsilon, \alpha_{1,n} \leq \alpha_1 + \rho] \bigg(e^{-n \left( \frac{3\epsilon}{4\mu_1 -\epsilon} \right)} \left( 1- \mathbb{P}[\tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}]\right)
    + \mathbb{P}[\tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}] \bigg).
    \numberthis{\label{eq: case21}}
\end{align*}

Let $Z_n$ be a random variable that follows the chi-squared distribution with $n$ degree of freedom and $F_n(\cdot)$ denote the CDF of $Z_n$.
Then, it holds that
\begin{align*}
  \mathbb{P}\bigg[ \tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}, \alpha_{1,n} \leq \alpha_1 + \rho \bigg]  &=\mathbb{P}\left[ Z \geq \frac{2n}{\alpha_{1,n}}(\alpha_1 + \bar{\rho}), \alpha_{1,n} \leq \alpha_1 + \rho \right]  \hspace{1em}\text{by Fact~\ref{fact1}}
    \\
    & 
    \leq \mathbb{P}\left[ Z \geq 2n \frac{\alpha_1 + \bar{\rho}}{\alpha_1 + \rho} \right]
    \\ 
    &\leq \mathbb{P}\left[ Z \geq  2n \frac{\mu_1 - \epsilon/4}{\mu_1 - \epsilon/2} \right] \\
    &= 1 - F_{2n-2k}(2n(1+\zeta)), \numberthis{\label{eq: Fchi}}
\end{align*}
where $\zeta = \frac{\epsilon}{4\mu_1 - 2\epsilon} \in (0, 1)$.
By applying Lemma~\ref{lem: wallace}, we have if $n\zeta > -k$,
\begin{align*}
    \mathbb{P}[\tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}, \alpha_{1,n} \leq \alpha_1 + \rho] \hspace{-4em}& \\
    &\leq 1-F_{2n-2k}\left( 2n (1+\zeta) \right) 
    \\ &< \frac{1}{2}\frac{\sqrt{2\pi} (n-k)^{n-k-1/2}e^{-(n-k)}}{\Gamma(n-k)} \mathrm{erfc}\left(\sqrt{n(\zeta+k)-(n-k)\log \frac{n(1+\zeta)}{n-k}} \right),
\end{align*}
where $\Gamma(\cdot)$ denotes the Gamma function.
For $n \geq 1/2$, it holds from Stirling's formula that
\begin{equation*}
    \sqrt{2\pi}n^{n-1/2}e^{-n} \leq \Gamma(n) \leq \sqrt{2\pi}e^{1/6}n^{n-1/2}e^{-n},
\end{equation*}
which results in
\begin{equation}\label{eq: erfcineq}
  \mathbb{P}[\tilde{\alpha}_1\geq \alpha_1 + \bar{\rho}, \alpha_{1,n} \leq \alpha_1 + \rho]
    <  \frac{1}{2}\mathrm{erfc}\left(\sqrt{n(\zeta+k)-(n-k)\log \frac{n(1+\zeta)}{n-k}} \right).
\end{equation}
Notice that $(n-k)\log \frac{n(1+\zeta)}{n-k} >0$ always holds from the assumption of $n\zeta> -k$ where priors with $k \in \mathbb{Z}_{\geq 0}$ satisfies regardless of $n$.
Thus, if $\zeta + k \leq 0$, then the argument in the complementary error function in (\ref{eq: erfcineq}) becomes negative.
This makes the upper bound in (\ref{eq: erfcineq}) greater than or equal to $\frac{1}{2}$.
Therefore, for the priors with $k \in \mathbb{Z}_{<0}$, the right term in (\ref{eq: erfcineq}) is bounded by a constant since $\zeta \in (0,1)$.

Since the complementary error function is a decreasing function, for priors with $k\in \mathbb{Z}_{\geq 0}$, it holds from (\ref{eq: erfcineq}) that 
\begin{equation*}
    \mathbb{P}[\tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}, \alpha_{1,n} \leq \alpha_1 + \rho]
  \leq \frac{1}{2}\mathrm{erfc}\left(\sqrt{n( \zeta - \log (1+\zeta)} \right),
\end{equation*}
where we substitute $k=0$.
By the change of variables, the complementary error function is bounded for any $x \geq 0$ as follows~\citep{simon1998erfc}:
\begin{equation*
    \mathrm{erfc}(x) \leq e^{-x^2},
\end{equation*}
which implies
\begin{equation}\label{eq: case2}
  \mathbb{P}[\tilde{\alpha}_1 \geq \alpha_1 + \bar{\rho}, \alpha_{1,n} \leq \alpha_1 + \rho]\leq \frac{1}{2} e^{-nc_{\mu_1}(\epsilon)},
\end{equation}
where $c_{\mu_1}(\epsilon) = \zeta - \log(1+\zeta) >0$ is a deterministic constants on $\mu_1$ and $\epsilon$.
By combining (\ref{eq: case2}) with (\ref{eq: case21}), we have
\begin{equation*}
     \mathbbm{1}[\hat{\kappa}_1 < \mu_1 - \epsilon, \alpha_{1,n} \leq \alpha_1 + \rho]p_n(\epsilon|{\theta}_{1,n}) \leq e^{-n \frac{3\epsilon}{4\mu_1}} \left( 1- \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)} \right) + \frac{1}{2}e^{-nc_{\mu_1}(\epsilon)} =: h(\mu_1, \epsilon, n).
\end{equation*}

From the power-series expansion of $\log(1+x)$, we have $\log(1+x) \geq x - \frac{x^2}{2} + \frac{x^3}{3}$ for $x \in (0,1)$ and 
\begin{align*}
    c_{\mu_1}(\epsilon) = \zeta - \log(1+\zeta) \leq \frac{\zeta^2}{2} - \frac{\zeta^3}{3} &= \frac{\zeta^2}{6}(3-2\zeta) \\
    &\leq \frac{\zeta^2}{2} = \mathcal{O}(\epsilon^{-2}).
\end{align*}

\paragraph{Case 3. On $\{ \hat{\kappa}_1 \in K(\epsilon), \alpha_{1,n} \geq \alpha_1 + \rho \}$}
By applying Lemma~\ref{lem: tmusmall} with $y=\mu_1 - \epsilon$ and $\xi = \alpha_1 + \rho$, we have
\begin{align*}
      \mathbbm{1}[\hat{\kappa}_1 < \mu_1 - \epsilon] p_n(\epsilon | {\theta}_{1,n}) &\leq
      \bigg( \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon/2} \bigg)^{n} \int_1^{\alpha_1 + \rho}  f_{n-k, \frac{n}{\alpha_{1,n}}}^{\mathrm{Er}}(x) \mathrm{d} x + \int_{\alpha_1 + \rho}^\infty  f_{n-k, \frac{n}{\alpha_{1,n}}}^{\mathrm{Er}}(x)  \mathrm{d} x  \\
      &=
        C_1(\mu_1,\epsilon, n) \mathbb{P}\left[\tilde{\alpha}_1 \in [1, \alpha_1+ \rho] \mid \alpha_{1,n}\right] + \mathbb{P}\left[\tilde{\alpha}_1 \geq  \alpha_1 + \rho \mid \alpha_{1,n} \right]\\
      &\leq  C_1(\mu_1,\epsilon, n) \mathbb{P}\left[\tilde{\alpha}_1 \leq \alpha_1 + \rho \mid \alpha_{1,n}\right] + \mathbb{P}\left[\tilde{\alpha}_1 \geq  \alpha_1  + \rho \mid \alpha_{1,n} \right] \\
      &=  C_1(\mu_1,\epsilon, n)G_k(1/\alpha_{1,n};n) + (1-G_k(1/\alpha_{1,n};n)),  \numberthis{\label{eq: pnKeps}}
\end{align*}
where $A_n = C_1(\mu_1,\epsilon, n) := \left( \frac{\mu_1 - \epsilon}{\mu_1 - \epsilon/2} \right)^{n} \leq e^{-n \frac{\epsilon}{2\mu_1 - \epsilon}} < 1$.
Since $\tilde{\alpha}_1$ follows $\mathrm{Erlang}\left(n-k, \frac{n}{\alpha_{1,n}} \right)$, it holds that
\begin{align*}
    \mathbb{P}\left[\tilde{\alpha}_1 \leq \alpha_1 + \rho \mid \alpha_{1,n}\right]= \frac{\gamma\left(n-k, \frac{n(\alpha_1+\rho)}{\alpha_{1,n}}\right) }{\Gamma(n-k)},
\end{align*}
where $\gamma(\cdot, \cdot)$ denotes the lower incomplete gamma function.
Therefore, letting 
\begin{equation*}
    G_k(x;n) := \frac{\gamma\left(n-k, n(\alpha_1+\rho)x \right) }{\Gamma(n-k)}
\end{equation*}
concludes the proof.
\end{proof}





\section{Proof of Theorem~\ref{thm: RegSubOopt}}~\label{sec: SubOpt}
As shown in proofs of Theorem~\ref{thm: RegOpt}, the integral term in (\ref{eq: integral}) diverges for $k \in \mathbb{Z}_{\leq 1}$ without the restriction on $\hat{\alpha}$.
In this section, we provide the partial proof of Theorem~\ref{thm: RegSubOopt} for $k\in \mathbb{Z}_{\leq 0}$, which shows the necessity of such requirement to achieve asymptotic optimality.
\begin{proof}[Proof of Theorem~\ref{thm: RegSubOopt}]
We consider a two-armed bandit problem with $\theta_1 = (\kappa, \alpha_1)$ and $\theta_2 = (\kappa, \alpha_2)$.
Let $\gamma = \max\{ \lceil\alpha_2  \rceil, \lfloor\alpha_2\rfloor +1\}$ and $m = \frac{\gamma}{\gamma-1}$, so that $\frac{\mu_2}{m} = \kappa \frac{\alpha_2}{\alpha_2 -1} \frac{\gamma-1}{\gamma} > \kappa$.
Assume $1 < \alpha_1 <\alpha_2$ and $\tilde{\mu}_2(s) = \mu_2 = \kappa \frac{\alpha_2}{\alpha_2 -1}$ for all $s\in \mathbb{N}$.
Recall that $\mathrm{STS}$ starts from playing every arms twice for priors $k \leq 1$, i.e., $N_a(s) \geq 2$ holds for all $a \in \{1, 2\}$.
We have for $T \geq 5$
\begin{align*}
    \mathbb{E}[\mathrm{Reg}(T)] &= \Delta_2 \mathbb{E} \left [\sum_{t=1}^T \mathbbm{1} [j(t) = 2] \right] \\
    &\geq \Delta_2 \mathbb{E} \left[ \sum_{t=5}^T \mathbbm{1} [j(t)=2, N_1(t) = 2] \right].
\end{align*}
From the definition of $N_1(\cdot)$, $\{ j(s) \ne 2, N_1(s) =2 \}$ implies $N_1(t) > 2$ for $t > s$.
Therefore, for any $t\geq 5$,
\begin{align*}
    \{j(t) = 2, N_1(t) = 2 \} &\Leftrightarrow \{ \forall s \in [1, t-4] : j(s+4) = 2 \} \\
     &\Leftrightarrow \{ \forall s \in [1, t-4] :\tilde{\mu}_1(s+4) < \mu_2 \}.
\end{align*}
Let $T' = T - 4$, then we have
\begin{align*}
    \mathbb{E}\bigg[\sum_{t=5}^T \mathbbm{1}  [j(t)=2, N_1(t) = 2] \bigg] &=
    \mathbb{E}\left[  \sum_{t=5}^{T} \mathbbm{1} \left[\forall s \in [1, t-4] :\tilde{\mu}_1(s+4) < \mu_2 \right] \right]  \\
   
    &= \mathbb{E}\left[ \sum_{s=1}^{T'} \left(\mathbb{P}[\tilde{\mu}_1 \leq \mu_2 | \hat{\kappa}_1(2), \hat{\alpha}_1(2)]\right)^{s}  \right]. \numberthis{\label{eq: sublower}}
\end{align*}
Notice that $\hat{\kappa}_1(N_1(s))=\hat{\kappa}_1(2)$ and $\hat{\alpha}_1(N_1(s))=\hat{\alpha}_1(2)$ hold for all $s\geq 2$ since only $j(s)=2$ holds for all $s \geq 2$.
Here, we first provide the lower bound on $\mathbb{P}[\tilde{\mu}_1 \leq \mu_2 | \hat{\kappa}_1, \hat{\alpha}_1]$.
Since $\frac{\mu_2}{m} = \frac{\kappa \alpha_2}{\alpha_2 - 1} \frac{\gamma-1}{\gamma} > \kappa$ holds, we can consider the case where $\hat{\kappa}_1(2) \leq  \frac{\mu_2}{m}$ occurs.

From (\ref{eq: tmucase1}), it holds for $y \geq \hat{\kappa}_1(n)$ that
\begin{align*}
    \mathbb{P}_t[\tilde{\mu}_a \leq y] &= \int_{1}^{\frac{y}{y-\hat{\kappa}(n)}} f_{n-k, \frac{n}{\alpha_{n}}}^{\text{Er}}(x) \left( \frac{x-1}{\hat{\kappa} x} y \right)^{nx} \mathrm{d} x + \int_{\frac{y}{y-\hat{\kappa}(n)}}^{\infty} f_{n-k, \frac{n}{\alpha_{n}}}^{\text{Er}}(x) \mathrm{d} x \hspace{2em} \text{by (\ref{eq: tmucase1})}\\
    &\geq \int_{\frac{y}{y-\hat{\kappa}(n)}}^{\infty} f_{n-k, \frac{n}{\alpha_{n}}}^{\text{Er}}(x) \mathrm{d} x.
\end{align*}
By letting $n=2$ and $y=\mu_2$, we have for $k \in \mathbb{Z}_{\leq 1}$
\begin{align*}
    \mathbb{P}[\tilde{\mu}_1 \leq \mu_2 | \hat{\kappa}_1(2), \hat{\alpha}_1(2)] &\geq \mathbbm{1}\left[\hat{\kappa} \leq  \frac{\mu_2}{m}\right]\int_{\frac{\mu_2}{\mu_2 - \hat{\kappa}}}^\infty f_{2-k, \frac{2}{\hat{\alpha}}}^{\text{Er}}(x)  \mathrm{d} x \\
    &\geq \mathbbm{1}\left[\hat{\kappa} \leq  \frac{\mu_2}{m}\right] \int_{\gamma}^\infty f_{2-k, \frac{2}{\hat{\alpha}}}^{\text{Er}}(x)  \mathrm{d} x \numberthis{\label{eq: star_2}}\\
    &= \mathbbm{1}\left[\hat{\kappa} \leq  \frac{\mu_2}{m}\right] \frac{\Gamma(2-k, \frac{2\gamma}{\hat{\alpha}})}{\Gamma(2-k)},  \numberthis{\label{eq: gz}}
   
   
\end{align*}
where (\ref{eq: star_2}) holds from $\frac{\mu_2}{\mu_2 - \hat{\kappa}_1(2)} \leq \frac{\mu_2}{\mu_2 - \mu_2/m} = \frac{m}{m-1} = \gamma = \lceil \alpha_2 \rceil$
and $\Gamma(\cdot, \cdot)$ is the upper incomplete Gamma function.
To simplify the notations, we drop the arguments on $n$ and $t$ of $\tilde{\mu}_1(t)$, $\hat{\kappa}_1(n)$, and $\hat{\alpha}_1(n)$ in the following sections.

\subsection{Priors $k\in\mathbb{Z}_{\leq 0}$}
Note that $\Gamma(n, x)$ is an increasing function with respect to $n$ for fixed $x$.
Therefore, (\ref{eq: gz}) implies that if the lower bound of regret for the reference prior is larger than the lower bound, then every prior with $k\in\mathbb{Z}_{\leq 0}$ are suboptimal.
Therefore, let us consider the case $k=1$, where we can rewrite (\ref{eq: gz}) as
\begin{equation}\label{eq: gz0}
    \mathbb{P}[\tilde{\mu}_1 \leq \mu_2 | \hat{\kappa}_1, \hat{\alpha}_1]  \geq \mathbbm{1}\left[\hat{\kappa}_1 \leq  \frac{\mu_2}{m}\right] \frac{\Gamma(1, \frac{2\gamma}{\hat{\alpha}_1})}{\Gamma(1)} = e^{-\frac{2\gamma}{\hat{\alpha}_1}}.
\end{equation}
Since $\hat{\alpha}_1(2) \sim \mathrm{IG}(1, 2\alpha_1)$ in (\ref{eq: MLEdist}), $z := \frac{2\gamma}{\hat{\alpha}}$ follows an exponential distribution with rate parameter $\alpha_1/\gamma$, i.e., $z \sim \mathrm{Exp}(\alpha_1/\gamma)$.
By combining (\ref{eq: gz0}) with (\ref{eq: sublower}), we have
\begin{align*}
    \mathbb{E}\Bigg[  \sum_{t=5}^T \mathbbm{1} [j(t)=2, N_1(t) = 2] \Bigg]
    &\geq \mathbb{E}_{\hat{\kappa}, z}\left[\sum_{s=1}^{T'} \bigg( \mathbbm{1}[\hat{\kappa} \leq \mu_2/m]e^{-z} \bigg)^{s}  \right] \\
    &= \mathbb{P}[\hat{\kappa} \leq \mu_2/m]\mathbb{E}_{z\sim \mathrm{Exp}(\alpha_1/\gamma)}\left[ \sum_{s=1}^{T'} e^{-zs}  \right], \numberthis{\label{eq: gz0_1}}
\end{align*}
where we used the stochastic independence of $\hat{\alpha}$ and $\hat{\kappa}$.
Here,
\begin{align*}
    \mathbb{E}_{z\sim \mathrm{Exp}(\alpha_1/\gamma)}\left[ \sum_{s=1}^{T'} e^{-zs}  \right] &=  \mathbb{E}_{z\sim \mathrm{Exp}(\alpha_1/\gamma)}\left[ (1-e^{-zT'}) \frac{e^{-z}}{1-e^{-z}}  \right] \\
    &=  \int_{0}^{\infty} (1-e^{-xT'})\frac{e^{-x}}{1-e^{-x}} e^{-\frac{\alpha_1}{\gamma}x} \mathrm{d} x \\
    &\geq \int_{0}^{\infty} (1-e^{-xT'}) \frac{e^{-2x}}{1-e^{-x}} \mathrm{d} x \hspace{2em} \text{by } \frac{\alpha_1}{\gamma} < 1 \\
    &\geq \left(1 - \frac{1}{e} \right) \int_{\frac{1}{T'}}^{\infty} \frac{e^{-2x}}{1-e^{-x}} \mathrm{d} x  \\
    &= \left(1 - \frac{1}{e} \right) \left[ \log(e^{x}-1) - z + e^{-z} \right]_{x=\frac{1}{T'}}^{\infty} 
    \\
    &\geq \left(1 - \frac{1}{e} \right) \left ( \log T'+1-\frac{3}{2T'}\right), \numberthis{\label{eq: T3k0rslt}}
\end{align*}
where the last inequality holds from its power series expansion
\begin{align*}
     \log(e^{x}-1) - x + e^{-x} \geq \log(x) + 1 - \frac{3}{2}x
\end{align*}
and $\lim_{x\to \infty} \log(e^{x}-1) - x + e^{-x} =0$.
By combining (\ref{eq: T3k0rslt}) with (\ref{eq: gz0_1}) and (\ref{eq: sublower}) and elementary calculation with $\hat{\kappa}_1(2) \sim \mathrm{Pa}(\kappa_1, 2\alpha_1)$, we have
\begin{align*}
    \mathbb{E}[\mathrm{Reg}(T)] &\geq \Delta_2 \left( 1- \left(\frac{m\kappa}{\mu_2}\right)^{2\alpha_1} \right) \left( 1 - \frac{1}{e} \right)\left( \log T' + 1 -\frac{3}{2T'} \right) \\
    &= \Delta_2 \left( 1- \left(\frac{m\kappa}{\mu_2}\right)^{2\alpha_1} \right) \left( 1 - \frac{1}{e} \right) \left( \log (T+4) + 1 -\frac{3}{2(T+4)} \right).
\end{align*}
Therefore, under $\mathrm{STS}$ with $k \in \mathbb{Z}_{\leq 1}$, there exists a constant $C(\alpha_1, \alpha_2)$ such that
\begin{equation*}
    \liminf_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\log T} \geq C(\alpha_1, \alpha_2).
\end{equation*}

\subsection{Priors $k \in \mathbb{Z}_{\leq 0}$}
Similarly to the last section, it is sufficient to consider the case $k=0$, where we can rewrite (\ref{eq: gz}) as
\begin{equation}\label{eq: gz1}
    \mathbb{P}[\tilde{\mu}_1 \leq \mu_2 | \hat{\kappa}_1, \hat{\alpha}_1]  \geq \mathbbm{1}\left[\hat{\kappa}_1 \leq  \frac{\mu_2}{m}\right] \frac{\Gamma(2, \frac{2\gamma}{\hat{\alpha}_1})}{\Gamma(2)}.
\end{equation}
From the definition of the upper incomplete Gamma function, we have
\begin{equation*}
    g(z) := \Gamma(2, z) = \int_z^\infty x^1 e^{-x} \mathrm{d} x = e^{-z} (z + 1),
\end{equation*}
as a counterpart of $e^{-z}$ in (\ref{eq: gz0_1}) with the same notations $z = \frac{2\gamma}{\hat{\alpha}_1} \sim \mathrm{Exp}\left(\frac{\alpha_1}{\gamma}\right)$.

Therefore, by replacing $e^{-zs}$ in (\ref{eq: gz0_1}) with $g(z)^s$, we have
\begin{align*}
    \mathbb{E}_{z}\left[ \sum_{s=1}^{T'} (g(z))^s  \right] 
    &\geq \mathbb{E}_{z}\left[ \mathbbm{1}[z\in(0,1]] \sum_{s=1}^{T'} (g(z))^s  \right] \\
    &\geq \mathbb{E}_{z}\left[ \mathbbm{1}[z\in(0,1]] \sum_{s=1}^{T'} (1-z^2)^s  \right] \\
    &= \mathbb{E}_{z} \left[ \mathbbm{1}[z\in(0,1]] (1-(1-z^2)^{T'}) \frac{1-z^2}{z^2} \right],
\end{align*}
where we used the fact $z \in [0,1]$, $g(z) \geq 1-z^2$ in the second inequality.
Since $z \in \left(0, \frac{1}{\sqrt{T'}} \right]$, $(1-z^2)^{T'} \leq \frac{1}{1+T'z^2}$ holds, we have $1-(1-z^2)^{T'} \geq \frac{T'z^2}{1+T'z^2}$.

By applying this fact, we have for $T' > 1$,
\begin{align*}
  \mathbb{E}_{z}\Bigg[ \sum_{s=1}^{T'}  (g(z))^s  \Bigg] &\geq \mathbb{E}_{z} \left[ \frac{T'(1-z^2)}{1+T'z^2}  \mathbbm{1}\left[z\in\left(0,\frac{1}{\sqrt{T'}}\right]\right] \right] \\
    &\geq\mathbb{E}_{z\sim \mathrm{Exp}(\alpha_1/\gamma)} \left[  \left( \frac{T'}{2} - \frac{1}{2} \right) \mathbbm{1}\left[z\in\left(0,\frac{1}{\sqrt{T'}}\right]\right] \right] \hspace{3em} \\
    &= \left( \frac{T'}{2} - \frac{1}{2} \right) \int_0^{\frac{1}{\sqrt{T'}}}  \frac{\alpha_1}{\gamma}  e^{-\frac{\alpha_1}{\gamma}z} \mathrm{d} z \numberthis{\label{eq: star_4}} \\
    &= \left( \frac{T'}{2} - \frac{1}{2} \right) \left(1-e^{-\frac{\alpha_1}{\gamma\sqrt{T'}}}\right).
\end{align*}
Notice that $e^{-x} \leq 1 - \frac{x}{2}$ holds for $x < 1$, which gives
\begin{align*}
      \mathbb{E}_{z}\bigg[  \sum_{s=1}^{T'}  (g(z))^s  \bigg] &\geq \left( \frac{T'}{2} - \frac{1}{2} \right) \left(1-e^{-\frac{\alpha_1}{\gamma\sqrt{T'}}}\right) \\
      &\geq \left( \frac{T'}{2} - \frac{1}{2} \right) \frac{\alpha_1}{2\gamma\sqrt{T'}} = \frac{\alpha_1}{4\gamma}\left( \sqrt{T'} - \frac{1}{\sqrt{T'}} \right). \numberthis{\label{eq: suboptimalend}}
\end{align*}

By applying (\ref{eq: suboptimalend}) to (\ref{eq: sublower}), we obtain for $k \in \mathbb{Z}_{\leq 0}$ and $T' = T-4 > 1$, 
\begin{align*}
    \mathbb{E}[\mathrm{Reg}(T)] &\geq \Delta_2 \frac{\alpha_1}{4\gamma} \left( 1- \left(\frac{m\kappa}{\mu_2}\right)^{2\alpha_1} \right) \left( \sqrt{T'} - \frac{1}{\sqrt{T'}} \right) \\
   
    &= \mathcal{O}(\sqrt{T}).
\end{align*}
Notice that from the definition of $m = \frac{\gamma}{\gamma-1} = \frac{\ceil{\alpha_2}}{\ceil{\alpha_2}-1}$, $m \frac{\kappa}{\mu_2} = m\left( 1 - \frac{1}{\alpha_2}\right) < 1$ holds.
Therefore, under $\mathrm{STS}$ with priors $k \in \mathbb{Z}_{\leq 0}$, there exists a constant $C'(\alpha_1, \alpha_2) > 0$ such that
\begin{equation*}
    \liminf_{T \to \infty} \frac{\mathbb{E}[\mathrm{Reg}(T)]}{\sqrt{T}} \geq C'(\alpha_1, \alpha_2).
\end{equation*}
\end{proof}


\section{Priors and posteriors}\label{sec: bayesian}
In this section, we provide details on the problem of Jeffreys prior and the probability matching prior under the multiparameter models.
One can find more details from references in this section.
\subsection{Problems of the Jeffreys prior in the presence of nuisance parameters}
The Jeffreys prior was defined to be proportional to the square root of the determinant of the FI matrix so that it remains invariant under all one-to-one reparameterizations of parameters~\citep{jeffreys1998theory}.
However, the Jeffreys prior is known to suffer from many problems when the model contains nuisance parameters~\citep{datta1995some,ghosh2011objective}.
Therefore, Jeffreys himself recommended using other priors in the case of multiparameter models~\citep{berger1992development}.
For example, for the location-scale family, Jeffreys recommended using alternate priors, which coincide with the exact matching prior~\citep{diciccio2017simple}.

As mentioned in the main text, it is known that the Jeffreys prior leads to inconsistent estimators for the variance in the Neyman-Scott problem~\citep[see][Example 3.]{berger1992development}.
Another example is Stein's example~\citep{stein1959example}, where the model of the Gaussian distribution with a common variance is considered.
In this example, the Jeffreys prior lead to an unsatisfactory posterior distribution since the generalized Bayesian estimator under the Jeffreys prior is dominated by other estimators for the quadratic loss~\citep[see][Example 3.5.9.]{robert2007bayesian}.
Note that \citet{bernardo1979reference} showed that the reference prior does not suffer from such problems, which would explain why the reference prior shows better performance than the Jeffreys prior in the multiparameter bandit problems.

\subsection{Probability matching prior}
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~\citep{welch1963formulae, tibshirani1989noninformative}. 
Therefore, the posterior probability of certain intervals matches exactly or asymptotically the frequentist's coverage probability under the probability matching prior.
If the posterior probability of certain intervals exactly matches the confidence interval, such a prior is called an exact matching prior.
In cases where the Bayesian interval estimate does not exactly match the frequentist's coverage probability, but the difference is small, it is called a $k$-th order matching prior. The difference between the two probabilities is measured by a remainder term, usually denoted as $\mathcal{O}(n^{-\frac{k}{2}})$, where $n$ is the sample size and $k$ is the order of the matching\footnote{Some papers call a prior $k$-th order matching prior when a remainder is $\mathcal{O}\left(n^{-\frac{k+1}{2}}\right)$~\citep{diciccio2017simple}. In this paper, we follow notations used in \citet{mukerjee1997second} and \citet{datta2005probability}.}.

For example, let $\theta \in \mathbb{R}_{+}$ be a parameter of interest.
For some priors $\pi(\theta)$, let $\psi(\theta|X_n)$ be a posterior distribution after observing $n$ samples $X_n$.
Then, for any $\alpha \in (0,1)$, let us define $\theta_{\alpha} > 0$ such that
\begin{equation*}
    \int_{0}^{\theta_{\alpha}} \psi(\theta|X_n) \mathrm{d} \theta = \alpha.
\end{equation*}
When $\pi(\theta)$ is the second order probability matching prior, it holds that
\begin{equation*}
    \mathbb{P}[\theta \leq \theta_\alpha | X_n] = \alpha + \mathcal{O}(n^{-1}). 
\end{equation*}
When $\pi(\theta)$ is the exact probability matching prior, we have
\begin{equation*}
    \mathbb{P}[\theta \leq \theta_\alpha | X_n] = \alpha.
\end{equation*}
For more details, we refer readers to \citet{datta2005probability} and \citet{ghosh2011objective} and the references therein.

\subsection{Details on the derivation of posteriors}\label{sec: derivation_posterior}
In this section, we provide the detailed derivation of posteriors.

Let the observation $\bm{r} = (r_{1}, \ldots, r_{n})$ of an arm and let $q(n) = \sum_{s=1}^n \log r_s$.
Then, Bayes' theorem gives the posterior probability density as
\begin{align*}
    p({\kappa, \alpha} \mid\bm{r}) 
    =\frac{p(\bm{r}| {\kappa, \alpha}) p({\kappa, \alpha})}{\int_{0}^\infty \int_{0}^\infty p(\bm{r} \mid {\kappa, \alpha})p({\kappa, \alpha}) \mathrm{d} \kappa \mathrm{d} \alpha},
\end{align*}
where 
\begin{align*}
    p(\bm{r}\mid{\kappa, \alpha}) &= \alpha^n \kappa^{n\alpha}\left( \prod_{s=1}^n r_{a,s} \right)^{-\alpha-1} \mathbbm{1}[\kappa \leq \hat{\kappa}(n)] \\
    &= \alpha^n \kappa^{n\alpha} \exp(-q(n)(\alpha+1)) \mathbbm{1}[\kappa \leq \hat{\kappa}(n)].
\end{align*}
By direct computation with given prior with $k \in \mathbb{Z}$, we have
\begin{align*}
    \int_{0}^\infty \int_{0}^\infty p(\bm{r} \mid {\kappa, \alpha})p({\kappa, \alpha}) \mathrm{d} \kappa \mathrm{d} \alpha &= \int_{0}^\infty \int_{0}^\infty p(\bm{r} \mid {\kappa, \alpha}) \frac{\alpha^{-k}}{\kappa}\mathrm{d} \kappa \mathrm{d} \alpha \\
    &= \int_{0}^\infty  \alpha^{n-k} \exp(-q(n) (\alpha+1)) \int_{0}^{\hat{\kappa}} \kappa^{n\alpha -1}  \mathrm{d} \kappa \mathrm{d} \alpha \\
    &=  \int_{0}^\infty  \frac{\alpha^{n-k-1}}{n} e^{-q(n)} \exp(-\alpha(q(n) - n \log \hat{\kappa})) \mathrm{d} \alpha \\
    &= \frac{\Gamma(n-k)}{n}\frac{e^{-q(n)}}{(q(n) - n \log \hat{\kappa})^{n-k}}.
\end{align*}
Therefore, the joint posterior probability density is given as follows:
\begin{equation*}
    p({\kappa, \alpha} \mid \bm{r}) = \frac{n[q(n) - n\log \hat{\kappa}(n)]^{n-k}}{\Gamma(n-k)}\alpha^{n-k} \kappa^{n\alpha-1} e^{-q(n)\alpha} \mathbbm{1}[0<\kappa \leq \hat{\kappa}(n)],
\end{equation*}
which gives the marginal posterior of $\alpha$ as
\begin{equation} \label{eq: postak1}
    p(\alpha \mid \bm{r}) = \frac{\alpha^{n-k-1}[q(n) - n\log \hat{\kappa}(n)]^{n-k}}{\Gamma(n-k)} e^{-\alpha(q(n)-n\log \hat{\kappa}(n))}.
\end{equation}
Thus, sample $\tilde{\alpha}$ generated from the marginal posterior actually follows the Gamma distribution with shape $n-k$ and rate $q(n)-n\log \hat{\kappa}(n)= \frac{n}{\hat{\alpha}}$, i.e., $\tilde{\alpha} \sim \mathrm{Erlang}\left(n-k, \frac{n}{\hat{\alpha}} \right)$ as $n\in \mathbb{N}$ and $k \in \mathbb{Z}$ if $n > k$. 
When $\tilde{\alpha}$ is given, the conditional posterior of $\kappa$ is given as
\begin{align*}
  p(\kappa \mid \bm{r}, \alpha) 
    &= \frac{p({\kappa, \alpha} \mid \bm{r})}{p(\alpha \mid \bm{r})}
  \\&= \frac{n\alpha}{\hat{\kappa}^{n\alpha}} \kappa^{n\alpha -1} \mathbbm{1}[0<\kappa \leq \hat{\kappa}(n)]. \numberthis{\label{eq: pdfkappak1}}
\end{align*}
Hence, the cumulative distribution function (CDF) of $\kappa$ given $\alpha$ is given as
\begin{equation}\label{eq: cdfkappak1}
  \mathbb{P}(\kappa \leq x) = F(x \mid \bm{r}, \alpha=\tilde{\alpha}) = \left( \frac{x}{\hat{\kappa}(n)}\right)^{n\tilde{\alpha}}, \, 0 < x \leq \hat{\kappa}(n). 
\end{equation}
Note that MLEs of ${\kappa, \alpha}$ are equivalent to the maximum a posteriori (MAP) estimators when one uses the Jeffreys prior~\citep{Pareto_inference, Pareto_prior}.

In sum, under aforementioned priors, we consider the marginalized posterior distribution on $\alpha$
\begin{equation*}
    p(\alpha \mid \bm{r}) = \mathrm{Erlang}\left(n-k, \frac{n}{\hat{\alpha}}\right)
\end{equation*}
and the cumulative distribution function (CDF) of the conditional posterior of $\kappa$
\begin{equation*}
  F(x \mid \bm{r}, \alpha=\tilde{\alpha}) = \left( \frac{x}{\hat{\alpha}(n)}\right)^{n\tilde{\alpha}}, \, 0 < x \leq \hat{\kappa}(n).
\end{equation*}
Note that we require $\max\left\{2, k+1 \right\}$ initial plays to avoid improper posteriors and improper MLEs.



\section{Technical lemma}
In this section, we present some technical lemmas used in the proof of main lemmas.

\begin{restatable}{lemma}{lemCramer}~\label{lem: chicramer}
Let $Z$ be a random variable following the chi-squared distribution with the degree of freedom $2n$.
Then, for any $ x \in (0,1)$
\begin{equation*}
    \mathbb{P}[Z \leq 2nx] \leq e^{-n h(x)},
\end{equation*}
where $h(x) = (x-1 -\log x) \geq 0$.
\end{restatable}
\begin{proof}
Let $X_i$ be random variables following the standard normal distribution, so that $Z = \sum_{i=1}^{2n} X_i^2$ holds.
From Lemma~\ref{lem: cramer}, one can derive
\begin{equation*}
    \mathbb{P}[Z \leq 2nx] =  \mathbb{P}\left[ \frac{1}{2n}\sum_{i=1}^{2n} X_i^2 \leq x \right] \leq \exp{\left( - 2n\inf_{z \leq x} \Lambda^* (z) \right)}.
\end{equation*}
From the definition of the moment generating function, one can see that
\begin{equation*}
    \Lambda^*(z) = \sup_{\lambda \in \mathbb{R}} \lambda z - \log \mathbb{E}\left[e^{\lambda X_1^2} \right] = \sup_{\lambda \in \mathbb{R}} \lambda z + \frac{1}{2}\log (1-2\lambda) = \frac{1}{2}(z -1 -\log z),
\end{equation*}
which concludes the proof.
\end{proof}

\section{Known results}
In this section, we present some proved lemmas that we use without proofs.
\begin{lemma}[Bernstein's inequality]\label{lem: subexp}
Let $X$ be a $(\sigma^2, b)$-subexponential random variable with $\mathbb{E}[X]=\mu$ and $Var[X]=\sigma^2$, which satisfies
\begin{equation*}
    \mathbb{E}[e^{\lambda X}] \leq \exp{\frac{\lambda^2 \sigma^2}{2}} \quad \text{ for } |\lambda| \leq \frac{1}{b}.
\end{equation*}
Let $X_i$ be independent $(\sigma^2, b)$-subexponential.
Then, it holds that
\begin{equation*}
    \mathbb{P}\left( \abs{\frac{1}{n} \sum_{s=1}^n X_i - \mu} \geq t \right) \leq 2\exp \left( - \frac{n}{2}\min \left\{ \frac{t^2}{\sigma^2} , \frac{t}{b} \right\}\right). 
\end{equation*}
\end{lemma}
For more details, we refer the reader to \citet{vershynin2018high}.

\begin{lemma}[Theorem~4.1. in \citet{wallace1959}]\label{lem: wallace}
Let $F_n$ be the distribution function of the chi-squared distribution on $n$ degrees of freedom.
For all $t > n$, all $n>0$, and with $w(t) = \sqrt{t - n -n \log(t/n)}$,
\begin{equation*}
    1 - F_n(t) < \frac{d_n}{2} \mathrm{erfc}\left(\frac{w(t)}{\sqrt{2}}\right),
\end{equation*}
where $d_n = \frac{\left( \frac{n}{2} \right)^{\frac{n-1}{2}} e^{-\frac{n}{2}} \sqrt{2\pi} }{\Gamma(n/2)}$ and $\mathrm{erfc}(\cdot)$ is the complementary error function.
\end{lemma}

\begin{lemma}[Cram\'{e}r's theorem]\label{lem: cramer}
Let $X_1, \ldots, X_n$ be i.i.d. random variables on $\mathbb{R}$. Then, for any convex set $C \in \mathbb{R}$,
\begin{equation*}
    \mathbb{P}\left[\frac{1}{n}\sum_{i=1}^n X_i \in C\right] \leq \exp{\left( -n \inf_{z \in C} \Lambda^* (z) \right)},
\end{equation*}
where $\Lambda^*(z) = \sup_{\lambda \in \mathbb{R}} \lambda z - \log \mathbb{E}[e^{\lambda X_1}]$.
\end{lemma}

\begin{lemma}[Result of term (A) in \citet{KordaTS}]\label{lem: kordaresult}
When one uses the Jeffreys prior as a prior distribution under the Pareto distribution with known scale parameter, TS satisfies that for sufficiently small $\epsilon >0$,
\begin{equation*}
    \sum_{t=1}^T \mathbb{E}\left[\mathbbm{1}[j(t) \ne 1, \mathcal{M}_\epsilon^c(t)] \right] \leq \mathcal{O}\left(\epsilon^{-1}\right).
\end{equation*}
\end{lemma}

\section{Additional experimental results}\label{app: Exp}
\begin{figure*}[!t]
\centering
    \subfigure[The Jeffreys prior $k=0$]{\label{fig: ka0}\includegraphics[width=0.35\textwidth]{img/regret_4_compare_0_sqrt.pdf}}
    \quad
    \subfigure[The reference prior $k=1$]{\label{fig: ka1}\includegraphics[width=0.35\textwidth]{img/regret_4_compare_1_sqrt.pdf}}
    \medskip
    \subfigure[Prior with $k=3$]{\label{fig: ka3}\includegraphics[width=0.3\textwidth]{img/regret_4_compare_3_sqrt.pdf}}
    \hfill
    \subfigure[Prior with $k=-1$]{\label{fig: ka-1}\includegraphics[width=0.3\textwidth]{img/regret_4_compare_-1_sqrt.pdf}}
    \hfill
    \subfigure[Prior with $k=-3$]{\label{fig: ka-3}\includegraphics[width=0.3\textwidth]{img/regret_4_compare_-3_sqrt.pdf}}
\vspace{-1em}
\caption{The solid lines denotes an averaged regret over independent 100,000 runs. The shaded regions show a quarter standard deviation.}
\label{fig: all_k_sqrt}
\end{figure*}
From Figure~\ref{fig: all_k_sqrt}, one can observe that the performance difference between $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$ is large as $k$ decreases.
Since a truncation procedure aims to prevent an extreme case that can occur under $\mathrm{STS}$ with priors $k \in \mathbb{Z}_{\leq 1}$, it is quite natural to see that there is no difference between $\mathrm{STS}$ and $\mathrm{STS}\text{-}\mathrm{T}$ with prior $k=3$.
We can further see the improvement of $\mathrm{STS}\text{-}\mathrm{T}$ is dramatic as $k$ decreases, where an extreme case can easily occur.


\begin{figure*}[!t]
\centering
    \subfigure[Cumulative regret of $\mathrm{STS}$ with various $k$ under $\boldsymbol{\theta}_4'$]{\label{fig: STS2}\includegraphics[width=0.42\textwidth]{img/STS_4arm_50000_sqrt_log.pdf}}
    \quad
    \subfigure[Cumulative regret of $\mathrm{STS}\text{-}\mathrm{T}$ with various $k$ under $\boldsymbol{\theta}_4'$]{\label{fig: STST2}\includegraphics[width=0.42\textwidth]{img/STST_4arm_50000_sqrt_log.pdf}}
\caption{The solid lines denote the averaged cumulative regret over 100,000 independent runs of priors that can achieve the optimal lower bound in (\ref{eq: lowerbound}).
The dashed lines denote that of priors that cannot achieve the optimal lower bound in (\ref{eq: lowerbound}).
The green dotted line denotes the problem-dependent lower bound based on Lemma~\ref{lem: KLinf}.}
\label{fig: overall2}
\end{figure*}

\begin{figure*}[!ht]
\centering
    \subfigure[The Jeffreys prior $k=0$]{\label{fig: 2ka0}\includegraphics[width=0.35\textwidth]{img/2regret_4_compare_0_995.pdf}}
    \quad
    \subfigure[The reference prior $k=1$]{\label{fig: 2ka1}\includegraphics[width=0.35\textwidth]{img/2regret_4_compare_1_995.pdf}}
    \hfill
    \medskip
    \subfigure[Prior with $k=3$]{\label{fig: 2ka3}\includegraphics[width=0.32\textwidth]{img/2regret_4_compare_3_995.pdf}}
    \hfill
    \subfigure[Prior with $k=-1$]{\label{fig: 2ka-1}\includegraphics[width=0.32\textwidth]{img/2regret_4_compare_-1_995.pdf}}
    \hfill
    \subfigure[Prior with $k=-3$]{\label{fig: 2ka-3}\includegraphics[width=0.32\textwidth]{img/2regret_4_compare_-3_995.pdf}}
\caption{The solid lines denotes an averaged regret over independent 10,000 runs. The shaded regions and dashed lines show the central $99\%$ interval and the upper $0.05\%$ of regret, respectively.}
\label{fig: all_k_995}
\end{figure*}

We further consider another $4$-armed bandit problem $\boldsymbol{\theta}_4'$ where $\bm{\kappa}=(1.0, 1.5, 2.0, 2.0)$ and $\bm{\alpha} = (1.2, 1.5, 1.8, 2.0)$ where $\boldsymbol{\mu} = (5.0, 4.5, 4.5, 4.0)$.
$\boldsymbol{\theta}_4'$ would be a more challenging problem than $\boldsymbol{\theta}_4$ in the sense that the $\kappa$ determines the left boundary of the support, where larger $\kappa$ implies larger minimum value of the arm.
Therefore, if $\kappa$ of the suboptimal arm is larger than that of the optimal arm, it would make a problem difficult in the first few trials.
Figures~\ref{fig: overall2} and~\ref{fig: all_k_995} show the numerical results with time horizon $T=$ 50,000 and independent 10,000 runs.
Although $\mathrm{STS}$ with the reference prior shows similar performance to the conservative prior $k=3$, its performance varies a lot.

Figures~\ref{fig: 2ka0} and~\ref{fig: 2ka1} show the effectiveness of the truncation procedure where $\mathrm{STS}\text{-}\mathrm{T}$ has a much smaller upper $0.05\%$ regret than that of $\mathrm{STS}$. 
Although $k=-1$ also shows huge improvements in the central $99\%$ interval of regret as shown in Figure~\ref{fig: 2ka-1}, $\mathrm{STS}\text{-}\mathrm{T}$ with $k=-1$ shows worse performance compared with priors with $k\in \mathbb{Z}_{\geq 0}$ in Figure~\ref{fig: STST2}.