Thompson Sampling for 1-Dimensional Exponential Family Bandits

Introduction

An algorithm, $\phi$, for a $K$-armed bandit problem is a (possibly randomised) method for choosing which distribution to sample from next, given a history of previous arm choices and obtained rewards, $\mathcal{H}_{t-1}:=((a_{s},x_{s}))_{s=1}^{t-1}$: each reward $x_{s}$ is drawn from the distribution $p_{a_{s}}$. We denote by $\phi_{t}$ the distribution over $\{1,\dots,K\}$ induced by the history $\mathcal{H}_{t-1}$: at time $t$ the agent using $\phi$ picks arm $a$ with probability $\phi_{t}(a)$. The agent’s goal is to design an algorithm with low regret:

This quantity measures the expected performance of algorithm $\phi$ compared to the expected performance of an optimal algorithm given knowledge of the reward distributions, i.e. sampling always from the distribution with the highest expectation.

Since the early 2000s the “optimisim in the face of uncertainty” heuristic has been a popular approach to this problem, providing both simplicity of implementation and finite-time upper bound on the regret (e.g. ). However in the last two years there has been renewed interest in the Thompson Sampling heuristic (TS). While this heuristic was first put forward to solve bandit problems eighty years ago in , it was not until recently that theoretical analyses of its performance were achieved . In this paper we take a major step towards generalising these analyses to the same level of generality already achieved for “optimistic” algorithms.

Unlike optimistic algorithm which are often based on confidence intervals, the Thompson Sampling algorithm $\phi^{TS,\pi_{0}}$ uses Bayesian tools and puts a prior distribution $\pi_{a,0}=\pi_{0}$ on each $\theta_{a}$. A posterior distribution, $\pi_{a,t}$, is then maintained according to the rewards observed in $\mathcal{H}_{t-1}$. At each time a sample $\theta_{a,t}$ is drawn from each posterior $\pi_{a,t}$ and then the algorithm chooses to sample $a_{t}=\arg\max_{a\in\{1,\dots,K\}}\{\mu(\theta_{a,t})\}$. Therefore $\phi^{TS,\pi_{0}}_{t}(a)$ is the posterior probability that $a=a^{*}$ given the history $\mathcal{H}_{t-1}$.

Our Contributions

TS has proved to have impressive empirical performances, very close to those of state of the art algorithms such as DMED and KL-UCB . Furthermore recent works have shown that in the special case where each $p_{a}$ is a Bernoulli distribution $\mathcal{B}(\theta_{a})$, TS using a uniform prior over the arms is asymptotically optimal in the sense that it achieves the asymptotic lower bound on the regret provided by Lai and Robbins in (that holds for univariate parametric bandits). In this paper, we show this optimality property also holds for $1$-dimensional exponential families if the algorithm uses the Jeffrey’s prior:

Suppose that the rewards distributions belong to a $1$-dimensional canonical exponential family and that $\pi_{J}$ is the Jeffrey’s prior. Then,

where $\text{K}(\theta,\theta^{\prime}):=\text{KL}(p_{\theta},p_{\theta}^{\prime})$ is the Kullback-Leibler divergence between $p_{\theta}$ and $p_{\theta}^{\prime}$.

This theorem follows directly from Theorem 2. In the proof of this result we provide in Theorem 4 a finite-time, exponential concentration bound for posterior distributions of exponential family random variables, something that to the best of our knowledge is new to the literature and of interest in its own right. Our proof also exploits the explicit connection between the Jeffreys prior, Fisher information and the Kullback-Leibler divergence in exponential families.

Related Work

Another line of recent work has focused on distribution-independent bounds for Thompson Sampling. establishes that $\mathcal{R}(\phi^{TS,\pi_{U}},T)=O(\sqrt{KT\ln(T)})$ for Thompson Sampling for bounded rewards (with the classic uniform prior on the underlying Bernoulli parameter). go beyond the Bernoulli model, and give an upper bound on the Bayes risk (i.e. the regret averaged over the prior) independent of the prior distribution. For the parametric multi-armed bandit with $K$ arms described above, their result states that the regret of Thompson Sampling using a prior $\pi_{0}$ is not too big when averaged over this same prior:

Building on the same ideas, have improved this upper bound to $14\sqrt{KT}$. In our paper, we rather see the prior used by Thompson Sampling as a tool, and we want therefore to obtain garantees for any given problem parametrized by $\theta$.

also use Thompson Sampling in more general models, like the linear bandit model. Their result is a bound on the Bayes risk that does not depend on the prior, whereas Agrawal and Goyal give in a first regret bound for this model. Linear bandits consider a possibly infinite number of arms whose mean rewards are linearly related by a single, unknown coefficient vector. Once again, the analysis in encounters the problem of describing the concentration of posterior distributions. However by using a conjugate normal prior, they can employ explicit the concentration bounds available for Normal distributions to complete their argument.

Paper Structure

In Section 2 we describe important features of the one-dimensional canonical exponential families we consider, including closed-form expression for KL-divergences and the Jeffrey’s prior. Section 3 gives statements of the main results, and provides the proof of the regret bound. Section 4 proves the posterior concentration result used in the proof of the regret bound.

Exponential Families and Jeffreys Priors

A distribution is said to belong to a one-dimensional canonical exponential family if it has a density with respect to some reference measure $\nu$ of the form:

showing in particular that $F$ is strictly convex. The mean function $\mu$ is differentiable and stricly increasing, since we can show that

In particular, this shows that $\mu$ is one-to-one in $\theta$.

In an exponential family, a direct computation show that the Kullback-Leibler divergence can be expressed as a Bregman divergence of the normalisation function, F:

Jeffreys prior in Exponential Families

In the Bayesian literature, a special “non-informative” prior, one which is invariant under re-parametrisation of the parameter space, is sometimes considered. It is called the Jeffrey’s prior, and it can be shown to be proportional to the square-root of the Fisher information $I(\theta)$. In the special case of the canonical exponential family, the Fisher information takes the form $I(\theta)=F^{\prime\prime}(\theta)$, hence the Jeffrey’s prior for the model (2) is

Under the Jeffrey’s prior, the posterior on $\theta$ after $n$ observations is given by

When $\int_{\Theta}\sqrt{F^{\prime\prime}(\theta)}d\theta<+\infty$, the prior is called proper. However, stasticians often use priors which are not proper: the prior is called improper if $\int_{\Theta}\sqrt{F^{\prime\prime}(\theta)}d\theta=+\infty$ and any observation makes the corresponding posterior (4) integrable.

Some Intuition for choosing the Jeffreys Prior

In the proof of our concentration result for posterior distributions (Theorem 4) it will be crucial to lower bound the prior probability of an $\epsilon$-sized KL-divergence ball around each of the parameters $\theta_{a}$. Since the Fisher information $F^{\prime\prime}(\theta)=\lim_{\theta^{\prime}\rightarrow\theta}K(\theta,\theta^{\prime})/|\theta-\theta^{\prime}|^{2}$, choosing a prior proportional to $F^{\prime\prime}(\theta)$ ensures that the prior measure of such balls are $\Omega(\sqrt{\epsilon})$.

Examples and Pseudocode

Algorithm 1 presents pseudocode for Thompson Sampling with the Jeffreys prior for distributions parametrized by their natural parameter $\theta$. But as the Jeffreys prior is invariant under reparametrization, if a distribution is parametrised by some parameter $\lambda\not\equiv\theta$, the algorithm can use the Jeffrey’s prior $\propto\sqrt{I(\lambda)}$ on $\lambda$, drawing samples from the posterior on $\lambda$. Note that the posterior sampling step (in bold) is always tractable using, for example, a Hastings-Metropolis algorithm.

Some examples of common exponential family models are given in Figure 1, together with the posterior distributions on the parameter $\lambda$ that is used by TS with Jeffreys prior. In addition to examples already studied in for which $T(x)=x$, we also give two examples of more general canonical exponential families, namely the Pareto distribution with known min value and unknown tail index $\lambda$, $\text{Pareto}(x_{m},\lambda)$, for which $T(x)=\log(x)$, and the Weibul distribution with known shape and unknown rate parameter, $\text{Weibull}(k,\lambda)$, for which $T(x)=x^{k}$. These last two distributions are not covered even by the work in , and belong to the family of heavy-tailed distributions.

For the Bernoulli model, one note futher that the use of the Jeffreys prior is not covered by the previous analyses. These analyses make an extensive use of the uniform prior, through the fact that the coefficient of the Beta posteriors they consider have to be integers.

Results and Proof of Regret Bound

An exponential family $K$-armed bandit is a $K$-armed bandit for which the reward distributions $p_{a}$ are known to be elements of an exponential family of distributions $\mathcal{P}(\Theta)$. We denote by $p_{\theta_{a}}$ the distribution of arm $a$ and its mean by $\mu_{a}=\mu(\theta_{a})$.

Assume that $\mu_{1}>\mu_{a}$ for all $a\neq 1$, and that $\pi_{a,0}$ is taken to be the Jeffrey’s prior over $\Theta$. Then for every $\epsilon>0$ there exists a constant $\mathcal{C}(\epsilon,\mathcal{P})$ depending on $\epsilon$ and on the problem $\mathcal{P}$ such that the regret of Thompson Sampling using the Jeffrey’s prior satisfies

We give here the main argument of the proof of the regret bound, which proceed by bounding the expected number of draws of any suboptimal arm. Along the way we shall state concentration results whose proofs are postponed to later sections.

Step 0: Notation

We denote by $y_{a,s}$ the $s$-th observation of arm $a$ and by $N_{a,t}$ the number of times arm $a$ is chosen up to time $t$. $(y_{a,s})_{s\geq 1}$ is i.i.d. with distribution $p_{\theta_{a}}$. Let $Y_{a}^{u}:=(y_{a,s})_{1\leq s\leq u}$ be the vector of first $u$ observations from arm $a$. $Y_{a,t}:=Y_{a}^{N_{a,t}}$ is therefore the vector of observations from arm $a$ available at the beginning of round $t$. Recall that $\pi_{a,t}$, respectively $\pi_{a,0}$, is the posterior, respectively the prior, on $\theta_{a}$ at round $t$ of the algorithm.

For all $a\neq 1$ and $\Delta_{a}$ such that $\mu_{a}<\mu_{a}+\Delta_{a}<\mu_{1}$, we introduce

Step 1: Concentration Results

We state here the two concentration results that are necessary to evaluate the probability of the above events.

Let $(y_{s})$ be an i.i.d sequence of distribution $p(\cdot\mid\theta)$ and $\delta>0$. Then

The two following inequalities that will be useful in the sequel can easily be deduced from Lemma 3. Their proof is gathered in Appendix A with that of Lemma 3. For any arm $a$,

The second result tells us that concentration of the empirical sufficient statistic around its mean implies concentration of the posterior distribution around the true parameter:

Let $\pi_{a,0}$ be the Jeffreys’ prior. There exists constants $C_{1,a}=C_{1}(F,\theta_{a})>0$, $C_{2,a}=C_{2}(F,\theta_{a},\Delta_{a})>0$, and $N(\theta_{a},F)$ s.t., $\forall N_{a,t}\geq N(\theta_{a},F)$,

whenever $\delta_{a}<1$ and $\Delta_{a}$ are such that $1-\delta_{a}C_{2,a}(\Delta_{a})>0$.

Step 2: Lower Bound the Number of Optimal Arm Plays with High Probability

The main difficulty adressed in previous regret analyses for Thompson Sampling is the control of the number of draws of the optimal arm. We provide this control in the form of Proposition 5 which is adapted from Proposition 1 in whose proof, an outline of which is given in Appendix D, explores in depth the randomised nature of Thompson Sampling. In particular, we show that the proof in can be significantly simplified, but at the expense of no longer being able to describe the constant $C_{b}$ explicitly:

For any $b\in(0,1)$ there exists a constant $C_{b}(\pi,\mu_{1},\mu_{2},K)<\infty$ such that

Step 3: Decomposition

The idea in this step is to decompose the probability of playing a suboptimal arm into principle and negligible components and control these components with the results from Steps 1 and 2:

The terms (B) and (C) are about concentration of the posterior on the suboptimal arm. An upper bound on term (C) is given in (6), whereas a bound on term (B) follows from Lemma 6 below. Although the proof of this lemma is standard, and bears a strong similarity to Lemma 3 of , we provide it in Appendix C for the sake of completeness.

For all actions $a$ and for all $\epsilon>0$, $\exists$ $N_{\epsilon}=N_{\epsilon}(\delta_{a},\Delta_{a},\theta_{a})>0$ such that

where $N_{\epsilon}=N_{\epsilon}(\delta_{a},\Delta_{a},\theta_{a})$ is the smallest integer such that for all $n\geq N_{\epsilon}$

and $N(\theta_{a},F)$ is the constant from Theorem 4.

When we have seen enough observations on the optimal arm, term (A) also becomes a result about the concentration of the posterior, but this time for the optimal arm:

For any $\Delta_{a}^{\prime}>0$, one can choose $\delta_{1}$ such that $1-\delta_{1}C_{1,1}>0$. Then, with $N=N(\mathcal{P})$ such that the function

is decreasing for $u\geq N$, $(B^{\prime})$ is bounded by

So far, we have shown that for any $\epsilon>0$ and for any choice of $\delta_{a}>0$ and $0<\Delta_{a}<\mu_{1}-\mu_{a}$ such that $1-\delta_{a}C_{2,a}>0$, there exists a constant $\mathcal{C}(\delta_{a},\Delta_{a},\epsilon,\mathcal{P})$ such that

The constant is of course increasing (dramatically) when $\delta_{a}$ goes to zero, $\Delta_{a}$ to $\mu_{1}-\mu_{a}$, or $\epsilon$ to zero. But one can choose $\Delta_{a}$ close enough to $\mu_{1}-\mu_{a}$ and $\delta_{a}$ small enough, such that

Posterior Concentration: Proof of Theorem 4

The argument rests on the following Lemma, whose proof can be found in Appendix B

Step 2: Upper bounding the numerator of (10)

We first note that on $\Theta_{\theta,\Delta}$ the leading term in the exponential is $K(\theta,\theta^{\prime})$. Indeed, from (3) we know that

which, by strict convexity of $F$, is strictly increasing in $|\theta-\theta^{\prime}|$ for any fixed $\theta$. Now since $\mu$ is one-to-one and continuous, $\Theta_{\theta,\Delta}^{c}$ is an interval whose interior contains $\theta$, and hence, on $\Theta_{\theta,\Delta}$,

So for $\delta$ such that $1-\delta C_{2}>0$ we can bound the numerator of (10) by:

where we have used that $\pi(\cdot|y_{s^{\prime}})$ is a probability distribution, and that, since $\mu$ is increasing, $\text{K}(\theta,\mu^{-1}(\mu+\Delta))=\inf_{\theta^{\prime}\in\Theta_{\theta,\Delta}}K(\theta,\theta^{\prime})$.

Step 3: Lower bounding the denominator of (10)

To lower bound the denominator, we reduce the integral on the whole space $\Theta$ to a KL-ball, and use the structure of the prior to lower bound the measure of that KL-ball under the posterior obtained with the well-chosen observation $y_{s^{\prime}}$. We introduce the following notation for KL balls: for any $x\in\Theta,\ \epsilon>0$, we define

We have $\frac{K(\theta,\theta^{\prime})}{(\theta-\theta^{\prime})^{2}}\rightarrow F^{\prime\prime}(\theta)\neq 0$ (since $F$ is strictly convex). Therefore, there exists $N_{1}(\theta,F)$ such that for $u\geq N_{1}(\theta,F)$, on $B_{\frac{1}{u^{2}}}(\theta)$,

Using this inequality we can then bound the denominator of (10) whenever $u\geq N_{1}(\theta,F)$ and $\delta<1$:

Finally we turn our attention to the quantity

Now since the KL divergence is convex in the second argument, we can write $B_{1/u}(\theta)=(a,b)$. So, from the convexity of $F$ we deduce that

As $p(y\mid\theta)\rightarrow 0$ as $y\rightarrow\pm\infty$, the set $\mathcal{C}(\theta)=\{y:p(y\mid\theta)\geq L(\theta)\}$ is compact. The map $y\mapsto\int_{\Theta}p(y|\theta^{\prime})\sqrt{F^{\prime\prime}(\theta^{\prime})}d\theta^{\prime}<\infty$ is continuous on the compact $\mathcal{C}(\theta)$. Thus, it follows that

is an upper bound on the denominator of (13).

Now by the continuity of $F^{\prime\prime}$, and the continuity of $(y,\theta)\mapsto p(y|\theta)$ in both coordinates, there exists an $N_{2}(\theta,F)$ such that for all $u\geq N_{2}(\theta,F)$

Finally, for $u\geq N_{2}(\theta,F)$, we have a lower bound on the numerator of (13):

Puting everything together, we get

that there exist constants $C_{2}=C_{2}(F,\theta,\Delta)$ and $N(\theta,F)=\max\{N_{1},N_{2}\}$ such that for every $\delta<1$ satisfying $1-\delta C_{2}>0$, and for every $u\geq N$, one has

Note that when the prior is proper we do not need to introduce the observation $y_{s^{\prime}}$, which significantly simplifies the argument. Indeed in this case, in (11) we can use $\pi_{0}$ in place of $\pi(\cdot|y_{s^{\prime}})$ which is already a probability distribution. In particular, the quantity (13) is replaced by $\pi_{0}\left(B_{1/u^{2}}(\theta)\right)$, and so the constants $L$ and $L^{\prime}$ are not needed.

Conclusions

We have shown that choosing to use the Jeffrey’s prior in Thompson Sampling leads to an asymptotically optimal algorithm for bandit models whose rewards belong to a $1$-dimensional canonical exponential family. The cornerstone of our proof is a finite time concentration bound for posterior distributions in exponential families, which, to the best of our knowledge, is new to the literature. With this result we built on previous analyses and avoided Bernoulli-specific arguments. Thompson Sampling with Jeffreys prior is now a provably competitive alternative to KL-UCB for exponential family bandits. Moreover our proof holds for slightly more general problems than those for which KL-UCB is provably optimal, including some heavy-tailed exponential family bandits.

Our arguments are potentially generalisable. Notably generalising to $n$-dimensional exponential family bandits requires only generalising Lemma 3 and Step 3 in the proof of Theorem 4. Our result is asymptotic, but the only stage where the constants are not explicitly derivable from knowledge of $F$, $T$, and $\theta_{0}$ is in Lemma 9. Future work will investigate these open problems. Another possible future direction lies the optimal choice of prior distribution. Our theoretical guarantees only hold for Jeffreys prior, but a careful examination of our proof shows that the important property is to have, for every $\theta_{a}$,

which could hold for prior distributions other than the Jeffreys prior.

References

Appendix A Concentration of the Sufficient Statistics: Proof of Lemma 3, and Inequalities (6) and (7)

The proof of Lemma 3 follows from the classical Cramér-Chenoff technique (see ). For any $\lambda>0$.

where we have used the Markov inequality, and where

Now we optimize in $\lambda$ by choosing $\lambda>0$ that maximizes

$f(\lambda)$ is differentiable in $\lambda$ and its minimum, $\lambda^{*}$, satisfies $f^{\prime}(\lambda^{*})=0$ i.e.

(Note that $\lambda^{*}>0$ since $F^{\prime}$ is increasing). Finally, we get

The same reasoning leads to the upper bound

where $\nu^{*}$ is such that $F^{\prime}(\theta-\nu^{*})=F^{\prime}(\theta)-\delta$. ∎

which gives inequality (6). To proof (7), we write:

Appendix B Extracting the KL-divergence: Proof of Lemma 7

where $\pi(\theta|y_{s^{\prime}})$ denotes the posterior distribution on $\theta$ after observation $y_{s^{\prime}}$ and

denotes the empirical KL-divergence obtained from the observations $Y_{s^{\prime}}^{u}=Y^{u}\setminus\{y_{s^{\prime}}\}$. Introducing

Indeed, for that for any $\theta,\theta^{\prime}\in\Theta$

Appendix C Proof of Lemma 6

From Theorem 4 we know that, for $N_{a,t}\geq N(\theta_{a},F)$,

Let $N_{\epsilon}=N_{\epsilon}(\delta_{a},\Delta_{a},\theta_{a})$ be the smallest integer such that for all $n\geq N_{\epsilon}$

we have that for all $t$ and $T$ such that $N_{a,t}-1\geq\max(L_{T},N_{\epsilon},N(\theta_{a},F)),$

Appendix D Controling the Number of Optimal Plays: Outline Proof of Proposition 5

The proof of this proposition is quite detailed, and essentially the same as the proof given for Proposition 1 in , which we will sometimes refer to. However, in generalising to the case of exponential family bandits we show how to avoid the need to explicity calculate posterior probabilities that lead to Lemma 4 in . While simplifying the proof we loose the ability to specify the constants explicitly, and so the analysis becomes asymptotic, but holds for every $b\in]0,1[$.

We introduce the interval $\mathcal{I}_{j}=\{\tau_{j},\tau_{j}+\lceil t^{1-b}-1\rceil\}$: on the event $\mathcal{E}_{j}$, $\mathcal{I}_{j}$ is included in $\{\tau_{j},\tau_{j+1}\}$ and no draw of arm 1 occurs on $\mathcal{I}$. We also introduce for each arm $a\neq 1$ $d_{a}:=\frac{\mu_{1}-\mu_{a}}{2}$.

The idea of the rest of the analysis is based on the following remark. If on a subinterval $\mathcal{I}\subseteq[\tau_{j},\tau_{j+1}[$ of size $f(t)$ arm 1 is not drawn and all the samples of the suboptimal arms fall below $\mu_{2}+d_{2}<\mu_{1}$, then for all $s\in\mathcal{I}$, $\mu(\theta_{1,s})\leq\mu_{2}+d_{2}$. On $\mathcal{I}$, the sequence $(\theta_{1,s})$ is i.i.d. with distribution $\pi_{1,\tau_{j}}$, and hence,

At this point, an asymptotic result, telling that the posterior on $\theta_{1}$ concentrates to a Dirac in $\theta_{1}$ (the Bernstein-Von-Mises theorem, see ) , leads to

There exists a constant $C=C(\pi_{0})<1$, such that for every (random) interval $\mathcal{I}$ included in $\mathcal{I}_{j}$ and for every positive function $f$, one has

For every $a\in A,\ \delta>0$, there exist constants $C_{a}=C_{a}(\mu_{a},\delta,F)$ and $N$ such that for $t\geq N$,

The rest of the proof proceeds by finding a subinterval of $\mathcal{I}_{j}$ on which all the samples of all the suboptimal arms indeed fall below the corresponding thresholds $\mu_{a}+d_{a}$. This is done exactly as in and we recall the main steps of the proof below. Before that, we need to introduce the notion of saturated, suboptimal action.

Let $t$ be fixed. For any $a\neq 1$, an action $a$ is said to be saturated at time $s$ if it has been chosen at least $C_{a}\ln(t)$ times, i.e. $N_{a,t}\geq C_{a}\ln(t)$. We shall say that it is unsaturated otherwise. Furthermore at any time we call a choice of an unsaturated, suboptimal action an interruption.

We want to study the process of saturation on the event $\mathcal{E}_{j}=\{\xi_{j}\geq t^{1-b}-1\}$. We start by decomposing the interval $\mathcal{I}_{j}=\{\tau_{j},\tau_{j}+\lceil t^{1-b}-1\rceil\}$ into $K$ subintervals:

Now for each interval $\mathcal{I}_{j,l}$, we introduce:

$\mathcal{F}_{j,l}$: the event that by the end of the interval $\mathcal{I}_{j,l}$ at least $l$ suboptimal actions are saturated;

$n_{j,l}$: the number of interruptions during this interval.

We use the following decomposition to bound the probability of the event $\mathcal{E}_{j}$:

Note that the quantities $\mathcal{E}_{j},\ \mathcal{I}_{j,l},\ \mathcal{F}_{j,l}$ and $n_{j,l}$ all depend on $t$, however we suppress this dependency for notational convenience. However, we keep in mind that we bound the different probabilities for $t\geq N$, so that Lemma 10 applies.

On the event $\mathcal{E}_{j}\cap\mathcal{F}_{j,K-1}$, only saturated suboptimal arms are drawn on the interval $\mathcal{I}_{j,K}$. Using Lemma 10, we get

for $0<C<1$ as in Lemma 9. The second last inequality comes from the fact that if arm 1 is not drawn, the sample $\theta_{1,s}$ must be smaller than some sample $\theta_{a,s}$ and therefore smaller than $\mu_{2}+d_{2}$.

A similar argument to that employed in Step 2 can be used in an induction to show that for all $2\leq l\leq K$, if $t$ is larger than some deterministic constant $N_{\mu_{1},\mu_{2},b}$ specified in the base case,

We refer the reader to for a precise description of the induction. For $l=K$ we then get

Step 4: Conclusion

Putting Steps 2 and 3 together we obtain that for $t\geq N_{0}:=\max(N,N_{\mu_{1},\mu_{2},b})$,