Multi-play Combinatorial Semi-Bandit Problem

## Abstract

Abstract In the combinatorial semi-bandit (CSB) problem, a player selects an action from a combinatorial action set and observes feedback from the base arms included in the action. While CSB is widely applicable to combinatorial optimization problems, its restriction to binary decision spaces excludes important cases involving non-negative integer flows or allocations, such as the optimal transport and knapsack problems.
To overcome this limitation, we propose the multi-play combinatorial semi-bandit (MP-CSB), where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round. We propose two algorithms for the MP-CSB.
One is a Thompson-sampling-based algorithm that is computationally feasible even when the action space is exponentially large with respect to the number of arms, and attains O ​ ( log ⁡ T ) O(\log T) distribution-dependent regret in the stochastic regime, where T T is the time horizon.
The other is a best-of-both-worlds algorithm, which achieves O ​ ( log ⁡ T ) O(\log T) variance-dependent regret in the stochastic regime and the worst-case 𝒪 ~ ​ ( T ) \tilde{\mathcal{O}}\left(\sqrt{T}\right) regret in the adversarial regime.
Moreover, its regret in adversarial one is data-dependent, adapting to the cumulative loss of the optimal action, the total quadratic variation, and the path-length of the loss sequence.
Finally, we numerically show that the proposed algorithms outperform existing methods in the CSB literature.

## 1 Introduction

The multi-armed bandit (MAB) problem is a fundamental framework to investigate online decision-making problems, where we study the tradeoff between *exploitation* and *exploration* problem [Auer et al., 2002, Audibert and Bubeck, 2009].
One of the most important subfields of MAB is the combinatorial bandit problem [Audibert et al., 2014, Cesa-Bianchi and Lugosi, 2012, Combes et al., 2015, Wang and Chen, 2018, Kveton et al., 2015, Chen et al., 2016b, Wang and Chen, 2017, Chen et al., 2016a, Wen et al., 2014], which has many practical applications such as the shortest path problem [Sniedovich, 2006], crowdsourcing [ul Hassan and Curry, 2016], matching [Gibbons, 1985], the spanning tree problem [Pettie and Ramachandran, 2002], recommender systems [Qin et al., 2014], and learning spectrum allocations [Gai et al., 2012].
In the combinatorial semi-bandit (CSB) problem, a player sequentially interacts with an unknown environment over $T$ rounds. At each round, the player selects a combinatorial action to play and observes the losses for each selected component.
The goal is to minimize (expected) cumulative regret, defined as the difference between the loss of the player’s actions and the loss of the optimal action.

The CSB problem has been widely applied to modeling combinatorial optimization problems under uncertainty.
However, its restriction to *binary* decision spaces limits its applicability to problems involving integer flows or allocations, such as the knapsack problem [Dantzig and Mazur, 2007], the optimal transport (OT) problem [Villani, 2008], and numerous others.
These problems require a more general action space where decisions can take *non-negative integer values*. In these problems, each element of an action often represents some quantity. For example, in the OT problem, each element of an action can be seen as the number of trucks used to transport goods. In real-world applications, it is reasonable to assume that each truck is equipped with sensors and that feedback can be obtained from each truck.

In this paper, we propose a novel framework, multi-play CSB (MP-CSB), where the set of actions is a subset of the non-integer vector space, and multiple losses can be observed from a single arm. MP-CSB can be seen as a natural generalization of the ordinary CSB problem.

We introduce two algorithms for MP-CSB.
First, we introduce the Generalized Combinatorial Thompson Sampling (GenCTS) algorithm that is computationally feasible even when the action set is exponentially large with respect to the number of arms. Even though this algorithm is a naive expansion of the CTS algorithm proposed by Wang and Chen [2018], our regret analysis shows that the GenCTS algorithm achieves $\mathcal{O}\left(\log T\right)$ distribution-dependent regret in the stochastic regime.
Then, we introduce a *best-of-both-worlds* (BOBW) algorithm named GenLBINFV (Generalized Logarithmic Barrier Implicit Normalized Forecaster considering Variances for semi-bandits), which achieves $\mathcal{O}\left(\log T\right)$ variance-dependent regret in the stochastic regime and $\tilde{\mathcal{O}}\left(\sqrt{T}\right)$ regret in the adversarial regime.
Moreover, its regret in adversarial one is data-dependent, adapting to the cumulative loss of the optimal action, the total quadratic variation, and the path-length of the loss sequence.

Finally, we show that our algorithms outperform existing methods in the ordinary CSB literature by conducting numerical experiments with synthetic data.

**Table 1: Regret upper bounds of algorithms for linear objectives. $\Delta_{\mathrm{LB},\mathrm{min}}$ and $\sigma_{\mathrm{LB}}$ are the minimum sub-optimality gap and maximum variance of the feedback loss, respectively. $c\left(\mathcal{A},\boldsymbol{\ell}\right)$ is a quantity that appears in the analysis of an asymptotic lower bound satisfying $\liminf\limits_{T\rightarrow\infty}\frac{\mathbb{E}\left[R_{T}\right]}{\log T}\geq\Omega\left(c\left(\mathcal{A},\boldsymbol{\ell}\right)\right)$. Other quantities are introduced in Section [2](https://arxiv.org/html/2509.09933v1#S2).**
| Reference | Stochastic | Adversarial | Complexity |
| --- | --- | --- | --- |
| Ito and Takemura [2023a] | $\mathcal{O}\left(\frac{d^{3}\sigma_{\mathrm{LB}}^{2}\log T}{\Delta_{\mathrm{LB},\mathrm{min}}}\right)$ | $\mathcal{O}\left(d^{2}\sqrt{Z\log T}\right)$ | $\mathrm{Exp}(d)$ |
| Ito and Takemura [2023b] | $\mathcal{O}\left(\frac{d^{2}}{\Delta_{\mathrm{LB},\mathrm{min}}}\log T\right)$ | $\mathcal{O}\left(d\sqrt{T\log T}\right)$ | $\mathrm{Exp}(d)$ |
| Lee et al. [2021] | $\mathcal{O}\left(c(\mathcal{A},\boldsymbol{\ell})\left(\log T\right)^{2}\right)$ | $\mathcal{O}\left(\sqrt{dT}\log T\right)$ | $\mathrm{Exp}(d)$ |
| CTS<br>[Wang and Chen, 2018] | $\mathcal{O}\left(\sum\limits_{i=1}^{d}b_{i}\frac{\log M}{\Delta_{i}}\log T\right)$ | - | $\mathrm{Poly}(\sum\limits_{i=1}^{d}b_{i})$ |
| LBINFV<br>[Tsuchiya et al., 2023] | $\mathcal{O}\left(\sum\limits_{i\in J^{*}}b_{i}\frac{M\sigma_{i}^{2}}{\Delta_{i}}\log T\right)$ | $\mathcal{O}\left(\sqrt{\sum\limits_{i=1}^{d}b_{i}Z\log T}\right)$ | $\mathrm{Poly}(\sum\limits_{i=1}^{d}b_{i})$ |
| GenCTS | $\mathcal{O}\left(\sum\limits_{i=1}^{d}\frac{\log m}{\Delta_{i}}\log T\right)$ | - | $\mathrm{Poly}(d)$ |
| GenLBINFV | $\mathcal{O}\left(\sum\limits_{i\in J^{*}}\frac{M\sigma_{i}^{2}}{\Delta_{i}}\log T\right)$ | $\mathcal{O}\left(\sqrt{\sum\limits_{i=1}^{d}n^{2}_{i}Z\log T}\right)$ | $\mathrm{Poly}(d)$ |

## 2 Preliminaries

In this section, we formally define the MP-CSB problem and introduce the three regimes depending on how the loss is generated. Then, we show some typical applications of MP-CSB. Finally, we introduce existing works that are related to MP-CSB and discuss the optimality in MP-CSB.

### 2.1 Multi-Play Combinatorial Semi-Bandit (MP-CSB) Problem

Here, we formalize the MP-CSB problem. Suppose we have $d$ base arms, numbered $1,\ldots,d$. In each round $t\in[T]$, the environment sets a set of losses $\left\{L_{i,j}(t)\right\}_{j=1,\ldots,n_{i}}\subset[0,1]$ for each base arm $i$, where $n_{i}$ is the maximum number of samples the agent can obtain from base arm $i$ in one round.
Then, the player chooses an action $\boldsymbol{a}(t)$ from the action set $\mathcal{A}\subset\mathbb{Z}_{\geq 0}^{d}$, observes a set of losses, $\left\{L_{i,j}(t)\right\}_{j=1,\ldots,a_{i}(t)}$, for each $i$ where $a_{i}(t)\geq 1$, and incurs a loss of $f\left(\boldsymbol{a},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t)\right)$, where $f:\mathcal{A}\times\mathbb{R}^{n_{1}}\times\cdots\mathbb{R}^{n_{d}}\rightarrow\mathbb{R}$ and $\boldsymbol{L}^{i}=\left(L_{i,1}(t),\ldots,L_{i,n_{i}}(t)\right)\in\mathbb{R}^{n_{i}}$.
The performance of the player is evaluated by regret $R_{T}$ defined as the difference between the cumulative losses of the player and the single optimal action $\boldsymbol{a}^{*}$ fixed in terms of the expected cumulative loss, i.e., $\boldsymbol{a}^{*}=\mathop{\rm arg~min}\limits_{\boldsymbol{a}\in\mathcal{A}}\mathbb{E}\left[\sum_{t=1}^{T}f\left(\boldsymbol{a},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t)\right)\right]$
and

$$ $\displaystyle R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{a}(t),\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t))-f(\boldsymbol{a}^{*},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t))\right)\right],$ $$

where the expectation is taken w.r.t. to the randomness of losses and the internal randomness of the algorithm.

We define $I_{\boldsymbol{a}}=\{i\in[d]\mid a_{i}\geq 1\}$, representing the set of indices of arms from which one or more samples are obtained. We define $J^{*}=[d]\setminus I_{\boldsymbol{a}^{*}}$, $m=\max\limits_{\boldsymbol{a}\in\mathcal{A}}\left|I_{\boldsymbol{a}}\right|$, and $M=\max\limits_{\boldsymbol{a}\in\mathcal{A}}\left\|\boldsymbol{a}\right\|_{1}$. Note that $M\geq m$. Also, we define an action set dependent constant $\lambda_{\mathcal{A}}=\min\left\{M,W_{J^{*}}\right\}$, where $W_{J^{*}}=\sum_{i\in J^{*}}n_{i}$.
We assume that for all $i\in[d]$, there exists $\boldsymbol{a}\in\mathcal{A}$ such that $a_{i}\geq 1$.

### 2.2 Considered Regimes

We consider three regimes as the assumptions for the losses.

In the *stochastic regime*, the losses are generated by unknown but fixed distributions.
Before the game starts, the environment chooses an arbitrary distribution $\mathcal{D}_{i}$ for each base arm $i\in[d]$.
In each round $t$, for each $i\in[d]$, the environment samples a set of $n_{i}$ random variables, $\{L_{i,j}(t)\}_{j=1,\ldots,n_{i}}$, from $\mathcal{D}_{i}$.
We denote $\ell_{i}=\mathbb{E}_{\xi\sim\mathcal{D}_{i}}\left[\xi\right]$ and $\sigma_{i}^{2}\in[0,1/4]$ as the expected outcome and variance of base arm $i$, respectively.
Also, we assume that the expected loss of an action $\boldsymbol{a}\in\mathcal{A}$ only depends on the mean outcomes of base arms in $I_{\boldsymbol{a}}$. That is, there exists a function $r$ such that $\mathbb{E}[f(\boldsymbol{a},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t))]=r\left(\boldsymbol{a},\left\{\ell_{i}\right\}_{i\in[I_{\boldsymbol{a}}]}\right)$.

By contrast, in the *adversarial regime*, we do not assume any stochastic structure for the losses, and the losses can be chosen arbitrarily.
In this regime, for each $i\in[d]$ and $j\in[n_{i}]$, the environment can choose $L_{i,j}(t)$ depending on the past history until $(t-1)$-th round, i.e., $\{(\boldsymbol{L}^{1}(s),\ldots,\boldsymbol{L}^{d}(s),\boldsymbol{a}(s))\}_{s=1}^{t-1}$.

We also consider the *stochastic regime with adversarial corruptions* [Ito, 2021, Zimmert and Seldin, 2021], which is an intermediate regime between the stochastic and adversarial regimes.
In this regime, for each $i\in[d]$, after a set of temporary loss $\left\{L^{\prime}_{i,j}(t)\right\}_{j=1,\ldots,n_{i}}$ is sampled from $\mathcal{D}_{i}$, the adversary corrupts $\{L^{\prime}_{i,j}(t)\}_{j=1,\ldots,n_{i}}$ to $\{L_{i,j}(t)\}_{j=1,\ldots,n_{i}}$.
We define the corruption level by $C=\mathbb{E}\left[\sum_{t=1}^{T}\max\limits_{i\in[d]}\max\limits_{j\in[n_{i}]}\left|L_{i,j}(t)-L^{\prime}_{i,j}(t)\right|\right]\geq 0$. If $C=0$, this regime coincides with the stochastic regime.

### 2.3 Typical Applications of MP-CSB

Here, we show typical applications where MP-CSB can be applied.

##### The Optimal Transport Problem.

The optimal transport (OT) problem [Villani, 2008] models resource allocation from $N_{\mathrm{sup}}$ suppliers to $N_{\mathrm{dem}}$ demanders. It is defined on a complete bipartite graph, where each supplier $x\in S:=\{1,\ldots,N_{\mathrm{sup}}\}$ has $u_{x}\in\mathbb{Z}_{\geq 0}$ trucks to deliver items, and each demander $y\in D:=\{1,\ldots,N_{\mathrm{dem}}\}$ requires $v_{y}\in\mathbb{Z}_{\geq 0}$ units of items. The goal is to find the most efficient transportation plan, minimizing the total transportation cost:

$$ $\displaystyle\begin{array}[]{ll@{}ll}\text{min.}&\sum\limits_{x=1}^{N_{\mathrm{sup}}}\sum\limits_{y=1}^{N_{\mathrm{dem}}}a_{xy}c_{xy}&\\ \text{s.t.}&\boldsymbol{a}\in\{\boldsymbol{\pi}\in\mathbb{Z}_{\geq 0}^{N_{\mathrm{sup}}\times N_{\mathrm{dem}}}\mid\boldsymbol{\pi}\mathbf{1}=\boldsymbol{u},\boldsymbol{\pi}^{\top}\mathbf{1}=\boldsymbol{v}\},&\end{array}$ (3) $$

where $a_{xy}$ represents the number of trucks transported from supplier $x$ to demander $y$, and $c_{xy}$ is the transportation cost of edge $(x,y)$.

In some scenarios, the transportation cost $c_{xy}$ is unknown and must be estimated. As a real-world application, each truck may have a sensor to measure the cost of edges it passes through, and feedback can be obtained from each truck. In such a case, we can apply the MP-CSB problem. Here, the number of arms $d$ is the number of edges in the bipartite graph, i.e., $d=N_{\mathrm{sup}}\times N_{\mathrm{dem}}$. Also, $n_{xy}$ is the maximum number of trucks that can pass through edge $(x,y)$, i.e., $n_{xy}=\min\left\{u_{x},v_{y}\right\}$.

##### The Knapsack Problem.

Next, we introduce an example of the knapsack problem [Dantzig and Mazur, 2007]. In the knapsack problem, we have $d$ items. Each item $i\in[d]$ has a weight $w_{i}$ and value $\mu_{i}$. Also, there is a knapsack whose capacity is $W$ in which we put items. Our goal is to maximize the total value of the items in the knapsack, not letting the total weight of the items exceed the capacity of the knapsack. Formally, the optimization problem is given as follows:

$$ $\displaystyle\begin{array}[]{ll@{}ll}\text{maximize}_{\boldsymbol{a}}&\boldsymbol{a}^{\top}\boldsymbol{\mu}&\\ \text{subject to}&\boldsymbol{a}^{\top}\boldsymbol{w}\leq W&\\ \text{and}&\boldsymbol{a}\in\mathbb{Z}_{\geq 0}^{d},&\end{array}$ $$

where $\boldsymbol{w}=\left(w_{1},\ldots,w_{d}\right)$.

Then, let us consider online advertising. Suppose an advertiser considers placing different types of ads in a frame of size $W$ on a website. The advertiser is allowed to place multiple ads of the same type. The size of each ad $i$ is $w_{i}$, and it is assumed that the total size of all ads must not exceed $W$.
As feedback to advertisers, they observe the profits generated from each ad.
In this example, we can apply the MP-CSB problem. The number of arms is the number of types of ads, and $n_{i}$ is the maximum number of ad $i$ that can be put in a website, i.e., $n_{i}=\left\lfloor\frac{W}{w_{i}}\right\rfloor$.

### 2.4 Related Works

In Table [1](https://arxiv.org/html/2509.09933v1#S1.T1), we show existing works that are related to MP-CSB.

The top three are state-of-the-art methods (SOTA) for the linear bandit (LB) [Ito and Takemura, 2023a, b, Lee et al., 2021], which studies best-of-both-worlds algorithms. In MP-CSB, if the objective is linear, i.e., $f\left(\boldsymbol{a},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t)\right)=\sum_{i=1}^{d}\sum_{j=1}^{a_{i}}L_{i,j}(t)$, we can apply these algorithms. However, there are several reasons why LB algorithms are not recommended for MP-CSB.
First, to apply LB algorithms, we need to enumerate all the actions in $\mathcal{A}$, which is unrealistic since the time complexity to enumerate them is exponential in $d$ in general. Secondly, since LB algorithms assume full-bandit feedback, in which the agent observes only the sum of rewards $\sum_{i=1}^{d}\sum_{j=1}^{a_{i}(t)}L_{i,j}(t)$, they are not able to take advantage of the benefit of obtaining multiple samples from a single arm.

The middle two are existing works that show SOTA methods proposed for the ordinary CSB. One may apply existing CSB algorithms to MP-CSB by *duplicating* base arms so that the action space becomes binary. However, this duplicating technique has two major shortcomings. First, duplicating base arms greatly increases the number of base arms, making it computationally infeasible to maintain statistics for each base arm (e.g., sample mean) in some cases.
For example, in the OT problem, the total number of duplicated arms is $\left(\sum\limits_{x=1}^{N_{\mathrm{sup}}}u_{x}\right)\times N_{\mathrm{dem}}$. If $\sum\limits_{x=1}^{N_{\mathrm{sup}}}u_{x}\sim\mathcal{O}\left(10^{10}\right)$, the computational burden of handling such a large number of base arms would be impractical.
The second issue is the sample efficiency in the stochastic regime. Even with the duplicating technique, existing algorithms maintain separate statistics on each base arm [Wang and Chen, 2018, Neu, 2015, Chen et al., 2021, Tsuchiya et al., 2023], even though all of the duplicated base arms follow the same distribution.
Such a lack of distinction between identical distributions leads to poor sample efficiency and may force the player to choose suboptimal actions frequently. See Appendix [A](https://arxiv.org/html/2509.09933v1#A1) for details.

### 2.5 Discussion on the Optimality

Next, we discuss lower bounds of MP-CSB for stochastic and adversarial regimes.
For the stochastic regime, if the objective is linear, i.e., $r\left(\boldsymbol{a},\left\{\ell_{i}\right\}_{i\in[I_{\boldsymbol{a}}]}\right)=\boldsymbol{a}^{\top}\boldsymbol{\ell}$, any consistent (^1^11 We say that an algorithm is consistent if for any stochastic CSB instance problem instance, any suboptimal $\boldsymbol{a}$, and any $0<\alpha<1$, $\mathbb{E}\left[T_{n}(\boldsymbol{a})\right]=o(n^{\alpha})$, where $T_{n}(\boldsymbol{a})$ is the number of times that action $\boldsymbol{a}$ is chosen in $n$ steps by the algorithm.) algorithm with the duplicating technique suffers a regret of $\Omega\left(\frac{\sum_{i=1}^{d}b_{i}M}{\Delta}\log T\right)$ asymptotically, where $\Delta=\min\limits_{\boldsymbol{a}\in\mathcal{A}\setminus\{\boldsymbol{a}^{*}\}}\boldsymbol{a}^{\top}\boldsymbol{\ell}-{\boldsymbol{a}^{*}}^{\top}\boldsymbol{\ell}$ and $b_{i}$ is the number of duplicates of arm $i$ [Kveton et al., 2015, Merlis and Mannor, 2020].
In Sections [3](https://arxiv.org/html/2509.09933v1#S3) and [4](https://arxiv.org/html/2509.09933v1#S4), we show that the upper bounds of our proposed algorithms are tighter than this lower bound.
We leave the derivation of a regret lower bound of consistent algorithms without using the duplicating technique in MP-CSB as a future work.

On the other hand, in the adversarial regime, since the adversary is setting $\sum_{i=1}^{d}n_{i}$ losses in total, from Audibert et al. [2014], we can directly obtain a worst case lower bound of MP-CSB of $\sqrt{M\left(\sum_{i=1}^{d}n_{i}\right)T}$.

## 3 Generalized CTS Algorithm

In this section, we introduce the generalized combinatorial Thompson sampling (GenCTS) algorithm, which is computationally feasible even when the action set $\mathcal{A}$ is exponentially large in $d$. We show that the GenCTS algorithm achieves $O(\log T)$ distribution-dependent regret in the stochastic regime.

##### Technical Assumptions.

To allow the GenCTS to handle not only linear loss functions but also a broader class of nonlinear loss functions, we assume that the function $r$ is Lipschitz continuous. Specifically, there exists a constant $\kappa_{r}$, such that for every action $\boldsymbol{a}$ and every pair of mean vectors $\boldsymbol{\mu}$ and $\boldsymbol{\mu}^{\prime}$, $\left|r\left(\boldsymbol{a},\left\{\mu_{i}\right\}_{i\in I_{\boldsymbol{a}}}\right)-r\left(\boldsymbol{a},\left\{\mu^{\prime}_{i}\right\}_{i\in I_{\boldsymbol{a}}}\right)\right|\leq\kappa_{r}\sum_{i\in I_{\boldsymbol{a}}}\left|\mu_{i}-\mu^{\prime}_{i}\right|$.
In the OT and knapsack problems, $r\left(\boldsymbol{a},\left\{\mu_{i}\right\}_{i\in[I_{\boldsymbol{a}}]}\right)=\sum_{i\in I_{\boldsymbol{a}}}a_{i}\mu_{i}$, and we can easily confirm that $\kappa_{r}=\max\limits_{i\in[d]}n_{i}$.

Also, GenCTS assumes that we have an *oracle* that takes a vector $\boldsymbol{\rho}=\left(\rho_{1},\ldots,\rho_{d}\right)$ as input and output an action $\mathrm{Oracle}(\boldsymbol{\rho})=\mathop{\rm arg~min}\limits\limits_{\boldsymbol{a}\in\mathcal{A}}r\left(\boldsymbol{a},\left\{\rho_{i}\right\}_{i\in I_{\boldsymbol{a}}}\right)$.
We assume that the time complexity of the oracle is polynomial or pseudo-polynomial (^2^22In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the *numeric value* of the input (the largest integer present in the input)—but not necessarily in the length (dimension) of the input, which is the case for polynomial time algorithms.) in $d$.
For instance, since it is known that the OT problem can be solved in $O(d^{3}\log d)$ time [Cuturi, 2013] using a linear programming solver, it can be the oracle. For the knapsack problem, there is a dynamic programming-based algorithm that runs in pseudo-polynomial time [Kellerer et al., 2004, Fujimoto, 2016], and therefore it can be the oracle.

##### Algorithm.

GenCTS is shown in Algorithm [1](https://arxiv.org/html/2509.09933v1#alg1).
Initially, we set a prior distribution of all the base arms as the beta distribution $\mathrm{Beta}(1,1)$, which is the uniform distribution on $[0,1]$. In each round $t$, we choose an action by drawing independent samples, $\{\theta_{i}(t)\}_{i\in[d]}$, from each base arm’s prior distribution, and use the output from the oracle, $\boldsymbol{a}(t)=\mathrm{Oracle}(\boldsymbol{\theta}(t))$, as the action to play.
After we obtain losses, we update the prior distributions of each base arm $i$ using the procedure Update (Algorithm [2](https://arxiv.org/html/2509.09933v1#alg2)).
In the Update procedure, we update the prior beta distribution of each base arm as follows.
For each $i\in I_{\boldsymbol{a}(t)}$ and $j\in[a_{i}(t)]$, we generate a Bernoulli random variable $Y_{i,j}(t)$ with mean $L_{i,j}(t)$, and update the prior beta distribution of base arm $i$ using $Y_{i,j}(t)$ as the new observation.
Let $p_{i}(t)$ and $q_{i}(t)$ denote the values of $p_{i}$ and $q_{i}$ at the beginning of round $t$, respectively. Here $p_{i}(t)-1$ and $q_{i}(t)-1$ represent the number of 1s and 0s in $\bigcup_{s=1}^{t-1}\bigcup_{j=1}^{a_{i}(s)}\{Y_{i,j}(s)\}$, respectively.
Then, following Bayes’ rule, the posterior distribution of arm $i$ after round $t$ is $\mathrm{Beta}\left(p_{i}(t)+\sum_{j=1}^{a_{i}(t)}Y_{i,j}(t),q_{i}(t)+\sum_{j=1}^{a_{i}(t)}(1-Y_{i,j}(t))\right)$, which is what the Update procedure does for $p_{i}$ and $q_{i}$.

One key advantage of the GenCTS algorithm is that it does not require enumerating all the possible actions in $\mathcal{A}$ in the beginning of the game. The total computation time of GenCTS is $O(\text{poly}(d)T)$ or $O(\text{pseudo-poly}(d)T)$.

Figure: Algorithm 1 GenCTS: Generalized Combinatorial Thompson Sampling

Figure: Algorithm 2 Procedure Update

Figure: Algorithm 3 Generalized LBINFV

##### Regret Analysis.

Here, we show a regret upper bound of the GenCTS algorithm.

###### Theorem 3.1 .

The GenCTS algorithm achieves $R_{T}=\mathcal{O}\left(\sum_{i=1}^{d}\frac{\kappa_{r}^{2}\log m}{\Delta_{i}}\log T\right)$, where $\Delta_{i}=\min\limits_{\boldsymbol{a}\in\mathcal{A}\setminus\{\boldsymbol{a}^{*}\}:a_{i}\geq 1}r\left(\boldsymbol{a},\left\{\ell_{i}\right\}_{i\in I_{\boldsymbol{a}}}\right)-r\left(\boldsymbol{a}^{*},\{\ell_{i}\}_{i\in I_{\boldsymbol{a}^{*}}}\right)$

We can see that the upper bound of GenCTS is tighter than the asymptotic lower bound of consistent algorithms with the duplicating technique, $\mathcal{O}\left(\frac{\sum_{i=1}^{d}b_{i}M}{\Delta}\log T\right)$, since $b_{i}\geq 1$ and $M\geq m$. From the result in Wang and Chen [2018], if we use the ordinary CTS algorithm with the duplicating technique for MP-CSB, the regret upper bound is $\mathcal{O}\left(\sum_{i=1}^{d}b_{i}\frac{\kappa_{r}^{2}\log M\log(T)}{\Delta_{\mathrm{i}}}\right)$. Therefore, we can see that the upper bound of GenCTS is tighter than that of the ordinary CTS algorithm with the duplicating technique.
Moreover, the time complexity of GenCTS in each round, $\mathcal{O}\left(\mathrm{Poly}(d)\right)$, can be smaller than that of CTS with the duplicating technique, which is $\mathcal{O}\left(\mathrm{Poly}\left(\sum_{i=1}^{d}b_{i}\right)\right)$. For instance, in the example of the OT problem, the time complexity of the ordinary CTS in each round is $\mathcal{O}((\sum_{i=1}^{d}b_{i})^{3}\log(\sum_{i=1}^{d}b_{i}))$, which can be much larger than that of GenLBINFV, which is $\mathcal{O}\left(d^{3}\log d\right)$.

###### Theorem 3.1 .

## 4 Generalized LBINFV Algorithm

In this section, we introduce the GenLBINFV algorithm, which is a BOBW algorithm for MP-CSB.

##### Technical Assumption for GenLBINFV.

For the GenLBINFV algorithm, we need an assumption that the loss function is linear, i.e., $f\left(\boldsymbol{a},\boldsymbol{L}^{1}(t),\ldots,\boldsymbol{L}^{d}(t)\right)=\sum_{i=1}^{d}\sum_{j=1}^{a_{i}}L_{i,j}(t)$.
This assumption holds for many combinatorial optimization problems with a linear objective, such as the OT and knapsack problems.

##### Algorithm.

We construct the algorithm based on the *optimistic-follow-the-regularized-leader* (OFTRL) framework, which has occasionally been used in the development of the BOBW algorithms [Wei and Luo, 2018, Ito, 2021].
In each round $t$, we choose $\boldsymbol{a}(t)\in\mathcal{A}$ so that $\mathbb{E}\left[\boldsymbol{a}(t)\mid\boldsymbol{x}(t)\right]=\boldsymbol{x}(t)$, where

$$ $\displaystyle\boldsymbol{x}(t)\in\min_{\boldsymbol{x}\in\mathcal{X}}\left\{\left\langle\boldsymbol{q}(t)+\sum_{s=1}^{t-1}\hat{\boldsymbol{\ell}}(s),\boldsymbol{x}\right\rangle+\psi_{t}\left(\boldsymbol{x}\right)\right\}.$ (4) $$

Here, $\mathcal{X}=\mathrm{conv}\left(\mathcal{A}\right)$ is a convex hull of the action set $\mathcal{A}$. Below, we define $\boldsymbol{q}(t)$, $\hat{\boldsymbol{\ell}}(t)$, and $\psi_{t}(\boldsymbol{x})$.

$q(t)$ is called the optimistic prediction; intuitively, it estimates the loss of the arms in round $t$. For the choice of optimistic prediction $\boldsymbol{q}(t)$, we introduce two methods: the least squares (LS) and gradient descent (GD) methods. LS defines $\boldsymbol{q}(t)=\left(q_{1}(t),\ldots,q_{d}(t)\right)^{\top}\in\left[0,1\right]^{d}$ by

$$ $\displaystyle q_{i}(t)=\frac{1}{N_{i}(t-1)}\left(\frac{1}{2}+\sum_{s=1}^{t-1}\sum_{j=1}^{a_{i}(s)}L_{i,j}(s)\right),$ (5) $$

and GD defines $\boldsymbol{q}(t)$ by $q_{i}(1)=\frac{1}{2}$ and

$$ $\displaystyle q_{i}(t+1)$ $\displaystyle=\!\left\{\begin{array}[]{ll}\!(1-\eta)q_{i}(t)+\eta\frac{1}{a_{i}(t)}\sum_{j=1}^{a_{i}(t)}L_{i,j}(t)&\text{if $a_{i}(t)\geq 1$},\\ \!q_{i}(t)&\text{otherwise},\end{array}\right.$ (8) $$

for all $i\in[d]$ with a step size $\eta\in\left(0,\frac{1}{2}\right)$. The design of LS is to reduce the leading constant $\frac{1}{1-2\eta}$ in the regret, and GD is to derive a path-length bound.

Next, we define $\hat{\boldsymbol{\ell}}(t)=\left(\hat{\ell}_{1}(t),\ldots,\hat{\ell}_{d}(t)\right)\in\mathbb{R}^{d}$ as $\hat{\ell}_{i}(t)=q_{i}(t)+\frac{a_{i}(t)}{x_{i}(t)}\left(k_{i}(t)-q_{i}(t)\right)$ for $i\in[d]$, where
$\boldsymbol{k}(t)=\left(\frac{1}{a_{1}(t)}\sum_{j=1}^{a_{1}(t)}L_{1,j}(t),\ldots,\frac{1}{a_{d}(t)}\sum_{j=1}^{a_{d}(t)}L_{d,j}(t)\right)$. From basic calculation, we can confirm that $\hat{\ell}_{i}(t)$ is an unbiased estimator of $\mathbb{E}\left[\sum_{j=1}^{a_{i}(t)}L_{i,j}(t)\mid\boldsymbol{x}(t)\right]/x_{i}$, which can be seen as the average of the losses occurred by pulling arm $i$.
The optimistic prediction $\boldsymbol{q}(t)$ plays a role in reducing the variance of $\hat{\ell}(t)$; the better $\boldsymbol{q}(t)$ predicts $\boldsymbol{k}(t)$, the smaller the variance of $\hat{\boldsymbol{\ell}}(t)$ becomes.

$\psi_{t}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is a convex regularizer function given by $\psi_{t}(\boldsymbol{x})=\sum_{i=1}^{d}\beta_{i}(t)\varphi_{i}(x_{i})$, where $\varphi_{i}:\mathbb{R}\rightarrow\mathbb{R}$ is defined as

$$ $\displaystyle\varphi_{i}(z)=n_{i}\left(\frac{z}{n_{i}}-1-\log\frac{z}{n_{i}}+\log T\left(\frac{z}{n_{i}}+\left(1-\frac{z}{n_{i}}\log\left(1-\frac{z}{n_{i}}\right)\right)\right)\right),$ (9) $$

and regularization parameters $\left\{\beta_{i}(t)\right\}_{i=1,\ldots,d}$ are defined as

$$ $\displaystyle\beta_{i}(t)=\sqrt{\left(1+\frac{\epsilon_{i}}{n_{i}}\right)^{2}+\frac{1}{\log T}\sum_{s=1}^{t-1}\left(\frac{a_{i}(s)}{n_{i}}\right)^{2}\left(k_{i}(s)-q_{i}(s)\right)^{2}\min\left\{1,\frac{2\left(1-\frac{x_{i}(s)}{n_{i}}\right)}{\left(\frac{x_{i}(s)}{n_{i}}\right)^{2}\log T}\right\}}.$ (10) $$

Here, $\epsilon_{i}\in\left(0,\frac{n_{i}}{2}\right]$ is a hyperparameter.
Our regularizer function $\varphi_{i}$ consists of a logarithmic barrier term $-\log\frac{z}{n_{i}}$ and an entropy term $\left(1-\frac{z}{n_{i}}\right)\log\left(1-\frac{z}{n_{i}}\right)$.
This type of regularizer is called a *hybrid* regularizer and was employed in existing studies for bounding a component of the regret [Zimmert et al., 2019, Ito et al., 2022a, b].
Our regularizer function can be seen as a generalization of that of LBINFV [Tsuchiya et al., 2023] since $n_{i}=1$ for all $i\in[d]$ in the ordinary CSB. $\beta_{i}(t)$ determines the strength of the regularization.
When $a_{i}(s)\geq 1$, $\left(k_{i}(s)-q_{i}(s)\right)^{2}$ in ([10](https://arxiv.org/html/2509.09933v1#S4.E10)) can be seen as the squared error of the optimistic prediction, and the algorithm becomes more explorative when the loss is unpredictable or has a high variance.

Overall, intuitively, $\boldsymbol{q}(t)$ and $\sum_{s=1}^{t-1}\hat{\boldsymbol{\ell}}(t)$ are values determined based on past information and are responsible for the *exploitation*. On the other hand, the regularizer $\psi_{t}(\boldsymbol{x})$ prevents overfitting to past data and encourages moderate *exploration*. This is intended to minimize regret even in adversarial environments.

##### Computational complexity.

OFTRL in ([4](https://arxiv.org/html/2509.09933v1#S4.E4)) can be solved in polynomial time in $d$ as long as the convex hull $\mathcal{X}=\mathrm{conv}(\mathcal{A})$ is represented by a polynomial number of constraints or admits a polynomial-time separation oracle [Schrijver, 1998].
Given the solution $\boldsymbol{x}(t)\in\mathcal{X}$, sampling a combinatorial action $\boldsymbol{a}(t)\in\mathcal{A}$ such that $\mathbb{E}[\boldsymbol{a}(t)\mid\boldsymbol{x}(t)]=\boldsymbol{x}(t)$ requires a convex decomposition of $\boldsymbol{x}(t)$ [Wei and Luo, 2018, Ito, 2021].
By Carathéodory’s theorem, any point $\boldsymbol{x}(t)\in\mathcal{X}$ can be expressed as a convex combination $\boldsymbol{x}(t)=\sum_{k=1}^{m}\lambda_{k}\boldsymbol{a}^{(k)}$, where $\boldsymbol{a}^{(k)}\in\mathcal{A}$, $\lambda_{k}\in[0,1]$, $\sum_{k=1}^{m}\lambda_{k}=1$, and $m\leq d+1$.
When the linear optimization oracle over $\mathcal{A}$ is efficient, the Frank-Wolfe (FW) algorithm can construct such a decomposition iteratively [Combettes and Pokutta, 2021]. This holds, for instance, in OT problems, where the feasible set forms a transportation polytope and each FW step reduces to a tractable linear program.
In contrast, for NP-hard domains such as knapsack problems, solving OFTRL exactly is generally intractable. In practice, this can be addressed either by exploiting problem structure to keep the action set small enough to enumerate, or by using approximate optimization and sampling methods.

##### Regret Analysis.

Here, we show regret upper bounds of the GenLBINFV algorithm. First, we show regret upper bounds of the GenLBINFV algorithm for each optimistic prediction method under the stochastic regime.

###### Theorem 4.1 .

Regret upper bounds of GenLBINFV using LS and GD methods in the stochastic regime are $\mathcal{O}\left(\sum_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$ and $\mathcal{O}\left(\frac{1}{1-2\eta}\sum_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$, respectively, where $\Delta_{i}=\min\limits_{\boldsymbol{a}\in\mathcal{A}:a_{i}\geq 1}\boldsymbol{a}^{\top}\boldsymbol{\ell}-{\boldsymbol{a}^{*}}^{\top}\boldsymbol{\ell}$.

We can see that both optimistic prediction methods achieve $\mathcal{O}\left(\log T\right)$ variance-dependent regret bound. Variance dependency is a clear advantage since the variances of losses for each base arm are extremely small in many real-world applications [Tsuchiya et al., 2023, Komiyama et al., 2017, György et al., 2006].
The upper bound of the ordinary LBINFV algorithm with the duplicating technique is $\mathcal{O}\left(\sum_{i\in J^{*}}b_{i}\frac{\lambda_{\mathcal{A}}^{\prime}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$, where $\lambda_{\mathcal{A}}^{\prime}=\min\{M,\sum_{i=1}^{d}b_{i}-\left\|\boldsymbol{a}^{*}\right\|_{1}\}$.
In the example of OT, when $u_{x}$’s are large, $\sum_{i=1}^{d}b_{i}-\|\boldsymbol{a}^{*}\|_{1}=\left(\sum_{x=1}^{N_{\mathrm{sup}}}u_{x}\right)\times N_{\mathrm{dem}}-\|\boldsymbol{a}^{*}\|_{1}$ is much larger than $M$, and we have $\lambda_{\mathcal{A}}^{\prime}=M$. Therefore, $\lambda_{\mathcal{A}}=\min\{M,W_{J^{*}}\}\leq M=\lambda_{\mathcal{A}}^{\prime}$, which implies that the upper bound of GenLBINFV is no looser than that of the LBINFV since $b_{i}\geq 1$.

Next, we show regret upper bounds of the GenLBINFV algorithm for each optimistic prediction method under the adversarial regime.
Let us denote the cumulative loss of the optimal action, total quadratic variation in loss sequence, and path-length of loss sequence by $L^{*}=\min\limits_{\boldsymbol{a}\in\mathcal{A}}\mathbb{E}[\sum_{t=1}^{T}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\sum_{i=1}^{d}}\sum_{j=1}^{a_{i}(t)}L_{i,j}(t)]$, $Q_{2}=\mathbb{E}[\sum_{t=1}^{T}\|\boldsymbol{k}(t)-\frac{1}{T}\sum_{s=1}^{T}\boldsymbol{k}(s)\|^{2}_{2}]$, and $V_{1}=\mathbb{E}[\sum_{t=1}^{T-1}\|\boldsymbol{k}(t)-\boldsymbol{k}(t+1)\|_{1}]$, respectively, to introduce the data-dependent bound of the GenLBINFV algorithm.

###### Theorem 4.2 .

Regret upper bounds of GenLBINFV using the LS and GD methods in the adversarial regime are $\mathcal{O}\left(\sqrt{\left(\sum_{i=1}^{d}n^{2}_{i}\right)Z^{\mathrm{LS}}\log T}\right)$ and $\mathcal{O}\left(\sqrt{\frac{1}{1-2\eta}\left(\sum_{i=1}^{d}n^{2}_{i}\right)Z^{\mathrm{GD}}\log T}\right)$, respectively, where $Z^{\mathrm{LS}}=\min\{L^{*},MT-L^{*},Q_{2}\}$ and $Z^{\mathrm{GD}}=\min\{L^{*},MT-L^{*},Q_{2},\frac{V_{1}}{\eta}\}$.

$Z^{\mathrm{LS}}$ and $Z^{\mathrm{GS}}$ can be seen as indicators of the problem. If the problem is relatively easy and can be assumed to be $\mathcal{O}\left(Z^{\mathrm{LS}}\right)=\mathcal{O}\left(Z^{\mathrm{GD}}\right)=o\left(T\right)$, the GenLBINFV can achieve a much smaller bound than the the worst case bound $\mathcal{O}\left(\sqrt{M\left(\sum_{i=1}^{d}b_{i}\right)T}\right)$.
The upper bound of the ordinary LBINFV using LS and GD methods are $\mathcal{O}\left(\sqrt{\left(\sum_{i=1}^{d}b_{i}\right)Z^{\mathrm{LS}}\log T}\right)$ and $\mathcal{O}\left(\sqrt{\frac{1}{1-2\eta}\left(\sum_{i=1}^{d}b_{i}\right)Z^{\mathrm{GD}}\log T}\right)$, respectively. In general, we do not know whether $\sum_{i=1}^{d}{n_{i}}^{2}$ is smaller than $\sum_{i=1}^{d}b_{i}$ or not.

On the other hand, GenLBINFV is computationally friendlier than LBINFV with the duplicating technique, since when calling the oracle to compute ([4](https://arxiv.org/html/2509.09933v1#S4.E4)), the time complexity of GenLBINFV in each round is $\mathcal{O}(\mathrm{Poly}(d))$, which can be much smaller than the time complexity of LBINFV with the duplicating technique, $\mathcal{O}(\mathrm{Poly}(\sum_{i=1}^{d}b_{i}))$.

###### Theorem 4.1 .

###### Theorem 4.2 .

##### Regret Upper Bound of the Intermediate Regime

We have the following theorem for the intermediate regime.

###### Theorem 4.3 .

In the stochastic regime with adversarial corruptions, upper bounds of GenLBINFV using the LS and GD methods are $\mathcal{O}\left(R^{\mathrm{LS}}+\sqrt{CMR^{\mathrm{LS}}}\right)$ and $\mathcal{O}\left(R^{\mathrm{GD}}+\sqrt{CMR^{\mathrm{GD}}}\right)$, respectively. Here, $R^{\mathrm{LS}}=\mathcal{O}\left(\sum_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$ and $R^{\mathrm{GD}}=\mathcal{O}\left(\frac{1}{1-2\eta}\sum_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$.

###### Theorem 4.3 .

## 5 Experiments

Figure: Figure 1: The result of the experiment under the stochastic regime.
Refer to caption: x1.png

In this section, we compare the GenLBINFV and GenCTS algorithms with existing algorithms in the CSB literature with the duplicating technique, and numerically illustrate their behavior with synthetic data.

We use the same notation as that used in ([3](https://arxiv.org/html/2509.09933v1#S2.E3)). We consider a case where $\boldsymbol{u}=(1,4,5)^{\top}$ and $\boldsymbol{v}=(4,6)^{\top}$.
In each round $t$, the environment sets a loss $\{c_{xy,j}(t)\}_{j=1,\ldots,n}$ for each edge $(x,y)$.
Then, the player’s objective is to minimize the regret defined as follows: $R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\sum_{x=1}^{m}\sum_{y=1}^{n}\left(\sum_{j=1}^{a_{xy}(t)}c_{xy,j}(t)-\sum_{j=1}^{a^{*}_{xy}}c_{xy,j}(t)\right)\right]$,
where $\boldsymbol{a}^{*}=\mathop{\rm arg~min}\limits_{\boldsymbol{a}\in\mathcal{A}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{x=1}^{m}\sum_{y=1}^{n}\sum_{j=1}^{a_{xy}}c_{xy,j}(t)\right]$.

We generate each element of the cost matrix $\boldsymbol{c}$ uniformly from $[0.10,0.50]$. The time horizon $T$ is set to $10000$.
For the stochastic regime, each sample from edge $(x,y)$ is from $U(0,2c_{xy})$, where $U(a,b)$ denotes the uniform distribution on $[a,b]$. For the stochastic regime with adversarial corruption, until $t\leq 2000$, each sample from edge $(x,y)$ is drawn from $U(0,2c_{xy})$, but when $t>2000$, it is drawn from $U(1-2c_{xy},1)$. We compare our algorithm with the LBINFV and CTS algorithms. To apply these two methods, we use the *duplicating* technique.

We show the results in Figures [2](https://arxiv.org/html/2509.09933v1#S5.F2) and [2](https://arxiv.org/html/2509.09933v1#S5.F2). The lines indicate the average over 30 independent trials. In the stochastic regime, we can see that GenCTS and GenLBINFV algorithms outperform the CTS and LBINFV algorithms, respectively. In the stochastic regime with adversarial corruptions, while Thompson sampling-based algorithms suffer linear regret, the GenLBINFV algorithm does not. We can see that the GenLBINFV algorithm successfully converges faster than the LBINFV algorithm.

## 6 Conclusion

In this study, we proposed the MP-CSB framework, where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round. We proposed two algorithms for MP-CSB: GenCTS and GenLBINFV. GenCTS is computationally feasible even when the action set $\mathcal{A}$ is exponentially large in $d$, and achieves a $\mathcal{O}\left(\log T\right)$ distribution-dependent regret. GenLBINFV is a BOBW algorithm, which achieves $\mathcal{O}(\log T)$ variance-dependent regret in the stochastic regime and $\tilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial regime. We numerically showed that the proposed algorithms outperform existing methods in the CSB literature.

## References

- Audibert and Bubeck [2009]
Jean-Yves Audibert and Sébastien Bubeck.
Minimax policies for adversarial and stochastic bandits.
In *Annual Conference Computational Learning Theory*, 2009.
- Audibert et al. [2014]
Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi.
Regret in online combinatorial optimization.
*Mathematics of Operations Research*, 39(1):31–45, 2014.
- Auer et al. [2002]
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
*Machine Learning*, 47:235–256, 05 2002.
- Cesa-Bianchi and Lugosi [2012]
Nicolò Cesa-Bianchi and Gábor Lugosi.
Combinatorial bandits.
*Journal of Computer and System Sciences*, 78(5):1404–1422, 2012.
- Chen et al. [2016a]
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu.
Combinatorial multi-armed bandit with general reward functions.
In *Proceedings of the 30th International Conference on Neural Information Processing Systems*, NIPS’16, page 1659–1667, Red Hook, NY, USA, 2016a. Curran Associates Inc.
ISBN 9781510838819.
- Chen et al. [2016b]
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang.
Combinatorial multi-armed bandit and its extension to probabilistically triggered arms.
*J. Mach. Learn. Res.*, 17(1):1746–1778, jan 2016b.
- Chen et al. [2021]
Wei Chen, Liwei Wang, Haoyu Zhao, and Kai Zheng.
Combinatorial semi-bandit in the non-stationary environment.
In *Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence*, volume 161 of *Proceedings of Machine Learning Research*, pages 865–875. PMLR, 27–30 Jul 2021.
- Combes et al. [2015]
Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, and Marc Lelarge.
Combinatorial bandits revisited.
In *Neural Information Processing Systems*, pages 2116–2124, 2015.
- Combettes and Pokutta [2021]
Cyrille W. Combettes and Sebastian Pokutta.
Revisiting the approximate carathéodory problem via the frank-wolfe algorithm.
*Math. Program.*, 197(1):191–214, 2021.
- Cuturi [2013]
Marco Cuturi.
Sinkhorn distances: Lightspeed computation of optimal transport.
In *Advances in Neural Information Processing Systems*, volume 26. Curran Associates, Inc., 2013.
- Dantzig and Mazur [2007]
T. Dantzig and J. Mazur.
*Number: The Language of Science*.
A Plume book. Penguin Publishing Group, 2007.
- Fujimoto [2016]
Noriyuki Fujimoto.
A pseudo-polynomial time algorithm for solving the knapsack problem in polynomial space.
In *Combinatorial Optimization and Applications*, pages 624–638, Cham, 2016. Springer International Publishing.
ISBN 978-3-319-48749-6.
- Gai et al. [2012]
Yi Gai, Bhaskar Krishnamachari, and Rahul Jain.
Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations.
*IEEE/ACM Transactions on Networking*, 20(5):1466–1478, 2012.
- Gibbons [1985]
A. Gibbons.
*Algorithmic Graph Theory*.
Cambridge University Press, 1985.
ISBN 9780521288811.
- György et al. [2006]
András György, Tamás Linder, and György Ottucsák.
The shortest path problem under partial monitoring.
In *Learning Theory*, pages 468–482, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
ISBN 978-3-540-35296-9.
- Hoeffding [1994]
Wassily Hoeffding.
*Probability Inequalities for sums of Bounded Random Variables*, pages 409–426.
Springer New York, New York, NY, 1994.
ISBN 978-1-4612-0865-5.
doi: 10.1007/978-1-4612-0865-5_26.
- Ito [2021]
Shinji Ito.
Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits.
In *Advances in Neural Information Processing Systems*, volume 34, pages 2654–2667. Curran Associates, Inc., 2021.
- Ito and Takemura [2023a]
Shinji Ito and Kei Takemura.
Best-of-three-worlds linear bandit algorithm with variance-adaptive regret bounds.
In *Proceedings of Thirty Sixth Conference on Learning Theory*, pages 2653–2677, 2023a.
- Ito and Takemura [2023b]
Shinji Ito and Kei Takemura.
An exploration-by-optimization approach to best of both worlds in linear bandits.
In *Thirty-seventh Conference on Neural Information Processing Systems*, 2023b.
- Ito et al. [2022a]
Shinji Ito, Taira Tsuchiya, and Junya Honda.
Adversarially robust multi-armed bandit algorithm with variance-dependent regret bounds.
In *Proceedings of Thirty Fifth Conference on Learning Theory*, volume 178, pages 1421–1422. PMLR, 2022a.
- Ito et al. [2022b]
Shinji Ito, Taira Tsuchiya, and Junya Honda.
Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs.
In *Proceedings of the 36th International Conference on Neural Information Processing Systems*, 2022b.
- Kellerer et al. [2004]
H. Kellerer, U. Pferschy, and D. Pisinger.
*Knapsack Problems*.
Springer, Berlin, Germany, 2004.
- Komiyama et al. [2017]
Junpei Komiyama, Junya Honda, and Akiko Takeda.
Position-based multiple-play bandit problem with unknown position bias.
In *Advances in Neural Information Processing Systems*, volume 30. Curran Associates, Inc., 2017.
- Kveton et al. [2015]
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari.
Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits.
In *Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics*, volume 38 of *Proceedings of Machine Learning Research*, pages 535–543, San Diego, California, USA, 09–12 May 2015. PMLR.
- Lee et al. [2021]
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang, and Xiaojin Zhang.
Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously.
In Marina Meila and Tong Zhang, editors, *Proceedings of the 38th International Conference on Machine Learning*, volume 139 of *Proceedings of Machine Learning Research*, pages 6142–6151. PMLR, 18–24 Jul 2021.
- Merlis and Mannor [2020]
Nadav Merlis and Shie Mannor.
Tight lower bounds for combinatorial multi-armed bandits.
In Jacob Abernethy and Shivani Agarwal, editors, *Proceedings of Thirty Third Conference on Learning Theory*, volume 125 of *Proceedings of Machine Learning Research*, pages 2830–2857. PMLR, 09–12 Jul 2020.
- Neu [2015]
Gergely Neu.
First-order regret bounds for combinatorial semi-bandits.
In *Proceedings of The 28th Conference on Learning Theory*, volume 40 of *Proceedings of Machine Learning Research*, pages 1360–1375, Paris, France, 03–06 Jul 2015. PMLR.
- Perrault et al. [2020]
Pierre Perrault, Etienne Boursier, Vianney Perchet, and Michal Valko.
Statistical efficiency of thompson sampling for combinatorial semi-bandits.
In *Proceedings of the 34th International Conference on Neural Information Processing Systems*, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc.
ISBN 9781713829546.
- Pettie and Ramachandran [2002]
Seth Pettie and Vijaya Ramachandran.
An optimal minimum spanning tree algorithm.
*J. ACM*, 49(1):16–34, jan 2002.
- Qin et al. [2014]
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu.
Contextual combinatorial bandit and its application on diversified online recommendation.
In *SDM*, 2014.
- Schrijver [1998]
Alexander Schrijver.
*Theory of linear and integer programming*.
John Wiley & Sons, 1998.
- Sniedovich [2006]
Moshe Sniedovich.
Dijkstra’s algorithm revisited: the dynamic programming connexion.
*Control and Cybernetics*, 35:599–620, 2006.
- Tsuchiya et al. [2023]
Taira Tsuchiya, Shinji Ito, and Junya Honda.
Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits.
In *Proceedings of The 26th International Conference on Artificial Intelligence and Statistics*, volume 206 of *Proceedings of Machine Learning Research*, pages 8117–8144. PMLR, 25–27 Apr 2023.
- ul Hassan and Curry [2016]
Umair ul Hassan and Edward Curry.
Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning.
*Expert Systems with Applications*, 58:36–56, 2016.
- Villani [2008]
C. Villani.
*Optimal Transport: Old and New*.
Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008.
ISBN 9783540710509.
- Wang and Chen [2017]
Qinshi Wang and Wei Chen.
Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications.
In *Neural Information Processing Systems*, 2017.
- Wang and Chen [2018]
Siwei Wang and Wei Chen.
Thompson sampling for combinatorial semi-bandits.
In *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, pages 5114–5122. PMLR, 10–15 Jul 2018.
- Wei and Luo [2018]
Chen-Yu Wei and Haipeng Luo.
More adaptive algorithms for adversarial bandits.
In *Annual Conference Computational Learning Theory*, 2018.
- Wen et al. [2014]
Zheng Wen, Branislav Kveton, and Azin Ashkan.
Efficient learning in large-scale combinatorial semi-bandits.
In *International Conference on Machine Learning*, 2014.
- Zimmert et al. [2019]
J. Zimmert, H. Luo, and C.-Y. Wei.
Beating stochastic and adversarial semi-bandits optimally and simultaneously.
In *Proceedings of The 36th International Conference on Machine Learning*, volume 97, pages 7683 – 7692, 2019.
- Zimmert and Seldin [2021]
Julian Zimmert and Yevgeny Seldin.
Tsallis-inf: an optimal algorithm for stochastic and adversarial bandits.
*J. Mach. Learn. Res.*, 22(1), January 2021.

## Appendix A Example of the Duplicating Technique

In Figure [4](https://arxiv.org/html/2509.09933v1#A1.F4), we show an example of the OT problem. Here, $S=\{1,2,3\}$ and $D=\{1,2,3,4\}$. We have $d=n_{s}\times n_{d}=12$ base arms. One candidate of action $\boldsymbol{a}$ can be $\boldsymbol{a}=\begin{pmatrix}1&0&0&0\\
0&1&2&0\\
0&0&0&4\end{pmatrix}$.
The player observes a set of losses, $\{L_{(1,1),1}\}\cup\{L_{(2,2),1}\}\cup\{L_{(2,3),1},L_{(2,3),2}\}\cup\{L_{(3,4),1},L_{(3,4),2},L_{(3,4),3},L_{(3,4),4}\}$. Here, $L_{(x,y),j}$ is the loss of edge $(x,y)$ observed by the $j$-th truck departed from supplier $x$ to demander $y$. Then, she incurs a loss of $f(\boldsymbol{a}(t),\boldsymbol{L}^{(1,1)},\ldots,\boldsymbol{L}^{(3,4)})=\sum\limits_{x=1}^{n_{s}}\sum\limits_{y=1}^{n_{d}}\sum\limits_{j=1}^{a_{xy}}L_{(x,y),j}$.

To apply existing algorithms in the ordinary CSB algorithms to MP-CSB, one may use the duplicating technique, which is shown in Figure [4](https://arxiv.org/html/2509.09933v1#A1.F4). Here, we treat each truck independently so that the action set becomes binary. However, the duplicating technique makes the sample efficiency in the stochastic regime worse.
For instance, in the stochastic regime, orange, green, and purple arms (edges) in Figure [4](https://arxiv.org/html/2509.09933v1#A1.F4) follow the same distribution as edges $(1,2)$, $(2,2)$, and $(3,2)$, in Figure [4](https://arxiv.org/html/2509.09933v1#A1.F4), respectively.
Such a lack of distinction between identical distributions leads to poor sample efficiency and may force the player to choose suboptimal actions frequently.

Figure: Figure 3: A simple sketch of the MP-CSB problem applied to the OT problem.

## Appendix B Proof of Theorem 3.1

Here, we prove Theorem [3.1](https://arxiv.org/html/2509.09933v1#S3.Thmtheorem1).

### B.1 Chernoff-Hoeffding Inequality

We first introduce the Chernoff-Hoeffding inequality, which is useful in the analysis.

###### Fact B.1 (Chernoff-Hoeffding Inequality [Hoeffding, 1994 ] ) .

When $X_{1},X_{2},\ldots,X_{N}$ are identical independent random variables such that $X_{i}\in[0,1]$ and $\mathbb{E}[X_{i}]=\mu_{i}$, we have the following inequalities:

$$ $\displaystyle\Pr\left[\frac{\sum\limits_{i=1}^{N}X_{i}}{N}\geq\mu_{i}+\epsilon\right]\leq\exp\left(-2\epsilon^{2}N\right),$ (11) $\displaystyle\Pr\left[\frac{\sum\limits_{i=1}^{N}X_{i}}{N}\leq\mu_{i}+\epsilon\right]\leq\exp\left(-2\epsilon^{2}N\right).$ (12) $$

###### Fact B.1 (Chernoff-Hoeffding Inequality [Hoeffding, 1994 ] ) .

### B.2 Notations

We use $p_{i}(t)$ and $q_{i}(t)$ to denote the value of $p_{i}$ and $q_{i}$ at the beginning of time $t$. Let

$$ $\displaystyle\hat{\mu}_{i}(t)=\frac{p_{i}(t)-1}{N_{i}(t)}=\frac{1}{N_{i}(t)}\sum\limits_{\tau:\tau<t,i\in I_{\boldsymbol{a}(t)}}\sum\limits_{j=1}^{a_{i}(t)}Y_{i,j}(t)$ (13) $$

be the empirical mean of arm $i$ at the beginning of time $t$, where $N_{i}(t)=p_{i}(t)+q_{i}(t)-2$ is the number of observations of arm $i$ at the beginning of time $t$.
Notice that for fixed arm $i$, in different time $t$ with $i\in I_{\boldsymbol{a}(t)}$ and $j\in[a_{i}(t)]$, $X_{i,j}(t)$’s are i.i.d with mean $\ell_{i}$, and $Y_{i,j}(t)$ is a Bernoulli random variable with mean $X_{i,j}$ thus the Bernoulli random variables $Y_{i,j}(t)$’s are also i.i.d. with mean $\ell_{i}$.

Let us define $M^{*}=\|\boldsymbol{a}^{*}\|_{1}$. Also, let $\epsilon$ be an arbitrary real number that satisfies   Based on $\hat{\mu}_{i}(t)$, we can define the following five events :

- •
$\mathcal{P}(t)=\left\{\boldsymbol{a}(t)\neq\boldsymbol{a}^{*}\right\}$
- •
$\mathcal{Q}(t)=\left\{\exists i\in I_{\boldsymbol{a}(t)},|\hat{\mu}_{i}(t)-\ell_{i}|>\frac{\epsilon}{\|\boldsymbol{a}(t)\|_{1}}\right\}$
- •
$\mathcal{R}(t)=\left\{\sum\limits_{i\in I_{\boldsymbol{a}(t)}}a_{i}(t)|\theta_{i}(t)-\ell_{i}|>\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+1\right)\epsilon\right\}$
- •
$\mathcal{S}(t)=\left\{\sum\limits_{i\in I_{\boldsymbol{a}(t)}}a_{i}(t)|\theta_{i}(t)-\hat{\mu}_{i}(t)|>\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right\}$
- •
$\mathcal{T}(t)=\left\{\sum\limits_{i\in I_{\boldsymbol{a}(t)}}\frac{1}{N_{i}(t)}\leq\frac{2\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{\log\left(2^{d}|\mathcal{A}|T\right)}\right\}$

### B.3 Proof of Theorem 3.1

The total regret can be written as follows:

$$ $\displaystyle\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\mathcal{Q}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]+\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\lnot\mathcal{Q}(t)\land\mathcal{R}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]$ $\displaystyle+\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\lnot\mathcal{R}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right].$ (14) $$

We analyze each term in the RHS of ([14](https://arxiv.org/html/2509.09933v1#A2.E14)).

#### B.3.1 The First Term of the RHS of ( 14 )

We can use the following lemma to bound the first term. Below, we denote $\hat{\mu}_{i}(t)$ by the sample mean of arm $i$ at the beginning of round $t$.

###### Lemma B.1 .

In Algorithm [1](https://arxiv.org/html/2509.09933v1#alg1), we have

$$ $\displaystyle\mathbb{E}\left[\left\{t\in[T]\ |\ i\in I_{\boldsymbol{a}(t)},|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon\right\}\right]\leq 1+\frac{1}{\epsilon^{2}}$ $$

for any $1\leq i\leq d$.

###### Proof.

Let $\tau_{1},\tau_{2},\ldots$ be the time slots such that $i\in I_{\boldsymbol{a}(t)}$ and define $\tau_{0}=0$, then

$$ $\displaystyle\mathbb{E}\left[\left|\left\{t\in[T]\mid i\in I_{\boldsymbol{a}(t)},|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon\right\}\right|\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\mathbbm{1}\left[i\in I_{\boldsymbol{a}(t)},|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon\right]\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\sum\limits_{w=0}^{T}\mathbb{E}\left[\sum\limits_{t=\tau_{w}}^{\tau_{w+1}-1}\mathbbm{1}\left[i\in I_{\boldsymbol{a}(t)},|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon\right]\right]\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\sum\limits_{w=0}^{n_{i}T}\Pr\left[|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon,N_{i}=w\right]\right]$ $\displaystyle\leq$ $\displaystyle 1+\sum\limits_{w=1}^{n_{i}T}\Pr\left[|\hat{\mu}_{i}(t)-\ell_{i}|>\epsilon,N_{i}=w\right]$ $\displaystyle\leq$ $\displaystyle 1+\sum\limits_{w=1}^{T}\exp\left(-2w\epsilon^{2}\right)+\sum\limits_{w=1}^{T}\exp\left(-2w\epsilon^{2}\right)$ (15) $\displaystyle\leq$ $\displaystyle 1+2\sum\limits_{w=1}^{\infty}\left(\exp\left(-2w\epsilon^{2}\right)\right)^{w}$ $\displaystyle\leq$ $\displaystyle 1+2\frac{\exp\left(-2\epsilon^{2}\right)}{1+\exp\left(-2\epsilon^{2}\right)}$ $\displaystyle\leq$ $\displaystyle 1+\frac{2}{2\epsilon^{2}}$ $\displaystyle=$ $\displaystyle 1+\frac{1}{\epsilon^{2}}$ $$

where Eq ([15](https://arxiv.org/html/2509.09933v1#A2.E15)) is because of the Chernoff-Hoeffding’s inequality (Fact [B.1](https://arxiv.org/html/2509.09933v1#A2.Thmfact1)).
∎

By Lemma [B.1](https://arxiv.org/html/2509.09933v1#A2.Thmtheorem1), we know that the first term is upper bounded by $\left(\frac{dM^{2}}{\epsilon^{2}}+d\right)\Delta_{\mathrm{max}}$, where $M=\max\limits_{\boldsymbol{a}\in\mathcal{A}}\|\boldsymbol{a}\|_{1}$.

###### Lemma B.1 .

###### Proof.

#### B.3.2 The Second Term of the RHS of ( 14 )

Under $\lnot\mathcal{Q}(t)\land\mathcal{R}(t)$, we must have that

$$ $\displaystyle\sum\limits_{i=1}^{d}a_{i}(t)|\theta_{i}(t)-\hat{\mu}_{i}(t)|\geq$ $\displaystyle\sum\limits_{i=1}^{d}a_{i}(t)|\theta_{i}(t)-\ell_{i}|-\sum\limits_{i=1}^{d}a_{i}(t)|\ell_{i}-\hat{\mu}_{i}(t)|$ $\displaystyle>$ $\displaystyle\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-({M^{*}}^{2}+1)\epsilon^{2}-\epsilon,$ $\displaystyle=$ $\displaystyle\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon^{2}$ (16) $$

i.e., event $\mathcal{S}(t)$ must happen.

Then, the second term of the RHS of
([14](https://arxiv.org/html/2509.09933v1#A2.E14)) can be bounded by

$$ $\displaystyle\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\lnot\mathcal{Q}(t)\land\mathcal{R}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\mathcal{S}(t)\land\mathcal{T}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]+\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbbm{1}\left[\mathcal{S}(t)\land\lnot\mathcal{T}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right].$ $$

Following the same discussion in Perrault et al. [2020], we can obtain $\Pr\left[\mathcal{S}(t)\land\mathcal{T}(t)\right]\leq\mathcal{O}\left(\frac{1}{T}\right)$, and therefore, $\mathbb{E}\left[\mathbbm{1}\left[\mathcal{S}(t)\land\mathcal{T}(t)\land\mathcal{P}(t)\right]\times\Delta_{\boldsymbol{a}(t)}\right]$ is $\mathcal{O}\left(1\right)$.

Now, we bound the regret term $\mathbb{E}\left[\mathbbm{1}\left[\mathcal{S}(t)\land\lnot\mathcal{T}(t)\land\mathcal{P}(t)\right]\right]$. Here, we use the regret allocation method to count this regret term. That is, for any time step $t$ such that $\mathcal{S}(t)\land\lnot\mathcal{T}(t)\land\mathcal{P}(t)$ happens, we allocate regret $g_{i}(N_{i}(t))$ to each base arm $i\in I_{\boldsymbol{a}(t)}$. We say the allocation function $g_{i}$’s are correct if the sum of allocated regret in this step is larger than $\Delta_{\boldsymbol{a}(t)}$, i.e., $\sum\limits_{i=1}^{d}g_{i}(N_{i}(t))\geq\Delta_{\boldsymbol{a}(t)}$.

Then, we describe our allocation function $g_{i}$’s. Here, we define

$$ $\displaystyle L_{i,1}=\frac{m\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)^{2}}$ (17) $$

and

$$ $\displaystyle L_{i,2}=\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)^{2}}.$ (18) $$

Also, we define $g_{i}(w)$ as follows:

$$ $\displaystyle g_{i}(w)=\left\{\begin{array}[]{ll}\Delta_{\mathrm{max}}&(w=0)\\ 2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{w}}&0<w<L_{i,2}\\ \frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{w\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{{\Delta_{\boldsymbol{a}}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}&L_{i,2}<w\leq L_{i,1}\\ 0&w>L_{i,1}\end{array}.\right.$ (23) $$

Now, we prove that these allocation function $g_{i}$’s satisfy the correctness condition when $\epsilon\leq\frac{\Delta_{\mathrm{min}}}{2\kappa_{r}({M^{*}}^{2}+2)}$, i.e., if event $\mathcal{S}(t)\land\lnot\mathcal{T}(t)\land\mathcal{P}(t)$ happens, then $\sum\limits_{i=1}^{d}g_{i}(N_{i}(t))\geq\Delta_{\boldsymbol{a}(t)}$.

If there exists $i\in I_{\boldsymbol{a}(t)}$ such that $N_{i}(t)=0$, then $g_{i}(N_{i}(t))=\Delta_{\mathrm{max}}\geq\Delta_{\boldsymbol{a}(t)}$.
Since $g_{i}(w)$ is always non-negative, we know that $\sum\limits_{i\in I_{\boldsymbol{a}(t)}}g_{i}(w)\geq\Delta_{\boldsymbol{a}(t)}$.

If there exists $i\in I_{\boldsymbol{a}(t)}$ such that $1\leq N_{i}(t)\leq\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)^{2}}$, then $N_{i}(t)\leq L_{i,2}$, and therefore,

$$ $\displaystyle g_{i}(t)=2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)}}\geq 2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)^{2}}}}=2\kappa_{r}\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)\geq\Delta_{\boldsymbol{a}(t)},$ $$

where the last inequality is because that $\epsilon\leq\frac{\Delta_{\mathrm{min}}}{2\kappa_{r}({M^{*}}^{2}+2)}$ and $a_{i}(t)\geq 1$. From the above inequalities, we know that $\sum\limits_{i\in I_{\boldsymbol{a}(t)}}g_{i}(t)\geq\Delta_{\boldsymbol{a}(t)}$.

If for all $i\in I_{\boldsymbol{a}(t)}$, $N_{i}(t)>\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}$, then we use $S^{1}_{\boldsymbol{a}(t)}$ to denote the set of arms $i\in I_{\boldsymbol{a}(t)}$ such that $N_{i}(t)>L_{i,1}$, $S^{2}_{\boldsymbol{a}(t)}$ to denote the set of arms $i\in I_{\boldsymbol{a}(t)}$ such that $L_{i,2}<N_{i}(t)<L_{i,1}$, $S^{3}_{\boldsymbol{a}(t)}(t)$ to denote the set of arms $i\in I_{\boldsymbol{a}(t)}$ such that $N_{i}(t)\leq L_{i,2}$. By the definition of allocation functions $g_{i}$’s, we have that

$$ $\displaystyle\sum\limits_{ii\in I_{\boldsymbol{a}(t)}}g_{i}(N_{i}(t)$ $\displaystyle=$ $\displaystyle\sum\limits_{i\in I^{3}_{\boldsymbol{a}(t)}}2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)}}+\sum\limits_{i\in I^{2}_{\boldsymbol{a}(t)}}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ $\displaystyle\geq$ $\displaystyle\sum\limits_{i\in I^{3}_{\boldsymbol{a}(t)}}2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)}}+\sum\limits_{i\in I^{2}_{\boldsymbol{a}(t)}}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ $\displaystyle=$ $\displaystyle\sum\limits_{i\in I^{3}_{\boldsymbol{a}(t)}}2\kappa_{r}\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\cdot\sqrt{\frac{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{\log\left(2^{d}|\mathcal{A}|T\right)}}$ $\displaystyle+\sum\limits_{i\in I^{2}_{\boldsymbol{a}(t)}}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ $\displaystyle\geq$ $\displaystyle\sum\limits_{i\in I^{3}_{\boldsymbol{a}(t)}}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}+\sum\limits_{i\in I^{2}_{\boldsymbol{a}(t)}(t)}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ (24) $\displaystyle=$ $\displaystyle\sum\limits_{i\in I_{\boldsymbol{a}(t)}\setminus I^{1}_{\boldsymbol{a}(t)}(t)}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{N_{i}(t)\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ $\displaystyle=$ $\displaystyle\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\left(\sum\limits_{i\in I_{\boldsymbol{a}(t)}}\frac{1}{N_{i}(t)}-\sum\limits_{i\in I^{1}_{\boldsymbol{a}(t)}}\frac{1}{N_{i}(t)}\right)$ $\displaystyle\geq$ $\displaystyle\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\left(\frac{2\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{\log\left(2^{d}|\mathcal{A}|T\right)}-\sum\limits_{i\in I^{1}_{\boldsymbol{a}(t)}}\frac{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{m\log\left(2^{d}|\mathcal{A}|T\right)}\right)$ (25) $\displaystyle\geq$ $\displaystyle\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\left(\frac{2\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{\log\left(2^{d}|\mathcal{A}|T\right)}-m\frac{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{m\log\left(2^{d}|\mathcal{A}|T\right)}\right)$ $\displaystyle=$ $\displaystyle\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\frac{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)^{2}}{\log\left(2^{d}|\mathcal{A}|T\right)}$ $\displaystyle=$ $\displaystyle 2\kappa_{r}\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)$ $\displaystyle\geq$ $\displaystyle\Delta_{\boldsymbol{a}(t)}.$ $$

Here, Eq([24](https://arxiv.org/html/2509.09933v1#A2.E24)) is because that $N_{i}(t)>\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\left(\frac{\Delta_{\boldsymbol{a}(t)}}{\kappa_{r}}-({M^{*}}^{2}+2)\epsilon\right)^{2}}$ (as we assumed in the beginning of the paragraph), Eq ([25](https://arxiv.org/html/2509.09933v1#A2.E25)) comes from the definition of $\lnot\mathcal{T}(t)$ (the first term) and the definition of $S^{1}_{\boldsymbol{a}(t)}$ (the second term). This finishes the proof that the allocation functions $g_{i}$’s satisfy the correctness condition when $\epsilon\leq\frac{\Delta_{\mathrm{min}}}{2\kappa_{r}\left({M^{*}}^{2}+2\right)}$.

Because of this, the second term of ([14](https://arxiv.org/html/2509.09933v1#A2.E14)) is upper-bounded by

$$ $\displaystyle\mathbb{E}\left[\mathbbm{1}\left[\lnot\mathcal{Q}(t)\land\mathcal{R}(t)\land\mathcal{P}(t)\right]\right]$ $\displaystyle\leq$ $\displaystyle(d+1)\Delta_{\mathrm{max}}+\sum\limits_{i=1}^{d}\sum\limits_{w=1}^{L_{i,2}}2\kappa_{r}\sqrt{\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{w}}+\sum\limits_{i=1}^{d}\sum\limits_{w=L_{i,2}+1}^{L_{i,1}}\frac{1}{w}\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}(t)}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ $\displaystyle\leq$ $\displaystyle(d+1)\Delta_{\mathrm{max}}+\sum\limits_{i=1}^{d}4\sqrt{\log\left(2^{d}|\mathcal{A}|T\right)L_{i,2}}+\sum\limits_{i=1}^{d}\left(1+\log\left(\frac{L_{i,1}}{L_{i,2}}\right)\right)\frac{2\kappa_{r}\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}(t)}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$ (26) $$

Here, Eq ([26](https://arxiv.org/html/2509.09933v1#A2.E26)) is because that $\sum\limits_{w=1}^{\kappa_{r}}\sqrt{\frac{1}{w}}\leq 2\sqrt{\kappa_{r}}$ (by as simple inductive proof on $N$) and $\sum\limits_{w=N_{1}}^{N_{2}}\frac{1}{w}\leq 1+\log\frac{N_{2}}{N_{1}}$.

The value $\sqrt{\log\left(2^{d}|\mathcal{A}|T\right)L_{i,2}}$ equals to $\frac{\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}\in\mathcal{A}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}$, and $\log\frac{L_{i,1}}{L_{i,2}}=\log m$, and therefore, the total regret in the second term is

$$ $\displaystyle\mathcal{O}\left(\sum\limits_{i=1}^{d}\frac{\kappa_{r}\log m\log\left(T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\right),$ (27) $$

and if set $\epsilon=\frac{\Delta}{({M-{*}}^{2}+2)\epsilon}$, the second term is

$$ $\displaystyle\mathcal{O}\left(\sum\limits_{i=1}^{d}\frac{{\kappa_{r}}^{2}\log m}{\Delta_{i}}\log T\right)$ (28) $$

#### B.3.3 The Third Term of the RHS of ( 14 )

Let $\boldsymbol{\theta}=\left(\theta_{1},\ldots,\theta_{d}\right)$ be a vector of parameters, $I\subseteq[d]$ and $I\neq\emptyset$ be some arm set, and $\boldsymbol{V}^{c}$ be the complement of $\boldsymbol{V}$. Recall that $\boldsymbol{\theta}_{V}$ is a vector whose $i$-th element is $\theta_{i}$ if $i\in V$ and 0 if $i\notin V$. Also, we use the notation $(\boldsymbol{\theta}^{\prime}_{\boldsymbol{V}},\boldsymbol{\theta}_{\boldsymbol{V}^{c}})$ to denote replacing $\theta_{i}$’s for $i\in V$ and keeping the values $\theta_{i}$ for $i\in V^{c}$ unchanged.

Given a subset $I\subseteq I_{\boldsymbol{a}^{*}}$, we consider the following property for $\boldsymbol{\theta}_{I^{c}}$. For any $\boldsymbol{\theta}^{\prime}_{Z}$ such that $\|\boldsymbol{\theta}^{\prime}_{Z}-\boldsymbol{\ell}_{Z}\|_{\infty}\leq\epsilon$, let $\boldsymbol{\theta}^{\prime}=\left(\boldsymbol{\theta}^{\prime}_{Z},\boldsymbol{\theta}_{I^{c}}\right)$, then:

- •
$I\subseteq I_{\mathsf{Oracle}(\boldsymbol{\theta}^{\prime})}$
- •
Either $\mathsf{\mathsf{Oracle}}(\boldsymbol{\theta}^{\prime})=\boldsymbol{a}^{*}$ or $\|\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)\cdot\left(\boldsymbol{\theta}^{\prime}-\boldsymbol{\ell}\right)\|_{1}\geq\Delta_{\mathsf{Oracle}(\boldsymbol{\theta}^{\prime})}-\left({M^{*}}^{2}+2\right)\epsilon$

The first one is to make sure that if we have normal samples in $I$ at time $t$ (i.e., the samples value $\theta_{i}(t)$ is within $\epsilon$ neighborhood of $\ell_{i}$ for all $i\in Z$), then all the arms in $I$ will be played and observed. These observations would update the beta distributions of these base arms to be more accurate, such that the probability of the next time that the samples from these base arms are also within $\epsilon$ neighborhood of their true mean value becomes larger. This fact would be used later in the quantitative regret analysis. The second one says that if the samples in $I$ are normal, then $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ can not happen. We use $\mathcal{E}_{Z,1}\left(\boldsymbol{\theta}\right)$ to denote the event that the vector $\boldsymbol{\theta}_{I^{c}}$ has such a property, and emphasize that this event only depends on the values in vector $\boldsymbol{\theta}_{I^{c}}$.

What we want to do is to find some exact $I$ such that $\mathcal{E}_{Z,1}\left(\boldsymbol{\theta}(t)\right)$ happens when $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ happens. If such $I$ exists, then for any $t$ such that $\mathcal{E}_{Z,1}\left(\boldsymbol{\theta}(t)\right)$ happens, there are two possible cases: $\mathrm{i}$) the samples of all arms $i\in Z$ are normal, which means $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ cannot happen, and will update the posterior distributions of all the arms $i\in Z$ to increase the probability that the samples of all the arms $i\in Z$ are normal; $\mathrm{ii}$) the samples of some arms $i\in Z$ are not normal, and $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ may happen in this case. As time goes on, the probability that the samples in $I$ are normal becomes larger and larger, and therefore the probability that $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ happens becomes smaller and smaller. Thus, $\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbf{1}\left[\lnot\mathcal{R}(t)\land\mathcal{P}(t)\right]\right]$ has a constant upper bound.

The following lemma shows that such $I$ must exist, and it is the key lemma in the analysis of the third term.

###### Lemma B.2 .

Suppose that $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ happens, then there exists $I\subseteq I_{\boldsymbol{a}^{*}}$ and $I\neq\emptyset$ such that $\mathcal{E}_{Z,1}(\boldsymbol{\theta}(t))$ holds.

###### Proof.

Firstly, consider the case that we choose $I=I_{\boldsymbol{a}^{*}}$, i.e., we change $\boldsymbol{\theta}_{I_{\boldsymbol{a}^{*}}}(t)$ to some $\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}-\boldsymbol{\ell}_{I_{\boldsymbol{a}^{*}}}\|_{\infty}\leq\epsilon$ and get a new vector $\boldsymbol{\theta}^{\prime}=\left(\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}},\boldsymbol{\theta}_{I_{\boldsymbol{a}^{*}}^{c}}(t)\right)$.
We claim that for any $\boldsymbol{a}^{\prime}$ such that $I_{\boldsymbol{a}^{\prime}}\land I_{\boldsymbol{a}^{*}}=\emptyset$, $\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)\neq\boldsymbol{a}^{\prime}$.
This is because

$$ $\displaystyle\langle\boldsymbol{a}^{\prime},\boldsymbol{\theta}^{\prime}\rangle=$ $\displaystyle\langle\boldsymbol{a}^{\prime},\boldsymbol{\theta}\left(t\right)\rangle$ (29) $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}\left(t\right),\boldsymbol{\theta}(t)\rangle$ (30) $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}(t),\boldsymbol{\ell}\rangle+\left({\Delta_{\boldsymbol{a}(t)}}-\left({M^{*}}^{2}+1\right)\epsilon\right)$ (31) $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-\left({M^{*}}^{2}+1\right)\epsilon$ (32) $\displaystyle<$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-M^{*}\epsilon$ (33) $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\theta}^{\prime}\rangle$ (34) $$

Eq ([29](https://arxiv.org/html/2509.09933v1#A2.E29)) is because $\boldsymbol{\theta}^{\prime}$ and $\boldsymbol{\theta}(t)$ only differs on arms in $I_{\boldsymbol{a}^{*}}$ but $I_{\boldsymbol{a}^{\prime}}\cap I_{\boldsymbol{a}^{*}}\neq\emptyset$. Eq ([30](https://arxiv.org/html/2509.09933v1#A2.E30)) is by the optimality of $\boldsymbol{a}(t)$ on input $\boldsymbol{\theta}(t)$. Eq ([31](https://arxiv.org/html/2509.09933v1#A2.E31)) is by the event $\lnot\mathcal{R}(t)$. Eq ([32](https://arxiv.org/html/2509.09933v1#A2.E32)) is by the definition of $\Delta_{\boldsymbol{a}(t)}$. Eq ([34](https://arxiv.org/html/2509.09933v1#A2.E34)) again uses the Lipschitz continuity. Thus, the claim holds.

We have two possibilities for $\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)$:

- 1a)
for all $\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}-\boldsymbol{\ell}_{I_{\boldsymbol{a}^{*}}}\|_{\infty}\leq\epsilon$, $I_{\boldsymbol{a}^{*}}\subseteq I_{\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)}$
- 1b)
for some $\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}-\boldsymbol{\ell}_{I_{\boldsymbol{a}^{*}}}\|_{\infty}\leq\epsilon$, $\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)=\boldsymbol{a}^{1}$ where $I_{\boldsymbol{a}^{1}}\cap I_{\boldsymbol{a}^{*}}=I_{1}$ and $I_{1}\neq I_{\boldsymbol{a}^{*}}$, $I_{1}\neq\emptyset$.

In 1a), let $\boldsymbol{a}^{0}=\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)$. Then, we have $\langle\boldsymbol{a}^{0},\boldsymbol{\theta}^{\prime}\rangle\geq\langle\boldsymbol{a}^{*},\boldsymbol{\theta}^{\prime}\rangle\geq\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-M^{*}\epsilon$.
If $\boldsymbol{a}^{0}\notin\mathsf{OPT}$, we have $\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle=\langle\boldsymbol{a}^{0},\boldsymbol{\ell}\rangle+\Delta_{\boldsymbol{a}^{0}}$.
Together, we have $\langle\boldsymbol{a}^{0},\boldsymbol{\theta}^{\prime}\rangle\geq\langle\boldsymbol{a}^{0},\boldsymbol{\ell}\rangle+\Delta_{\boldsymbol{a}^{0}}-M^{*}\epsilon$.
This implies that $\|\boldsymbol{a}^{0}\cdot\left(\boldsymbol{\theta}^{\prime}-\boldsymbol{\ell}\right)\|_{1}\geq\Delta_{\boldsymbol{a}^{0}}-M^{*}\epsilon>\Delta_{\boldsymbol{a}^{0}}-\left({M^{*}}^{2}+1\right)\epsilon>\Delta_{\boldsymbol{a}^{0}}-\left({M^{*}}^{2}+1\right)\epsilon$.
That is, we conclude that either $\boldsymbol{a}^{0}\in\mathsf{OPT}$ or $\|\boldsymbol{a}^{0}\cdot\left(\boldsymbol{\theta}^{\prime}-\boldsymbol{\ell}\right)\|_{1}\geq\Delta_{\boldsymbol{a}^{0}}-M^{*}\epsilon>\Delta_{\boldsymbol{a}^{0}}-\left({M^{*}}^{2}+1\right)\epsilon$, which means that $\mathcal{E}_{\boldsymbol{a}^{*},1}\left(\boldsymbol{\theta}^{\prime}(t)\right)=\mathcal{E}_{\boldsymbol{a}^{*},1}\left(\boldsymbol{\theta}(t)\right)$ holds.

Next, we consider 1b). Fix a $\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{\boldsymbol{a}^{*}}}-\boldsymbol{\ell}_{I_{\boldsymbol{a}^{*}}}\|_{\infty}\leq\epsilon$. Let $\boldsymbol{a}^{1}=\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)$ which does not equal to $\boldsymbol{a}^{*}$. Then $\langle\boldsymbol{a}^{1},\boldsymbol{\theta}^{\prime}\rangle\geq\langle\boldsymbol{a}^{*},\boldsymbol{\theta}^{\prime}\rangle\geq\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-M^{*}\epsilon$.

Now we try to choose $I=I_{1}$. For all $\boldsymbol{\theta}^{\prime}_{I_{1}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{1}}-\boldsymbol{\ell}_{I_{1}}\|_{\infty}\leq\epsilon$, consider $\boldsymbol{\theta}^{\prime}=\left(\boldsymbol{\theta}^{\prime}_{I_{1}},\boldsymbol{\theta}_{I_{1}^{c}}(t)\right)$.
We see that $\|\boldsymbol{a}^{1}\left(\boldsymbol{\theta}-\boldsymbol{\ell}\right)\|\leq 2\left(M^{*}-1\right)\epsilon$.
Thus,

$$ $\displaystyle\langle\boldsymbol{a}^{1},\boldsymbol{\theta}^{\prime}\rangle\geq$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-M^{*}\epsilon-2(M^{*}-1)\epsilon$ $\displaystyle=$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-(3M^{*}-2)$ $$

Similarly, we have the following inequalities for any $I_{\boldsymbol{a}^{\prime}}\cap{Z}_{1}=\emptyset$:

$$ $\displaystyle\langle\boldsymbol{a}^{\prime},\boldsymbol{\theta}^{\prime}\rangle=$ $\displaystyle\langle\boldsymbol{a}^{\prime},\boldsymbol{\theta}(t)\rangle$ $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}(t),\boldsymbol{\theta}(t)\rangle$ $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}(t),\boldsymbol{\ell}\rangle+\left(\Delta_{\boldsymbol{a}(t)}-\left({M^{*}}^{2}+1\right)\epsilon\right)$ $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-({M^{*}}^{2}+1)\epsilon$ (35) $\displaystyle<$ $\displaystyle\langle\boldsymbol{a}^{*},\boldsymbol{\ell}\rangle-(3M^{*}-2)$ (36) $\displaystyle\leq$ $\displaystyle\langle\boldsymbol{a}^{1},\boldsymbol{\theta}^{\prime}\rangle$ $$

That is, $I_{\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)}\cap I_{1}\neq\emptyset$. Thus, we will also have two possibilities:

- 2a)
for all $\boldsymbol{\theta}_{I_{1}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{1}}-\boldsymbol{\ell}_{I_{1}}\|_{\infty}\leq\epsilon$, $I_{1}\subseteq I_{\mathsf{Oracle}\left(\boldsymbol{\theta}\right)}$
- 2b)
for some $\boldsymbol{\theta}^{\prime}_{I_{1}}$ with $\|\boldsymbol{\theta}^{\prime}_{I_{1}}-\boldsymbol{\ell}_{I_{1}}\|_{\infty}\leq\epsilon$, $\mathsf{Oracle}\left(\boldsymbol{\theta}^{\prime}\right)=\boldsymbol{a}^{2}$ where $I_{\boldsymbol{a}^{2}}\cap I_{1}=I_{2}$ and $I_{2}\neq I_{1}$, $I_{2}\neq\emptyset$.

We could repeat the above argument and the size of $I_{i}$ is decreased by at least 1.
In the first step, the terms contain $\epsilon$ (in Eq ([33](https://arxiv.org/html/2509.09933v1#A2.E33))) is $M^{*}\epsilon$, and in the second step, the terms contain $\epsilon$ (in Eq ([36](https://arxiv.org/html/2509.09933v1#A2.E36))) becomes $M^{*}\epsilon+2(M^{*}-1)\epsilon=(3M^{*}-2)\epsilon$.
Thus, after at most $|I_{\boldsymbol{a}^{*}}|-1$ steps, this terms is at most

$$ $\displaystyle M^{*}+2\left(M^{*}-1\right)+2\left(M^{*}-2\right)+\cdots+2\times 1={M^{*}}^{2},$ (37) $$

which is still less than $({M^{*}}^{2}+1)\epsilon$ (in Eq ([32](https://arxiv.org/html/2509.09933v1#A2.E32)) or ([35](https://arxiv.org/html/2509.09933v1#A2.E35)) ).
This means that the above analysis works for any steps in the induction procedure. When we reach the end, we could find a $I_{i}\subseteq I_{\boldsymbol{a}^{*}}$ and $I_{i}\neq\emptyset$ such that $\mathcal{E}_{Z_{i},1}\left(\boldsymbol{\theta}\left(t\right)\right)$ occurs.
∎

By Lemma [B.2](https://arxiv.org/html/2509.09933v1#A2.Thmtheorem2), for some nonempty $I$, $\mathcal{E}_{Z,1}\left(\boldsymbol{\theta}(t)\right)$, occurs when $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ happens. Another fact is that $\|\boldsymbol{\theta}_{Z}(t)-\boldsymbol{\ell}_{Z}\|_{\infty}>\epsilon$. The reason is that if $\|\boldsymbol{\theta}_{Z}(t)-\boldsymbol{\ell}_{Z}\|_{\infty}\leq\epsilon$, by definition of the property, either $\boldsymbol{a}(t)\in\mathsf{OPT}$ or $\|\boldsymbol{a}(t)\cdot(\boldsymbol{\theta}-\boldsymbol{\ell})\|_{1}>\Delta_{\boldsymbol{S}(t)}-({M^{*}}^{2}+2)\epsilon$, which means $\lnot\mathcal{R}(t)\land\mathcal{P}(t)$ can not happen. Let $\mathcal{E}_{Z,2}\left(\boldsymbol{\theta}\right)$ be the event $\{\|\boldsymbol{\theta}_{Z}-\boldsymbol{\ell}_{Z}\|_{\infty}>\epsilon\}$. Then, $\lnot\mathcal{R}(t)\land\mathcal{P}(t)\Rightarrow\lor_{Z\subseteq I_{\boldsymbol{a}^{*}},Z\neq\emptyset}\left(\mathcal{E}_{Z,1}\left(\boldsymbol{\theta}\left(t\right)\right)\land\mathcal{E}_{Z,2}\left(\boldsymbol{\theta}(t)\right)\right)$.

Following a similar discussion as that of Wang and Chen [2018], we know that $\sum\limits_{Z\subset I_{\boldsymbol{a}},Z\neq\emptyset}\left(\sum\limits_{t=1}^{T}\mathbb{E}\left[\mathbf{1}\left\{\mathcal{E}_{Z,1}\boldsymbol{\theta}(t))\land\mathcal{E}_{Z,2}(\boldsymbol{\theta}(t)\right\}\right]\right)$,
and therefore, the third term of the RHS of ([14](https://arxiv.org/html/2509.09933v1#A2.E14)) does not depend on $t$.

###### Lemma B.2 .

###### Proof.

#### B.3.4 Sum of All Terms in the RHS of ( 14 )

The regret upper bound of GenCTS is the sum of these three terms, i.e.,

$$ $\displaystyle\mathcal{O}\left(\sum\limits_{i=1}^{d}\frac{\kappa_{r}\log m\log\left(2^{d}|\mathcal{A}|T\right)}{\min\limits_{\boldsymbol{a}:i\in I_{\boldsymbol{a}}}\left(\frac{\Delta_{\boldsymbol{a}}}{\kappa_{r}}-\left({M^{*}}^{2}+2\right)\epsilon\right)}\right),$ (38) $$

where $\epsilon\leq\frac{\Delta_{\mathrm{min}}}{2\kappa_{r}({M^{*}}^{2}+2)}$.

## Appendix C Proof of Theorems in Section 4

Here, provide proof for theorems in Section [4](https://arxiv.org/html/2509.09933v1#S4). We define

$$ $\displaystyle\alpha_{i}(t)=\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-q_{i}(t)\right)^{2}\cdot\min\left\{1,\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}\gamma}\right\}$ (39) $$

### C.1 Preparatory Lemma

We first show a preparatory lemma.

###### Lemma C.1 .

Let $D_{i}^{(1)}$ and $D_{i}^{(2)}$ denote the Bregman divergence associated with $\phi_{i}^{(1)}(x)=-n_{i}\log\frac{x}{n_{i}}$ and $\phi^{(2)}_{i}=n_{i}(1-\frac{y}{n_{i}})\log\left(1-\frac{y}{n_{i}}\right)$, respectively. Then, for any $x\in(0,n_{i})$, we have

$$ $\displaystyle\max_{y\in\mathbb{R}}f_{i}^{(1)}(y)$ $\displaystyle=\max_{y\in\mathbb{R}}\left\{a(x-y)-D^{(1)}_{i}\left(y,x\right)\right\}$ $\displaystyle=n_{i}g\left(a\frac{x}{n_{i}}\right)$ (40) $\displaystyle\max_{y\in\mathbb{R}}f_{i}^{(2)}(y)$ $\displaystyle=\max_{y\in\mathbb{R}}\left\{a(x-y)-D^{(2)}_{i}\left(y,x\right)\right\}$ $\displaystyle=n_{i}\left(1-\frac{x}{n_{i}}\right)h\left(a\right),$ (41) $$

where $g$ and $h$ are defined as

$$ $\displaystyle g\left(x\right)=x-\log\left(x+1\right),h(x)=\exp\left(x\right)-x-1.$ (42) $$

###### Proof.

The derivative of $f_{i}^{(1)}$ is expressed as

$$ $\displaystyle\frac{df_{i}^{(1)}(y)}{dx}=-a+\frac{n_{i}}{y}-\frac{n_{i}}{x}$ $$

As $f_{i}^{(1)}$ is a concave function with respect to $y$, the maximizer $y^{*}$ of $f_{i}^{(1)}$ satisfies $a=\frac{n_{i}}{y^{*}}-\frac{n_{i}}{x}$.
Hence, the maximum value is expressed as

$$ $\displaystyle\max_{y\in\mathbb{R}}f_{i}^{(1)}(y)=$ $\displaystyle f_{i}^{(1)}\left(y^{*}\right)$ $\displaystyle=$ $\displaystyle a\left(x-y^{*}\right)+n_{i}\log\frac{y^{*}}{n_{i}}-n_{i}\log\frac{x}{n_{i}}+n_{i}\frac{x-y^{*}}{x}$ $\displaystyle=$ $\displaystyle-n_{i}\log\frac{x}{y^{*}}+n_{i}\left(\frac{x-y^{*}}{y^{*}}\right)$ $\displaystyle=$ $\displaystyle-n_{i}\left(\log\left(1+a\frac{x}{n_{i}}\right)+a\frac{x}{n_{i}}\right)$ $\displaystyle=$ $\displaystyle n_{i}g\left(a\frac{x}{n_{i}}\right)$ $$

which proves ([40](https://arxiv.org/html/2509.09933v1#A3.E40)).
Similarly, as $f_{i}^{(2)}$ is a concave function with respect to $y$, the maximizer $y^{*}\in\mathbb{R}$ of $f_{i}^{(2)}$ satisfies

$$ $\displaystyle\frac{df_{i}^{(2)}}{dy}(y^{*})$ $\displaystyle=-a+\log\left(1-\frac{y^{*}}{n_{i}}\right)+1-\log\left(1-\frac{x}{n_{i}}\right)-1$ $\displaystyle=0$ (43) $$

Hence, we have

$$ $\displaystyle f_{i}^{(2)}\left(y^{*}\right)=$ $\displaystyle a\left(x-y^{*}\right)-n_{i}\left(1-\frac{y^{*}}{n_{i}}\right)\log\left(1-\frac{y^{*}}{n_{i}}\right)+n_{i}\left(1-\frac{x}{n_{i}}\right)\log\left(1-\frac{x}{n_{i}}\right)$ $\displaystyle-n_{i}\left(y^{*}-x\right)\left(\log\left(1-\frac{x}{n_{i}}\right)+\frac{1}{n_{i}}\right)$ $\displaystyle=$ $\displaystyle n_{i}\left(1-\frac{y^{*}}{n_{i}}\right)-n_{i}\left(1-\frac{x}{n_{i}}\right)-n_{i}\left(1-\frac{x}{n_{i}}\right)\log\left(1-\frac{y^{*}}{n_{i}}\right)$ $\displaystyle+n_{i}\left(1-\frac{x}{n_{i}}\right)\log\left(1-\frac{x}{n_{i}}\right)$ $\displaystyle=$ $\displaystyle n_{i}\left(1-\frac{x}{n_{i}}\right)\left(e^{a}-a-1\right)$ $\displaystyle=$ $\displaystyle n_{i}\left(1-\frac{x}{n_{i}}\right)h\left(a\right)$ $$

which proves ([41](https://arxiv.org/html/2509.09933v1#A3.E41)).
∎

###### Lemma C.1 .

###### Proof.

### C.2 Common Analysis

#### C.2.1 General Regret Upper Bound

Let $D_{t}$ be the Bregman divergence induced by $\psi_{t}$, i.e.,

$$ $\displaystyle D_{t}(\boldsymbol{y},\boldsymbol{x})=\psi_{t}(\boldsymbol{y})-\psi_{t}(\boldsymbol{x})-\langle\nabla\psi_{t}(\boldsymbol{x}),\boldsymbol{y}-\boldsymbol{x}\rangle.$ (44) $$

Then, the regret for OFTRL is bounded as follows.

###### Lemma C.2 .

If $\boldsymbol{x}(t)$ is given by the OFTRL update ([4](https://arxiv.org/html/2509.09933v1#S4.E4)), for any $\boldsymbol{x}^{*}\in\mathcal{X}\cap\mathbb{R}_{+}^{d}$, we have

$$ $\displaystyle\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}(t)-\boldsymbol{x}^{*}\right\rangle$ $\displaystyle\leq\underbrace{\psi_{T+1}\left(\boldsymbol{x}^{*}\right)-\psi_{1}(\boldsymbol{y}(1))+\sum\limits_{t=1}^{T}\left(\psi_{t}\left(\boldsymbol{y}(t+1)\right)-\psi\left(\boldsymbol{y}(t+1)\right)\right)}_{\text{penalty term}}$ $\displaystyle+\underbrace{\sum\limits_{t=1}^{T}\Biggl{(}\left\langle\hat{\boldsymbol{\ell}}(t)-\boldsymbol{q}(t),\boldsymbol{x}(t)-\boldsymbol{y}(t+1)\right\rangle-D_{t}\left(\boldsymbol{y}(t+1),\boldsymbol{x}(t)\right)\Biggr{)}}_{\text{stability term}},$ (45) $$

where we define $\boldsymbol{y}(t)\in\mathop{\rm arg~min}\limits_{\boldsymbol{x}\in\mathcal{X}}\left\{\left\langle\sum\limits_{s=1}^{t-1}\hat{\boldsymbol{\ell}}(s),\boldsymbol{x}\right\rangle+\psi_{t}(\boldsymbol{x})\right\}$.

In the RHS of the above inequality ([45](https://arxiv.org/html/2509.09933v1#A3.E45)), we refer to the sum of the first three terms as the penalty term and the remaining term as the stability term.

First, we prove the following lemma.

###### Lemma C.3 .

The regret of the proposed algorithm is bounded as

$$ $\displaystyle R_{T}\leq$ $\displaystyle\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[2\beta_{i}(T+1)-\beta_{i}(1)+2\delta_{i}\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right]+dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i},$ (46) $$

where $\delta_{i}>0$ is defined by

$$ $\displaystyle\delta_{i}=\frac{1}{3\left(1-\frac{1}{\beta_{i}(1)}\right)}$ $$

###### Proof.

Using $\bar{\boldsymbol{x}}\in\mathcal{X}$ such that $\bar{x}_{i}\geq\frac{n_{i}}{d}$ for all $i\in[d]$, let

$$ $\displaystyle\boldsymbol{x}^{*}=\left(1-\frac{d}{T}\right)\boldsymbol{a}^{*}+\frac{d}{T}\bar{\boldsymbol{x}}.$ $$

Using this and the equality $\mathbb{E}\left[\hat{\boldsymbol{\ell}}(t)|\boldsymbol{x}(t)\right]=\boldsymbol{\ell}$, we have

$$ $\displaystyle R_{T}$ $\displaystyle=\mathbb{E}\left[\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}(t)-\boldsymbol{a}^{*}\right\rangle\right]$ $\displaystyle=\mathbb{E}\left[\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}(t)-\boldsymbol{x}^{*}\right\rangle+\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}^{*}-\boldsymbol{a}^{*}\right\rangle\right]$ $\displaystyle=\mathbb{E}\left[\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}(t)-\boldsymbol{x}^{*}\right\rangle+\frac{d}{T}\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t),\bar{\boldsymbol{x}}-\boldsymbol{a}^{*}\right\rangle\right]$ $\displaystyle\leq\mathbb{E}\left[\langle\hat{\boldsymbol{\ell}}(t),\boldsymbol{x}(t)-\boldsymbol{x}^{*}\right]+dW,$ (47) $$

where in the last inequality, we used $\sum\limits_{t=1}^{T}\langle\hat{\boldsymbol{\ell}}(t),\bar{\boldsymbol{x}}-\boldsymbol{a}\rangle\leq T\|\bar{\boldsymbol{x}}-\boldsymbol{a}^{*}\|_{1}\leq T\sum\limits_{i=1}^{d}n_{i}=TW$.

The first term in ([47](https://arxiv.org/html/2509.09933v1#A3.E47)) is bounded by ([45](https://arxiv.org/html/2509.09933v1#A3.E45)) in Lemma [C.2](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem2), the components of which we will bound in the following. We first consider the penalty term. The remaining part of the proof follows a similar argument as that in Ito et al. [2022a] and Tsuchiya et al. [2023], and we include the argument for completeness.

Bounding the penalty term in ([45](https://arxiv.org/html/2509.09933v1#A3.E45)) Using the definition of the regularizer $\psi_{t}\left(\boldsymbol{x}\right)=\sum\limits_{i=1}^{d}\beta_{i}(t)\varphi_{i}\left(x_{i}\right)$, we have

$$ $\displaystyle\psi_{t}\left(\boldsymbol{x}^{*}\right)$ $\displaystyle=\sum\limits_{i=1}^{d}\beta_{i}(t)\varphi_{i}\left({x}_{i}^{*}\right)$ $\displaystyle\leq\sum\limits_{i=1}^{d}\beta_{i}(t)\max_{\boldsymbol{x}\in\left[\frac{n_{i}}{T},n_{i}\right]}\varphi_{i}\left(\boldsymbol{x}\right)$ $\displaystyle\leq\sum\limits_{i=1}^{d}\beta_{i}(t)\max\left\{\varphi_{i}\left(\frac{n_{i}}{T}\right),\varphi_{i}(n_{i})\right\},$ (48) $$

where the first inequality follows since the definition of $\boldsymbol{x}^{*}$ implies ${x}^{*}_{i}\geq\frac{d}{T}\bar{x}_{i}\geq\frac{n_{i}}{T}$ for $i\in[d]$ and the second inequality holds since $\varphi_{i}$ is a convex function. Further, from the definition of $\varphi_{i}$, we have

$$ $\displaystyle\max\left\{\varphi_{i}\left(\frac{n_{i}}{T}\right),\varphi_{i}\left(n_{i}\right)\right\}=$ $\displaystyle n_{i}\cdot\max\Biggl{\{}\frac{1}{T}-1+\log T+\gamma\left(\frac{1}{T}+\left(1-\frac{1}{T}\right)\log\left(1-\frac{1}{T}\right)\right),\gamma\Biggr{\}}$ $\displaystyle\leq$ $\displaystyle n_{i}\cdot\max\left\{\frac{1+\gamma}{T}-1+\log T,\gamma\right\}$ $\displaystyle=$ $\displaystyle n_{i}\gamma,$ (49) $$

where the last inequality follows from $\gamma=\log T$. From this and ([48](https://arxiv.org/html/2509.09933v1#A3.E48)), we have

$$ $\displaystyle\psi_{T+1}\left(\boldsymbol{x}^{*}\right)\leq\gamma\sum\limits_{i=1}^{d}n_{i}\beta_{i}(T+1).$ (50) $$

Further, as we have $\beta_{i}(t)\leq\beta_{i}(t+1)$ from ([10](https://arxiv.org/html/2509.09933v1#S4.E10)) and $\varphi_{i}\left(x\right)\geq 0$ for any $x\in(0,n_{i}]$, we have

$$ $\displaystyle-\psi_{1}\left(\boldsymbol{y}(1)\right)+\sum\limits_{t=1}^{T}\left(\psi_{t}\left(\boldsymbol{y}\left(t+1\right)\right)-\psi_{t+1}\left(\boldsymbol{y}(t+1)\right)\right)$ $\displaystyle=$ $\displaystyle-\sum\limits_{i=1}^{d}\Biggl{(}\beta_{i}(1)\varphi_{i}\left(y_{i}(1)\right)+\sum\limits_{t=1}^{T}\left(\beta_{i}(t+1)-\beta_{i}(t)\right)\varphi_{i}\left({y}_{i}(t+1)\right)\Biggr{)}$ $\displaystyle\leq$ $\displaystyle 0.$ (51) $$

Combining ([50](https://arxiv.org/html/2509.09933v1#A3.E50)) and ([51](https://arxiv.org/html/2509.09933v1#A3.E51)), we can bound the penalty term in ([45](https://arxiv.org/html/2509.09933v1#A3.E45)) as

$$ $\displaystyle\psi_{T+1}\left(\boldsymbol{x}^{*}\right)-\psi_{1}\left(\boldsymbol{y}(1)\right)+\sum\limits_{t=1}^{T}\left(\psi_{t}\left(\boldsymbol{y}\left(t+1\right)\right)-\psi_{t+1}\left(\boldsymbol{y}\left(t+1\right)\right)\right)$ $\displaystyle\leq$ $\displaystyle\gamma\sum\limits_{i=1}^{d}n_{i}\beta_{i}\left(T+1\right).$ (52) $$

Bounding the stability term in ([45](https://arxiv.org/html/2509.09933v1#A3.E45))
The Bregman divergence $D_{t}(\boldsymbol{x},\boldsymbol{y})$ is expressed as

$$ $\displaystyle D_{t}\left(\boldsymbol{x},\boldsymbol{y}\right)$ $\displaystyle=\sum\limits_{i=1}^{d}\left(\beta_{i}\left(t\right)D_{i}^{(1)}(x_{i},y_{i})+\beta_{i}(t)\gamma D^{(2)}_{i}(x_{i},y_{i})\right)$ $\displaystyle\geq\sum\limits_{i=1}^{d}\max\left\{\beta_{i}(t)D_{i}^{(1)}(x_{i},y_{i}),\beta_{i}(t)\gamma D^{(2)}_{i}\left(x_{i},y_{i}\right)\right\}$ (53) $$

where $D_{i}^{(1)}$ and $D_{i}^{(2)}$ are Bregman divergence induced by $\varphi_{i}(x)=-n_{i}\log\left(\frac{x}{n_{i}}\right)$ and $\varphi_{i}^{(2)}(x)=n_{i}\left(1-\frac{x}{n_{i}}\right)\log\left(1-\frac{x}{n_{i}}\right)$, respectively. Let $g=x-\log(x+1)$ and $h=\exp(x)-x-1$. Since, $\delta_{i}\geq\frac{1}{3\left(1-\frac{1}{\beta_{i}(1)}\right)}$ for all $i\in[d]$, from a simple calculation, we have

$$ $\displaystyle g(x)$ $\displaystyle=x-\log(x+1)\leq\frac{1}{2}x^{2}+\delta_{i}|x|^{3}\quad\left(x\geq-\frac{1}{\beta_{i}(1)}\right)$ (54) $$

and

$$ $\displaystyle h(x)$ $\displaystyle=\exp(x)-x-1\leq x^{2}\quad\left(x\leq 1\right)$ (55) $$

for all $i\in[d]$.
Then, we have

$$ $\displaystyle\left\langle\hat{\boldsymbol{\ell}}(t)-\boldsymbol{q}(t),\boldsymbol{x}(t)-\boldsymbol{y}(t+1)\right\rangle-D_{t}\left(\boldsymbol{y}(t+1),\boldsymbol{x}(t)\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}\left(\hat{l}_{i}\left(t\right)-q_{i}(t)\right)\left(x_{i}(t)-y_{i}(t+1)\right)-\beta_{i}(t)\max\Biggl{\{}D_{i}^{(1)}\left(y_{i}(t+1),x_{i}(t)\right),\gamma D_{i}^{(2)}\left(y_{i}(t+1),x_{i}(t)\right)\Biggr{\}}$ $\displaystyle=$ $\displaystyle\sum\limits_{i=1}^{d}\beta_{i}(t)\left\{\frac{\hat{l}_{i}\left(t\right)-q_{i}(t)}{\beta_{i}(t)}\left(x_{i}(t)-y_{i}(t+1)\right)-\max\Biggl{\{}D_{i}^{(1)}\left(y_{i}(t+1),x_{i}(t)\right),\gamma D_{i}^{(2)}\left(y_{i}(t+1),x_{i}(t)\right)\Biggr{\}}\right\}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}\beta_{i}\left(t\right)\min\Biggl{\{}n_{i}g_{i}\left(\frac{\hat{l}_{i}(t)-q_{i}(t)}{\beta_{i}(t)}\frac{x_{i}(t)}{n_{i}}\right),\gamma n_{i}\left(1-\frac{x}{n_{i}}\right)h\left(\frac{\hat{l}_{i}(t)-q_{i}(t)}{\gamma\beta_{i}(t)}\right)\Biggr{\}},$ (56) $$

where the last inequality follows from Lemma [C.1](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem1).

Note that $g(0)=h(0)=0$ and it holds that

$$ $\displaystyle\hat{l}_{i}(t)-q_{i}(t)$ $\displaystyle=\left\{\begin{array}[]{ll}\frac{a_{i}(t)}{x_{i}(t)}\left(k_{i}(t)-q_{i}(t)\right)&\text{if $a_{i}(t)\geq 1$}\\ 0&\text{if}\ a_{i}=0\end{array}.\right.$ (59) $$

Therefore, the LHS of ([56](https://arxiv.org/html/2509.09933v1#A3.E56)) is further bounded as

$$ $\displaystyle\left\langle\hat{\boldsymbol{\ell}}(t)-\boldsymbol{q}(t),\boldsymbol{x}(t)-\boldsymbol{y}(t+1)\right\rangle-D_{t}\left(\boldsymbol{y}(t+1),\boldsymbol{x}(t)\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}\beta_{i}\left(t\right)\min\Biggl{\{}n_{i}g\left(\frac{\frac{a_{i}(t)}{x_{i}(t)}\left(k_{i}(t)-q_{i}(t)\right)}{\beta_{i}(t)}\frac{x_{i}(t)}{n_{i}}\right),\gamma n_{i}\left(1-\frac{x}{n_{i}}\right)h\left(\frac{\frac{a_{i}(t)}{x_{i}(t)}\left(k_{i}(t)-q_{i}(t)\right)}{\gamma\beta_{i}(t)}\right)\Biggr{\}}$ $\displaystyle\leq$ $\displaystyle\left\{\begin{array}[]{lr}\sum\limits_{i=1}^{d}\frac{1}{n_{i}}\Biggl{(}\frac{a^{2}_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)^{2}}{2\beta_{i}(t)}+\frac{\delta_{i}a^{3}_{i}(t)\left|k_{i}(t)-q_{i}(t)\right|^{3}}{n_{i}\beta^{2}_{i}(t)}\Biggr{)}&\mathrm{if}\ \gamma\frac{x_{i}(t)}{a_{i}(t)}\leq 1\\ \sum\limits_{i=1}\frac{1}{n_{i}}\min\Biggl{\{}\frac{a^{2}_{i}(t)\left(k_{i}(t)-m_{j}(t)\right)^{2}}{2\beta_{i}(t)}+\frac{\delta_{i}a^{3}_{i}(t)\left|k_{i}(t)-q_{i}(t)\right|^{3}}{n_{i}\beta^{2}_{i}(t)},\frac{\left(1-\frac{x_{i}(t)}{n_{i}}\right)a^{2}_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)^{2}}{\gamma\left({\frac{x_{i}(t)}{n_{i}}}\right)^{2}\beta_{i}(t)}\Biggr{\}}&\mathrm{otherwise}\end{array}\right.$ (62) $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}\frac{1}{n_{i}}\min\Biggl{\{}\frac{\left(a^{2}_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)\right)^{2}}{2\beta_{i}(t)}+\delta_{i}\frac{a^{3}_{i}(t)\left|\left(k_{i}(t)-q_{i}(t)\right)\right|^{3}}{n_{i}\beta^{2}_{i}\left(t\right)},\left(1-\frac{x}{n_{i}}\right)\frac{a^{2}_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)^{2}}{\gamma\beta_{i}(t)\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\Biggr{\}}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}\frac{1}{n_{i}}\left(\frac{1}{2\beta_{i}(t)}+\frac{\delta}{n_{i}\beta^{2}_{i}(t)}\right)\cdot a^{2}_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)^{2}\min\left\{1,\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\right\}$ $\displaystyle=$ $\displaystyle\sum\limits_{i=1}^{d}n_{i}\left(\frac{1}{2\beta_{i}(t)}+\frac{1}{\beta^{2}_{i}(t)}\right)\alpha_{i}(t)$ (63) $$

where the first inequality follows from ([56](https://arxiv.org/html/2509.09933v1#A3.E56)) and ([59](https://arxiv.org/html/2509.09933v1#A3.E59)), the second inequality follows from ([54](https://arxiv.org/html/2509.09933v1#A3.E54)), ([55](https://arxiv.org/html/2509.09933v1#A3.E55)), and the fact that $\left|\frac{\left(k_{i}(t)-q_{i}(t)\right)}{\beta_{i}(t)}\right|\leq\frac{1}{\beta_{i}(1)}\leq 1$, and third inequality holds since $\gamma\frac{x_{i}(t)}{a_{i}(t)}\leq 1$ means $\frac{1-\frac{x_{i}(t)}{n_{i}}}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\geq\frac{1-\frac{x_{i}(t)}{a_{i}(t)}}{\gamma\left(\frac{x_{i}(t)}{a_{i}(t)}\right)^{2}}\geq\frac{1-\frac{1}{\gamma}}{\gamma\left(\frac{1}{\gamma}\right)^{2}}=\gamma-1\geq\frac{1}{2}+\delta_{i}$, which implies

$$ $\displaystyle\frac{\left(k_{i}(t)-q_{i}(t)\right)^{2}}{2\beta_{i}(t)}+\frac{\delta_{i}a_{i}(t)\left|k_{i}(t)-q_{i}(t)\right|^{3}}{n_{i}\beta^{2}_{i}(t)}\leq$ $\displaystyle\frac{\left(k_{i}(t)-q_{i}(t)\right)^{2}}{2\beta_{i}(t)}+\frac{\delta_{i}\left|k_{i}(t)-q_{i}(t)\right|^{3}}{\beta_{i}(t)}$ $\displaystyle=$ $\displaystyle\frac{1}{\beta_{i}(t)}\left(\frac{1}{2}+\delta_{i}\right)\left(k_{i}(t)-q_{i}(t)\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{\beta_{i}(t)}\frac{1-\frac{x_{i}(t)}{n_{i}}}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\left(k_{i}(t)-q_{i}(t)\right)^{2}.$ $$

We hence have

$$ $\displaystyle\sum\limits_{t=1}^{T}\left(\left\langle\hat{\boldsymbol{\ell}}(t)-\boldsymbol{q}(t),\boldsymbol{x}(t)-\boldsymbol{y}(t+1)\right\rangle-D_{t}\left(\boldsymbol{y}(t+1),\boldsymbol{x}(t)\right)\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i=1}^{d}n_{i}\sum\limits_{t=1}^{T}\left(\frac{1}{2\beta_{i}(t)}+\frac{\delta_{i}}{\beta^{2}_{i}(t)}\right)\alpha_{i}(t).$ (64) $$

We can show that a part of ([64](https://arxiv.org/html/2509.09933v1#A3.E64)) is bounded as

$$ $\displaystyle\sum\limits_{t=1}^{T}\frac{\alpha_{i}(t)}{2\beta_{i}(t)}$ $\displaystyle\leq$ $\displaystyle\gamma\left(\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}}\right)$ $\displaystyle\leq$ $\displaystyle\gamma\left(\beta_{i}\left(T+1\right)-\beta_{i}(1)\right).$ (65) $$

The first inequality in ([65](https://arxiv.org/html/2509.09933v1#A3.E65)) holds since

$$ $\displaystyle\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{t=1}^{t}\alpha_{i}(t)}-\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{t=1}^{t-1}\alpha_{i}(t)}$ $\displaystyle=$ $\displaystyle\frac{1}{\gamma}\cdot\frac{\alpha_{i}(t)}{\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{s=1}^{t}\alpha_{i}(s)}+\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\gamma\sum\limits_{s=1}^{t-1}\alpha_{i}(s)}}$ (66) $\displaystyle\geq$ $\displaystyle\frac{\alpha_{i}(t)}{2\gamma\sqrt{\beta^{2}_{i}(1)+\frac{1}{\gamma}\sum\limits_{s=1}^{t-1}\alpha_{i}(s)}}$ (67) $\displaystyle=$ $\displaystyle\frac{\alpha_{i}(t)}{2\gamma\beta_{i}(t)},$ (68) $$

where the inequality follows by $\alpha_{i}(t)\leq 1$. The second inequality in ([65](https://arxiv.org/html/2509.09933v1#A3.E65)) follows since

$$ $\displaystyle\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}}$ (69) $\displaystyle\leq$ $\displaystyle\sqrt{\beta^{2}_{i}(1)-\frac{1}{\gamma}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\beta_{i}(1)+\frac{1}{\gamma}$ (70) $\displaystyle\leq$ $\displaystyle\beta_{i}(T+1)-\beta_{i}(1)+\frac{1}{\gamma},$ (71) $$

where the first inequality follows from $\sqrt{x}-\sqrt{x-y}\leq\frac{y}{\sqrt{x}}$ for $x\geq y\geq 0$ and $\beta_{i}(1)\geq 1$.

Similarly, we can show

$$ $\displaystyle\sum\limits_{t=1}^{T}\frac{\alpha_{i}(t)}{\beta^{2}_{i}(t)}=$ $\displaystyle\sum\limits_{t=1}^{T}\frac{\alpha_{i}(t)}{\beta^{2}_{i}(1)+\frac{1}{\gamma}\sum\limits_{s=1}^{t-1}\alpha_{i}(s)}$ $\displaystyle=$ $\displaystyle\gamma\sum\limits_{t=1}^{T}\frac{\alpha_{i}(t)}{\gamma\beta^{2}_{i}(1)+\sum\limits_{s=1}^{t-1}\alpha_{i}(s)}$ $\displaystyle\leq$ $\displaystyle\gamma\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)-1}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)$ (72) $\displaystyle\leq$ $\displaystyle 2\gamma\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}+2.$ (73) $$

The first inequality in ([73](https://arxiv.org/html/2509.09933v1#A3.E73)) follows since

$$ $\displaystyle\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)-1}\sum\limits_{s=1}^{t}\alpha_{i}(s)\right)-\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)-1}\sum\limits_{s=1}^{t-1}\alpha_{i}(s)\right)$ $\displaystyle=$ $\displaystyle-\log\left(1-\frac{\alpha_{i}(t)}{\gamma\beta^{2}_{i}(1)-1+\sum\limits_{s=1}^{t}\alpha_{i}(s)}\right)$ (74) $\displaystyle\geq$ $\displaystyle-\log\left(1-\frac{\alpha_{i}(t)}{\gamma\beta^{2}_{i}(1)+\sum\limits_{s=1}^{t-1}\alpha_{i}(s)}\right)$ (75) $\displaystyle\geq$ $\displaystyle\frac{\alpha_{i}(t)}{\gamma\beta^{2}_{i}(1)+\sum\limits_{s=1}^{t-1}\alpha_{i}(s)},$ (76) $$

where the first inequality follows from $\alpha_{i}(t)\leq 1$ and the last inequality follows from $-\log(1-x)\geq x$ for $x<1$. The second inequality in ([73](https://arxiv.org/html/2509.09933v1#A3.E73)) follows from

$$ $\displaystyle\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)-1}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)$ $\displaystyle<$ $\displaystyle\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)+\log\frac{\gamma\beta^{2}_{i}(1)}{\gamma\beta^{2}_{i}(1)-1}$ (77) $\displaystyle=$ $\displaystyle\log\left(\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right)+\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)-1}\right)$ (78) $\displaystyle\leq$ $\displaystyle 2\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}+\frac{2}{\gamma}$ (79) $$

where the last inequality follows from $\log(1+\frac{1}{x-1})\geq\frac{2}{x}$ for $x\geq 3/2$. Bounding the RHS of ([63](https://arxiv.org/html/2509.09933v1#A3.E63)) with ([65](https://arxiv.org/html/2509.09933v1#A3.E65)) and ([73](https://arxiv.org/html/2509.09933v1#A3.E73)) yields

$$ $\displaystyle\sum\limits_{t=1}^{T}\left\langle\hat{\boldsymbol{\ell}}(t)-\boldsymbol{q}(t),\boldsymbol{x}(t)-\boldsymbol{y}(t+1)\right\rangle-D_{t}\left(\boldsymbol{y}(t+1),\boldsymbol{x}(t)\right)$ $\displaystyle\leq$ $\displaystyle\gamma\sum\limits_{i=1}^{d}n_{i}\left(\beta_{i}(T+1)-\beta_{i}(1)+2\delta_{i}\log\frac{\beta_{i}(T+1)}{\beta_{1}}\right)+2\sum\limits_{i=1}^{d}n_{i}\delta_{i}$ (80) $$

Finally, by bounding the RHS of ([45](https://arxiv.org/html/2509.09933v1#A3.E45)) and sequentially using ([47](https://arxiv.org/html/2509.09933v1#A3.E47)), ([52](https://arxiv.org/html/2509.09933v1#A3.E52)) and ([80](https://arxiv.org/html/2509.09933v1#A3.E80)), we have

$$ $\displaystyle R_{T}\leq$ $\displaystyle\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[2\beta_{i}(T+1)-\beta_{i}(1)+2\delta_{i}\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right]+dW+2\sum\limits_{i=1}^{d}n_{i}\delta_{i},$ (81) $$

which completes the proof.
∎

###### Lemma C.2 .

###### Lemma C.3 .

###### Proof.

#### C.2.2 A Lower Bound

Below, we define

$$ $\displaystyle\Delta^{\prime}_{i,\mathrm{min}}=\min_{\boldsymbol{a}\in\mathcal{A}\setminus\{\boldsymbol{a}^{*}\}}\left\{\boldsymbol{a}^{\top}\boldsymbol{\ell}-{\boldsymbol{a}^{*}}^{\top}\boldsymbol{\ell}:a_{i}=0\right\}.$ (82) $$

To obtain the regret upper bound depending on $\Delta_{i}$ in the stochastic regime and the stochastic regime with adversarial corruptions, we prove the following regret *lower bound*.

###### Lemma C.4 .

In the stochastic regime with adversarial corruptions, for any algorithm and any action set $\mathcal{A}$, the regret is bounded as

$$ $\displaystyle R_{T}\geq\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\Biggl{(}\frac{1}{\lambda_{\mathcal{A}}^{\prime}}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}\left(a^{*}_{i}-a_{i}(t)\right)+\frac{1}{\lambda_{\mathcal{A}}}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}a_{i}(t)\Biggr{)}\Biggr{]}-2CM,$ (83) $$

where $\lambda_{\mathcal{A}}^{\prime}=\min\left\{W_{I^{*}},W-M\right\}$.

###### Proof.

We can bound the regret as

$$ $\displaystyle R_{T}$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L_{i,j}(t)\right)\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L^{\prime}_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L^{\prime}_{i,j}(t)\right)+\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L^{\prime}_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L^{\prime}_{i,j}(t)\right)\Biggr{]}$ $\displaystyle\geq$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L^{\prime}_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L^{\prime}_{i,j}(t)\right)\Biggr{]}-\sum\limits_{t=1}^{T}\left|\max\limits_{i\in[d],j\in[n_{i}]}L_{i,j}(t)-L^{\prime}_{i,j}(t)\right|\|\boldsymbol{a}(t)-\boldsymbol{a}^{*}\|_{1}$ $\displaystyle\geq$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L^{\prime}_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L^{\prime}_{i,j}(t)\right)\Biggr{]}-2MC,$ (84) $$

where the first inequality follows from the Hölder’s inequality, the second inequality follows since $\|\boldsymbol{a}(t)-\boldsymbol{a}^{*}\|_{1}\leq 2M$, and the last inequality follows from the definition of $C=\mathbb{E}\left[\sum_{t=1}^{T}\max\limits_{i\in[d]}\max\limits_{j\in[n_{i}]}\left|L_{i,j}(t)-L^{\prime}_{i,j}(t)\right|\right]\geq 0$. We then bound $\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}(t)}L^{\prime}_{i,j}(t)-\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a^{*}_{i}(t)}L^{\prime}_{i,j}(t)\right)\Biggr{]}$.

Below, we write $\langle\boldsymbol{L},\boldsymbol{a}\rangle=\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{a_{i}}L_{i,j}(t)$. We have $\langle\boldsymbol{L},\boldsymbol{a}\rangle-\langle\boldsymbol{L},\boldsymbol{a}^{\prime}\rangle=\langle\boldsymbol{L},\boldsymbol{a}-\boldsymbol{a}^{\prime}\rangle$.

We consider the case of general action sets and recall that $I^{*}:=\{i\in[d]:\ {a}^{*}_{i}\geq 1\}$ and $J^{*}=[d]\setminus I^{*}$. Since $\sum\limits_{i\in I^{*}}(a^{*}_{i}-a_{i}(t))\leq M^{*}$ and $\sum\limits_{i\in J^{*}}a_{i}(t)\leq M$, we have

$$ $\displaystyle\left\langle\boldsymbol{L},\boldsymbol{a}(t)-\boldsymbol{a}^{*}\right\rangle$ $\displaystyle=$ $\displaystyle\frac{1}{2}\left\langle\boldsymbol{L},\boldsymbol{a}(t)-\boldsymbol{a}^{*}\right\rangle+\frac{1}{2}\left\langle\boldsymbol{L},\boldsymbol{a}(t)-\boldsymbol{a}^{*}\right\rangle$ $\displaystyle\geq$ $\displaystyle\frac{1}{2\min\left\{W_{I^{*}},W-M\right\}}\sum\limits_{i\in I^{*}}\left(n_{i}-{a}_{i}(t)\right)\left\langle\boldsymbol{L},\boldsymbol{a}(t)-\boldsymbol{a}^{*}\right\rangle$ $\displaystyle+\frac{1}{2\min\left\{W_{J^{*}},M\right\}}\sum\limits_{i\in J^{*}}a_{i}(t)\left\langle\boldsymbol{L},\boldsymbol{a}(t)-\boldsymbol{a}^{*}\right\rangle$ $\displaystyle\geq$ $\displaystyle\frac{1}{2\min\left\{W_{I^{*}},W-M\right\}}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}\left(n_{i}-{a}_{i}(t)\right)+\frac{1}{2\min\left\{W_{J^{*}},M\right\}}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}a_{i}(t).$ $$

Combining this inequality with ([84](https://arxiv.org/html/2509.09933v1#A3.E84))
completes the proof.
∎

Note that in the stochastic regime with adversarial corruptions, from Lemma [C.4](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem4), it holds that

$$ $\displaystyle R_{T}\geq$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\Biggl{(}\frac{1}{2M^{*}}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}\left(a^{*}_{i}-{a}_{i}(t)\right)+\frac{1}{2M}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}a_{i}(t)\Biggr{)}\Biggr{]}-2CM$ $\displaystyle=$ $\displaystyle\frac{1}{2M^{*}}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}Q_{i}+\frac{1}{2M}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}P_{i}-2CM,$ (85) $$

where equality follows from the law of iterated expectations.

###### Lemma C.4 .

###### Proof.

### C.3 Proof for the LS Method

In this section, we provide proof for the results of the LS Method.

#### C.3.1 Preliminaries

We use the following lemma to bound $\sum\limits_{t=1}^{T}\alpha_{i}(t)$ for suboptimal arms $i\in J^{*}$.

###### Lemma C.5 .

It holds for any $i\in[d]$ and $q_{i}^{*}\in[0,1]$ that

$$ $\displaystyle\sum\limits_{t=1}^{T}\alpha_{i}(t)\leq$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-q_{i}(t)\right)^{2}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-m^{*}\right)^{2}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)+\frac{5}{4}$ (86) $$

To prove this lemma, we use the following lemma.

###### Lemma C.6 .

Suppose $k_{i}(s)\in[0,1]$ for any $s\in[t]$, and define $q_{i}(t)\in[0,1]$ by

$$ $\displaystyle q_{i}(t)=\frac{1}{1+\sum\limits_{s=1}^{t-1}a_{i}(s)}\left(\frac{1}{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)k_{i}(s)\right).$ (87) $$

We then have

$$ $\displaystyle\sum\limits_{t=1}^{T}a_{i}(t)\left(\left(k_{i}(t)-q_{i}(t)\right)^{2}-\left(k_{i}(t)-m^{*}\right)^{2}\right)\leq\frac{5}{4}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)$ (88) $$

for any $m^{*}\in[0,1]$.

###### Proof.

From the definition of $q_{i}(t)$, $q_{i}(t)$ is expressed as

$$ $\displaystyle q_{i}(t)\in\mathop{\rm arg~min}\limits_{m\in\mathbb{R}}\left\{\left(m-\frac{1}{2}\right)^{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(m-k_{i}(s)\right)^{2}\right\},$ (89) $$

which implies

$$ $\displaystyle q_{i}(t)-\frac{1}{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(q_{i}(t)-k_{i}(s)\right)=0.$ (90) $$

We have

$$ $\displaystyle\left(m-\frac{1}{2}\right)^{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(m-k_{i}(s)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(m-q_{i}(t)+q_{i}(t)-\frac{1}{2}\right)^{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(m-q_{i}(t)+q_{i}(t)-k_{i}(s)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(m-q_{i}(t)\right)^{2}+2\left(m-q_{i}(t)\right)\left(q_{i}(t)-\frac{1}{2}\right)+\left(q_{i}(t)-\frac{1}{2}\right)^{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(m-q_{i}(t)\right)^{2}$ $\displaystyle+2\left(m-q_{i}(t)\right)\sum\limits_{s=1}^{t-1}a_{i}(s)\left(q_{i}(t)-k_{i}(s)\right)+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(q_{i}(t)-k_{i}(s)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(t)-\frac{1}{2}\right)^{2}+\left(\sum\limits_{s=1}^{t-1}a_{i}(s)+1\right)\left(m-q_{i}(t)\right)^{2}+\sum\limits_{s=1}^{t-1}a_{i}(s)\left(q_{i}(t)-k_{i}(s)\right)^{2}$ (91) $$

for any $m\in\mathbb{R}$. The third equality follows from ([90](https://arxiv.org/html/2509.09933v1#A3.E90)).
Using this, for any $m^{*}$, we obtain

$$ $\displaystyle\left(m^{*}-\frac{1}{2}\right)^{2}+\sum\limits_{t=1}^{T}a_{i}(t)\left(k_{i}(t)-m^{*}\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(T+1)-\frac{1}{2}\right)^{2}+\left(\sum\limits_{t=1}^{T}a_{i}(t)+1\right)\left(m^{*}-q_{i}(T+1)\right)^{2}+\sum\limits_{t=1}^{T}a_{i}(t)\left(q_{i}(T+1)-k_{i}(t)\right)^{2}$ $\displaystyle\geq$ $\displaystyle\left(q_{i}(T+1)-\frac{1}{2}\right)^{2}+\sum\limits_{t=1}^{T}a_{i}(t)\left(q_{i}(T+1)-k_{i}(t)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(T+1)-\frac{1}{2}\right)^{2}+\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(T+1)-k_{i}(t)\right)^{2}+a_{i}(T)\left(q_{i}(T+1)-k_{i}(T)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(T+1)-q_{i}(T)+q_{i}(T)-\frac{1}{2}\right)^{2}+\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(T+1)-q_{i}(T)+q_{i}(T)-k_{i}(t)\right)^{2}$ $\displaystyle+a_{i}(T)\left(q_{i}(T+1)-k_{i}(T)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(T+1)-q_{i}(T)\right)^{2}+2\left(q_{i}(T+1)-q_{i}(T)\right)\left(q_{i}(T)-\frac{1}{2}\right)+\left(q_{i}(T)-\frac{1}{2}\right)^{2}$ $\displaystyle+\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(T+1)-q_{i}(T)\right)^{2}+2\left(q_{i}(T+1)-q_{i}(T)\right)\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(t)-l_{ij}(t)\right)$ $\displaystyle+\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(T)-k_{i}(t)\right)^{2}+a_{i}(T)\left(q_{i}(T+1)-k_{i}(T)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(T)-\frac{1}{2}\right)^{2}+\left(\sum\limits_{t=1}^{T-1}a_{i}(t)+1\right)\left(q_{i}(T+1)-q_{i}(T)\right)^{2}+\sum\limits_{t=1}^{T-1}a_{i}(t)\left(q_{i}(T)-k_{i}(t)\right)^{2}$ $\displaystyle+a_{i}(T)\left(q_{i}(T+1)-k_{i}(T)\right)^{2}$ $\displaystyle=$ $\displaystyle\left(q_{i}(1)-\frac{1}{2}\right)^{2}+\sum\limits_{t=1}^{T}a_{i}(t)\left(k_{i}(t)-q_{i}(t+1)\right)^{2}+\sum\limits_{t=1}^{T}\left(1+\sum\limits_{s=1}^{t-1}a_{i}(s)\right)\left(q_{i}(t+1)-q_{i}(t)\right)$ (92) $$

where the first and fifth inequalities follow from ([91](https://arxiv.org/html/2509.09933v1#A3.E91)), and the last equality can be shown by repeating the same transformation $T$ times.
Hence, for any $m^{*}\in\mathbb{R}$, we have

$$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(\left(q_{i}(t)-k_{i}(t)\right)^{2}-\left(k_{i}(t)-m^{*}\right)^{2}\right)$ $\displaystyle\leq$ $\displaystyle\frac{1}{n_{i}}\sum\limits_{t=1}^{T}a_{i}(t)\left(\left(q_{i}(t)-k_{i}(t)\right)^{2}-\left(k_{i}(t)-m^{*}\right)^{2}\right)$ $\displaystyle\leq$ $\displaystyle\frac{1}{n_{i}}\sum\limits_{t=1}^{T}a_{i}(t)\left(q_{i}(t)-k_{i}(t)\right)^{2}$ $\displaystyle-\frac{1}{n_{i}}\Biggl{(}\sum\limits_{t=1}^{T}a_{i}(t)\left(q_{i}(t+1)-k_{i}(t)\right)^{2}+\sum\limits_{t=1}^{T}\left(\sum\limits_{s=1}^{t-1}a_{i}(s)+1\right)\left(q_{i}(t+1)-q_{i}(t)\right)^{2}\Biggr{)}$ $\displaystyle+\frac{1}{n_{i}}\left(m^{*}-\frac{1}{2}\right)^{2}$ $\displaystyle=$ $\displaystyle\frac{1}{n_{i}}\sum\limits_{t=1}^{T}\left(a_{i}(t)\left(q_{i}(t)-k_{i}(t)\right)^{2}-a_{i}(t)\left(q_{i}(t+1)-k_{i}(t)\right)^{2}+\left(\sum\limits_{s=1}^{t-1}a_{i}(s)+1\right)\left(q_{i}(t+1)-q_{i}(t)\right)^{2}\right)$ $\displaystyle+\frac{1}{n_{i}}\left(m^{*}-\frac{1}{2}\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{n_{i}}\sum\limits_{t=1}^{T}\Biggl{(}a_{i}(t)\left(2k_{i}(t)-q_{i}(t)-q_{i}(t+1)\right)\left(q_{i}(t+1)-q_{i}(t)\right)-\left(\sum\limits_{s=1}^{t-1}a_{i}(s)+1\right)\left(q_{i}(t+1)-q_{i}(t)\right)\Biggr{)}$ $\displaystyle+\frac{1}{n_{i}}\left(m^{*}-\frac{1}{2}\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{n_{i}}\sum\limits_{t=1}^{T}\frac{a^{2}_{i}(t)}{4\left(1+\sum\limits_{s=1}^{t-1}a_{i}(s)\right)}\left(2k_{i}(t)-q_{i}(t)-q_{i}(t+1)\right)^{2}+\frac{1}{n_{i}}\left(m^{*}-\frac{1}{2}\right)^{2}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\frac{a_{i}(t)}{\left(1+\sum\limits_{s=1}^{t-1}a_{i}(s)\right)}+\left(m^{*}-\frac{1}{2}\right)^{2}$ $\displaystyle\leq$ $\displaystyle\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)+\frac{5}{4}$ (93) $$

where the second equality follows from $ax-tx^{2}=\frac{a^{2}}{4t}-\left(\frac{a}{2\sqrt{t}}-\sqrt{t}x\right)^{2}\leq\frac{a^{2}}{4t}$ that holds for any $a,x\in\mathbb{R}$, and the forth inequality holds since $\left|2k_{i}(t)-m(t)-m(t+1)\right|\leq 2$, which follows from $k_{i}(t),m(t)\in[0,1]$.
∎

###### Proof of Lemma C.5 .

$$ $\displaystyle\sum\limits_{t=1}^{T}\alpha_{i}(t)$ $\displaystyle=$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\Biggl{(}k_{i}(t)-q_{i}(t)\Biggr{)}^{2}\cdot\min\left\{1,\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}\gamma}\right\}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\Biggl{(}k_{i}(t)-q_{i}(t)\Biggr{)}^{2}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-m^{*}\right)^{2}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)+\frac{5}{4}$ (94) $$

where the second inequality follows from Lemma [C.6](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem6).
∎

From Lemma [C.5](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem5), in the stochastic regime, it holds that

$$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\alpha_{i}(t)\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\frac{a^{2}_{i}(t)}{n^{2}_{i}}\cdot\frac{\sigma_{i}^{2}}{a_{i}(t)}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)\right]+\frac{5}{4}$ $\displaystyle\leq$ $\displaystyle\frac{\sigma_{i}^{2}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4},$ (95) $$

where the first inequality follows from Lemma [C.5](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem5) with $m^{*}_{i}=\mu_{i}$ and in the last inequality, we define

$$ $\displaystyle P_{i}=\mathbb{E}\left[\sum\limits_{t=1}^{T}a_{i}(t)\right]=\mathbb{E}\left[\sum\limits_{t=1}^{T}x_{i}(t)\right].$ (96) $$

We give a bound on $\sum\limits_{t=1}^{T}\alpha_{i}(t)$ using the following lemma.

###### Lemma C.7 .

It holds for any $i\in[d]$ that

$$ $\displaystyle\mathbb{E}\left[\alpha_{i}(t)\right]\leq$ $\displaystyle 2\mathbb{E}\left[\min\left\{x_{i}(t),\frac{n_{i}-x_{i}(t)}{\sqrt{\gamma}}\right\}\right]$ $\displaystyle\leq$ $\displaystyle 2\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}\mathbb{E}\left[\frac{n_{i}-x_{i}(t)}{\sqrt{\gamma}}\right].$ (97) $$

###### Proof.

From the definition of $\alpha_{i}(t)$, we have

$$ $\displaystyle\mathbb{E}\left[\alpha_{i}(t)|x_{i}(t)\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-q_{i}(t)\right)^{2}\cdot\min\left\{1,\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\right\}\Bigg{|}x_{i}(t)\Biggr{]}$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\cdot\frac{\sigma_{i}^{2}}{a_{i}(t)}\Bigg{|}x_{i}(t)\right]\min\left\{1,\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\right\}$ $\displaystyle\leq$ $\displaystyle\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}\min\left\{x_{i}(t),\frac{2x_{i}(t)\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\gamma\left(\frac{x_{i}(t)}{n_{i}}\right)^{2}}\right\}$ $\displaystyle=$ $\displaystyle\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}n_{i}\min\left\{\frac{x_{i}(t)}{n_{i}},\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\gamma\frac{x_{i}(t)}{n_{i}}}\right\}$ $\displaystyle\leq$ $\displaystyle\left\{\begin{array}[]{ll}\frac{\sigma_{i}^{2}}{n_{i}}\frac{x_{i}(t)}{n_{i}}&\text{ if $\frac{x_{i}(t)}{n_{i}}<\frac{1}{\sqrt{\gamma}}$ }\\ \frac{\sigma_{i}^{2}}{n_{i}}\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\sqrt{\gamma}}&\text{if $\frac{x_{i}(t)}{n_{i}}\geq\frac{1}{\sqrt{\gamma}}$}\end{array}\right.$ (100) $\displaystyle\leq$ $\displaystyle\frac{\sigma_{i}^{2}}{n_{i}}\frac{2\left(1-\frac{x_{i}(t)}{n_{i}}\right)}{\sqrt{\gamma}}$ $\displaystyle=$ $\displaystyle\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}\frac{2}{\sqrt{\gamma}}\left(n_{i}-x_{i}(t)\right),$ (101) $$

where the first inequality follows from the condition of $k_{i}(t),q_{i}(t)\in[0,1]$ and the last inequality is due to $\sqrt{\gamma}\geq 2$ that follows from the assumption $T\geq 55\geq e^{4}$.
∎

###### Lemma C.5 .

###### Lemma C.6 .

###### Proof.

###### Proof of Lemma C.5 .

###### Lemma C.7 .

###### Proof.

#### C.3.2 Proof of the Stochastic Regime

Proof for the Stochastic Regime.
We call base arms in $I^{*}$ *optimal arms* and $J^{*}$ *suboptimal arms*. We bound the RHS of ([46](https://arxiv.org/html/2509.09933v1#A3.E46)) separately considering sub-optimal and optimal base arms.

Sub-optimal base arms side From ([95](https://arxiv.org/html/2509.09933v1#A3.E95)), the component of the RHS of ([46](https://arxiv.org/html/2509.09933v1#A3.E46)) is bounded by

$$ $\displaystyle\mathbb{E}\left[2\beta_{i}\left(T+1\right)-\beta_{i}(1)+2\delta_{i}\log\left(\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right)\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}2\sqrt{{\beta_{i}(1)}^{2}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)\Biggr{]}$ $\displaystyle\leq$ $\displaystyle 2\sqrt{{\beta_{i}(1)}^{2}+\frac{1}{\gamma}\left(\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4}\right)}-\beta_{i}(1)$ $\displaystyle+\delta_{i}\log\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\left(\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4}\right)\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{{\beta_{i}(1)}^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}+\frac{1}{\gamma\beta_{i}(1)}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma{\beta_{i}(1)}^{2}}\right)$ $\displaystyle+\frac{\delta}{\gamma{\beta_{i}(1)}^{2}}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)$ $\displaystyle=$ $\displaystyle 2\sqrt{{\beta_{i}(1)}^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma{\beta_{i}(1)}^{2}}\right)+\frac{\xi_{i}}{\gamma}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right),$ (102) $$

where the first inequality follows from ([95](https://arxiv.org/html/2509.09933v1#A3.E95)), the second inequality follows from $\sqrt{x+y}\leq\sqrt{x}+\frac{y}{2\sqrt{x}}$ that holds for any $x>0$ and $y>0$, $\log\left(1+x+y\right)\leq\log\left(1+x\right)+y$ that holds for any $x,y\geq 0$, and in the last equality we define $\xi_{i}=\frac{1}{\beta_{i}(1)}+\frac{\delta_{i}}{{\beta_{i}(1)}^{2}}$.

Optimal base-arm side Next, we let $i\in I^{*}$ be an optimal base-arm. We define the complement version of $P_{i}$ by

$$ $\displaystyle Q_{i}=\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(n_{i}-x_{i}(t)\right)\right]$ (103) $$

for $i\in[d]$. Then, from Lemma [C.7](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem7), we have

$$ $\displaystyle\mathbb{E}\left[2\beta_{i}\left(T+1\right)-\beta_{i}(1)+2\delta_{i}\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}2\sqrt{{\beta_{i}(1)}^{2}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)\Biggr{]}$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\Biggl{[}2\sqrt{{\beta_{i}(1)}^{2}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\beta_{i}(1)+2\delta_{i}\left(\sqrt{1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-1\right)\Biggr{]}$ $\displaystyle=$ $\displaystyle 2\left(\beta_{i}(1)+\delta_{i}\right)\mathbb{E}\left[\sqrt{1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-1\right]+\beta_{i}(1)$ $\displaystyle\leq$ $\displaystyle 2\left(\beta_{i}(1)+\delta_{i}\right)\cdot\left(\sqrt{1+\frac{2}{\gamma^{\frac{3}{2}}{\beta_{i}(1)}^{2}}\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}\sum\limits_{t=1}^{T}\mathbb{E}\left[\left(n_{i}-x_{i}(t)\right)\right]}-1\right)+\beta_{i}(1)$ $\displaystyle\leq$ $\displaystyle 2\left(\beta_{i}(1)+\delta_{i}\right)\sqrt{\mathbb{E}\left[\frac{2}{\gamma^{\frac{3}{2}}{\beta_{i}(1)}^{2}}\left(\frac{\sigma_{i}}{n_{i}}\right)^{2}\sum\limits_{t=1}^{T}\mathbb{E}\left[n_{i}-x_{i}(t)\right]\right]}+\beta_{i}(1)$ $\displaystyle\leq$ $\displaystyle 2\left(1+\delta_{i}\right)\frac{\sigma_{i}}{n_{i}}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\beta_{i}(1)$ (104) $$

where the first inequality follows from the inequality of $\log\left(1+x\right)\leq 2\left(\sqrt{1+x}-1\right)$ for $x>0$, the second inequality follows from Lemma [C.7](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem7), the third inequality follows from $\sqrt{1+x}-1\leq\sqrt{x}$ for $x\geq 0$, and the last inequality follows from $\beta_{i}(1)\geq 1$ for any $i\in[d]$.

Putting together the upper bound and lower bounds and applying a self-bounding technique Bounding the RHS of ([46](https://arxiv.org/html/2509.09933v1#A3.E46)) using ([102](https://arxiv.org/html/2509.09933v1#A3.E102)) and ([104](https://arxiv.org/html/2509.09933v1#A3.E104)) yields the regret upper bound depending on $\left(P_{i}\right)_{i\in J^{*}}$ and $\left(Q_{i}\right)_{i\in I^{*}}$ as

$$ $\displaystyle\frac{R_{T}}{\gamma}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}n_{i}\Biggl{(}\sqrt{{\beta_{i}(1)}^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma{\beta_{i}(1)}^{2}}\right)+\frac{\xi_{i}}{\gamma}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)\Biggr{)}$ $\displaystyle+\sum\limits_{i\in I^{*}}n_{i}\left(2\left(1+\delta_{i}\right)\frac{\sigma_{i}}{n_{i}}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\beta_{i}(1)\right)+\frac{dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}}{\gamma}$ $\displaystyle=$ $\displaystyle\sum\limits_{i\in J^{*}}\Biggl{(}\sqrt{\left({n_{i}\beta_{i}(1)}\right)^{2}+\sigma^{2}_{i}\frac{P_{i}}{\gamma}}-n_{i}\beta_{i}(1)+n_{i}\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma{\beta_{i}(1)}^{2}}\right)+\frac{n_{i}\xi_{i}}{\gamma}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)\Biggr{)}$ (105) $\displaystyle+\sum\limits_{i\in I^{*}}\left(2\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+n_{i}\beta_{i}(1)\right)+\frac{dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}}{\gamma}$ $\displaystyle=$ $\displaystyle\sum\limits_{i\in J^{*}}\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)+2\sum\limits_{i\in I^{*}}\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right),$ (106) $$

where we define convex function $\bar{f}_{i}:\mathbb{R}\rightarrow\mathbb{R}$ by

$$ $\displaystyle\bar{f}_{i}\left(x\right)=2\sqrt{\left({n_{i}\beta_{i}(1)}\right)^{2}+\sigma_{i}^{2}x}+n_{i}\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}x}{\gamma\left({n_{i}\beta_{i}(1)}\right)^{2}}\right)+\frac{n_{i}\xi_{i}}{\gamma}\log\left(1+\gamma x\right)-n_{i}\beta_{i}(1).$ (107) $$

In the stochastic regime, setting $C=0$ in ([85](https://arxiv.org/html/2509.09933v1#A3.E85)) yields the regret lower bound depending on $(P_{i})_{i\in J^{*}}$ and $(Q_{i})_{i\in I^{*}}$ as

$$ $\displaystyle R_{T}\geq\frac{1}{\lambda^{\prime}_{\mathcal{A}}}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}Q_{i}+\frac{1}{\lambda_{\mathcal{A}}}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}P_{i}.$ (108) $$

Combining ([106](https://arxiv.org/html/2509.09933v1#A3.E106)) and ([108](https://arxiv.org/html/2509.09933v1#A3.E108)), we have

$$ $\displaystyle\frac{R_{T}}{\log T}=\frac{R_{T}}{\gamma}=2\frac{R_{T}}{\gamma}-\frac{R_{T}}{\gamma}$ $\displaystyle\leq$ $\displaystyle 2\frac{R_{T}}{\gamma}-\frac{1}{\gamma}\left(\frac{1}{\lambda_{\mathcal{A}}^{\prime}}\sum\limits_{i\in I^{*}}\Delta_{i,\mathrm{min}}Q_{i}+\frac{1}{\lambda_{\mathcal{A}}}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}P_{i}\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\left(2\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}\frac{P_{i}}{\gamma}\right)+\sum\limits_{i\in I^{*}}\left(4\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{1}{2}}}\frac{Q_{i}}{\gamma}}-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}^{\prime}}\frac{Q_{i}}{\gamma}\right)$ (109) $\displaystyle+2\sum\limits_{i=1\in I^{*}}n_{i}\beta_{i}(1)+\frac{2}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\max_{x\geq 0}\left\{2\bar{f}_{i}\left(x\right)-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}x\right\}+\sum\limits_{i\in I^{*}}\max_{x\geq 0}\left\{4\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{1}{2}}}x}-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}^{\prime}}x\right\}$ (110) $\displaystyle+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{2}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\max_{x\geq 0}\left\{2\bar{f}_{i}\left(x\right)-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}x\right\}+\sum\limits_{i\in I^{*}}\frac{16\left(1+\delta_{i}\right)^{2}\lambda_{\mathcal{A}}^{\prime}\sigma^{2}_{i}}{\sqrt{\gamma}\Delta_{i,\mathrm{min}}}$ $\displaystyle+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{2}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ (111) $$

where the second inequality follows from ([106](https://arxiv.org/html/2509.09933v1#A3.E106)) and the last inequality follows from $a\sqrt{x}-bx\leq\frac{a^{2}}{2b}$ for $a,b,x\geq 0$. In the following, we evaluate the first term of ([111](https://arxiv.org/html/2509.09933v1#A3.E111)).

Bounding the first term of ([111](https://arxiv.org/html/2509.09933v1#A3.E111)) We will prove the following statement:

$$ $\displaystyle\max_{x\geq 0}\left\{2\bar{f}_{i}\left(x\right)-\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}x\right\}\leq h\left(\lambda_{\mathcal{A}}\frac{\sigma_{i}^{2}}{\Delta_{i,\mathrm{min}}}\right)+\mathcal{O}\left(\frac{\log(1+\gamma)}{\gamma}\right),$ (112) $$

where $h:\mathbb{R}_{+}\rightarrow\mathbb{R}$ is defined as

$$ $\displaystyle h_{i}(z)=\begin{cases}4n_{i}\beta_{i}(1)&\text{ if $0\leq z\leq\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta_{i}}{n_{i}\beta_{i}(1)}\right)}$ },\\ 2z\left(1+\sqrt{1+2\frac{\delta_{i}}{z}}\right)-2\delta_{i}\\ +4\delta_{i}\left(\log\frac{z}{n_{i}\beta_{i}(1)}+\log\left(1+\sqrt{1+2\frac{\delta_{i}}{z}}\right)\right)\\ +\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z}-2n_{i}\beta_{i}(1)&\text{if $z>\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta_{i}}{n_{i}\beta_{i}(1)}\right)}$}.\end{cases}$ (113) $$

Let $\bar{\Delta}_{i}=\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}$ for the notational simplicity. As $\bar{f}_{i}$ is concave, the maximum of $2\bar{f}_{i}(x)-\bar{\Delta}_{i,\mathrm{min}}x$ is attained by $x^{*}_{i}\in\mathbb{R}$ satisfying $2\bar{f}^{\prime}_{i}(x^{*}_{i})=\bar{\Delta}_{i}$. Define $\tilde{x}_{i}\geq 0$ by

$$ $\displaystyle\tilde{x}_{i}:=\max\left\{\left(\frac{4\sigma_{i}}{\bar{\Delta}_{i}}\right)^{2},\frac{8\delta_{i}n_{i}}{\bar{\Delta}_{i}},\frac{16\xi_{i}n_{i}}{\gamma\bar{\Delta}_{i}}\right\}.$ (114) $$

We then have

$$ $\displaystyle 2\bar{f}^{\prime}_{i}\left(\tilde{x}_{i}\right)\leq$ $\displaystyle\frac{2\sigma_{i}}{\sqrt{\left(\frac{4\sigma_{i}}{\bar{\Delta}_{i}}\right)^{2}}}+\frac{2\delta_{i}n_{i}\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma^{2}_{i}\frac{8\delta_{i}n_{i}}{\bar{\Delta}_{i}}}+\frac{2n_{i}\xi_{i}}{1+\gamma\frac{16n_{i}\xi_{i}}{\gamma\bar{\Delta}_{i}}}$ $\displaystyle\leq$ $\displaystyle\frac{\bar{\Delta}_{i}}{2}+\frac{\bar{\Delta}_{i}}{4}+\frac{\bar{\Delta}_{i}}{8}\leq\bar{\Delta}_{i},$ $$

which implies $\tilde{x}_{i}\geq x^{*}_{i}$.
Hence, we have

$$ $\displaystyle\max_{x\geq 0}\{2f_{i}(x)-\bar{\Delta}_{i}x\}=2f_{i}(x^{*}_{i})-\bar{\Delta}_{i}x^{*}_{i}$ $\displaystyle=$ $\displaystyle 4\sqrt{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma^{2}_{i}x^{*}_{i}}+2\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}x^{*}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}\right)$ $\displaystyle+2\frac{n_{i}\xi_{i}}{\gamma}\log\left(1+\gamma x^{*}_{i}\right)-\bar{\Delta}_{i}x^{*}_{i}-2n_{i}\beta_{i}(1)$ $\displaystyle\leq$ $\displaystyle\max_{x\geq 0}\left\{4\sqrt{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma^{2}_{i}x}+2\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}x\right)-\bar{\Delta}_{i}x\right\}$ $\displaystyle+2\frac{n_{i}\xi_{i}}{\gamma}\log\left(1+\gamma\tilde{x}_{i}\right)-2n_{i}\beta_{i}(1)$ $\displaystyle=$ $\displaystyle\max_{x\geq 0}\left\{g_{i}(x)-\bar{\Delta}_{i}x\right\}-2n_{i}\beta_{i}(1)+\mathcal{O}\left(\frac{\left(\log\left(1+\gamma\right)\right)}{\gamma}\right),$ (115) $$

where we define

$$ $\displaystyle g_{i}(x)=4\sqrt{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma^{2}_{i}x}+2\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}x}{\left(n_{i}\beta_{i}(1)\right)^{2}}\right).$ (116) $$

From ([115](https://arxiv.org/html/2509.09933v1#A3.E115)) and ([111](https://arxiv.org/html/2509.09933v1#A3.E111)), we have

$$ $\displaystyle\limsup_{T\rightarrow\infty}\frac{R_{T}}{\log T}\leq\sum\limits_{i\in J^{*}}\left(\max_{x\geq 0}\left\{g_{i}(x)-\bar{\Delta}_{i}x\right\}-2n_{i}\beta_{i}(1)\right)+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1).$ (117) $$

In the following, we write $z_{i}=\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}$.
As we have

$$ $\displaystyle g^{\prime}_{i}(x)=\frac{2\sigma_{i}^{2}}{\sqrt{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma_{i}^{2}x}}+\frac{2\delta_{i}\sigma_{i}^{2}}{\left(n_{i}\beta_{i}(1)\right)^{2}+\sigma_{i}^{2}x}\leq 2\sigma_{i}^{2}\left(\frac{1}{n_{i}\beta_{i}(1)}+\frac{\delta}{\left(n_{i}\beta_{i}(1)\right)^{2}}\right),$ (118) $$

if $z_{i}=\frac{\sigma_{i}^{2}}{\bar{\Delta}_{i}}\leq\frac{1}{2\left(\frac{1}{n_{i}\beta_{i}(1)}+\frac{\delta}{\left(n_{i}\beta_{i}(1)\right)^{2}}\right)}=\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta}{n_{i}\beta_{i}(1)}\right)}$, the maximum of $g_{i}(x)-\bar{\Delta}_{i}x$ is attained by $x=0$, implying

$$ $\displaystyle\max\left\{g_{i}(x)-\bar{\Delta}_{i}x\right\}=g_{i}(0)=4n_{i}\beta_{i}(1)\quad\text{if}\quad z_{i}:=\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\leq\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta}{n_{i}\beta_{i}(1)}\right)}.$ (119) $$

Otherwise, we have

$$ $\displaystyle g_{i}(x)-\bar{\Delta}_{i}x=$ $\displaystyle 4n_{i}\beta_{i}(1)\sqrt{1+\frac{\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}x}+2\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}x\right)$ $\displaystyle-\frac{\left(n_{i}\beta_{i}(1)\right)^{2}\bar{\Delta}_{i}}{\sigma_{i}^{2}}\left(1+\frac{\sigma^{2}_{i}x}{\left(n_{i}\beta_{i}(1)\right)^{2}}\right)+\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}$ $\displaystyle=$ $\displaystyle 4n_{i}\beta_{i}(1)\sqrt{1+\frac{\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}x}+4\delta_{i}\log\left(\sqrt{1+\frac{\sigma^{2}_{i}}{\left(n_{i}\beta_{i}(1)\right)^{2}}x}\right)$ $\displaystyle-\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}\left(\sqrt{1+\frac{\sigma^{2}_{i}x}{\left(n_{i}\beta_{i}(1)\right)^{2}}}\right)^{2}+\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}.$ $$

From this, by setting $y=\sqrt{1+\frac{\sigma^{2}_{i}x}{\left(n_{i}\beta_{i}(1)\right)^{2}}}$, we obtain

$$ $\displaystyle\max_{x\geq 0}\left\{g_{i}\left(x\right)-\bar{\Delta}_{i}x\right\}\leq\max_{y\geq 0}\left\{4n_{i}\beta_{i}(1)y+4\delta_{i}\log y-\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}y^{2}\right\}+\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}.$ (120) $$

We here use the following:

$$ $\displaystyle\max_{y\geq 0}\left\{ay+b\log y-cy^{2}\right\}=\frac{1}{2}\left(\frac{a}{4c}\left(a+\sqrt{a^{2}+8bac}-b\right)\right)+b\log\frac{a+\sqrt{a^{2}+8bc}}{4c},$ (121) $$

which holds for any $a,b,c>0$. We hence have

$$ $\displaystyle\max_{y\geq 0}\left\{4n_{i}\beta_{i}(1)y+4\delta_{i}\log y-\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}y^{2}\right\}$ $\displaystyle=$ $\displaystyle\frac{1}{2}\left(\frac{4n_{i}\beta_{i}(1)z_{i}}{4\left(n_{i}\beta_{i}(1)\right)^{2}}\left(4n_{i}\beta_{i}(1)+\sqrt{(4n_{i}\beta_{i}(1))^{2}+32\frac{\delta_{i}\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}}\right)-4\delta_{i}\right)$ $\displaystyle+4\delta\log\frac{4n_{i}\beta_{i}(1)+\sqrt{\left(4n_{i}\beta_{i}(1)\right)^{2}+32\frac{\delta_{i}\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}}}{4\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{z_{i}}}$ $\displaystyle=$ $\displaystyle 2\left(z_{i}\left(n_{i}\beta_{i}(1)+\sqrt{1+2\frac{\delta}{z_{i}}}\right)-\delta_{i}\right)+4\delta_{i}\left(\log\frac{z_{i}}{n_{i}\beta_{i}(1)}+\log\left(1+\sqrt{1+2\frac{\delta_{i}}{z_{i}}}\right)\right).$ (122) $$

Combining ([115](https://arxiv.org/html/2509.09933v1#A3.E115)) with ([119](https://arxiv.org/html/2509.09933v1#A3.E119)), ([120](https://arxiv.org/html/2509.09933v1#A3.E120)), ([122](https://arxiv.org/html/2509.09933v1#A3.E122)), we obtain

$$ $\displaystyle\max_{x\geq 0}\left\{2f_{i}(x)-\bar{\Delta}_{i}x\right\}\leq$ $\displaystyle h_{i}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\right)+\mathcal{O}\left(\frac{\log\left(1+\gamma\right)}{\gamma}\right)$ $\displaystyle=$ $\displaystyle h_{i}\left(\lambda_{\mathcal{A}}\frac{\sigma^{2}_{i}}{\Delta_{i,\mathrm{min}}}\right)+\mathcal{O}\left(\frac{\log\left(1+\gamma\right)}{\gamma}\right)$ (123) $$

where $h_{i}:\mathbb{R}_{+}\rightarrow\mathbb{R}$ is defined by ([113](https://arxiv.org/html/2509.09933v1#A3.E113)). From ([111](https://arxiv.org/html/2509.09933v1#A3.E111)) and ([123](https://arxiv.org/html/2509.09933v1#A3.E123)), we complete the proof of ([112](https://arxiv.org/html/2509.09933v1#A3.E112)).

Bouding $h$ For $z>\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta_{i}}{n_{i}\beta_{i}(1)}\right)}$, $h(z)$ in ([113](https://arxiv.org/html/2509.09933v1#A3.E113)) is bounded as

$$ $\displaystyle h_{i}(z)\leq$ $\displaystyle 2z\left(1+1+\frac{\delta_{i}}{z}\right)-2\delta_{i}+4\delta_{i}\left(\log z+\log\left(1+\sqrt{1+2\frac{\delta_{i}}{z}}\right)\right)$ $\displaystyle+\frac{\left(n_{i}\beta_{i}(1)\right)^{2}}{n_{i}\beta_{i}(1)}\cdot 2\left(1+\frac{\delta_{i}}{n_{i}\beta_{i}(1)}\right)-2n_{i}\beta_{i}(1)$ $\displaystyle=$ $\displaystyle 4z+4\delta_{i}\left(\log z+\log\left(1+\sqrt{1+2\frac{\delta_{i}}{z}}\right)+\frac{1}{2}\right)$ $\displaystyle\leq$ $\displaystyle 4z+c_{i}\log\left(1+z\right)\quad\left(c=\mathcal{O}\left({\delta_{i}}^{2}\right)\right),$ (124) $$

where the last inequality follows from $\log\left(1+z\right)=\Omega\left(\frac{1}{\delta}\right)$ that holds for $z>\frac{n_{i}\beta_{i}(1)}{2\left(1+\frac{\delta_{i}}{n_{i}\beta_{i}(1)}\right)}$. Hence, for any $z>0$, $h_{i}(z)$ is bounded as

$$ $\displaystyle h_{i}(z)=\max\left\{4z+c_{i}\log\left(1+z\right),2n_{i}\beta_{i}(1)\right\}.$ (125) $$

From this and ([123](https://arxiv.org/html/2509.09933v1#A3.E123)), we obtain

$$ $\displaystyle R_{T}\leq$ $\displaystyle\left(\sum\limits_{i\in J^{*}}\max\left\{4\frac{\lambda_{\mathcal{A}}\sigma_{i}^{2}}{\Delta_{i,\mathrm{min}}}+c_{i}\log\left(1+\frac{\lambda_{\mathcal{A}}\sigma_{i}^{2}}{\Delta_{i,\mathrm{min}}}\right),2n_{i}\beta_{i}(1)\right\}+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)\right)\log T$ (126) $\displaystyle+\sum\limits_{i\in I^{*}}\frac{16(1+\delta_{i})^{2}\lambda_{\mathcal{A}}^{\prime}\sigma_{i}^{2}}{\Delta^{\prime}_{i,\mathrm{min}}}\sqrt{\log T}+o\left(\sqrt{\log T}\right)$ (127) $$

which completes the proof of upper bound of the LS method under the stochastic regime for the stochastic regime.

#### C.3.3 Proof for the Stochastic Regime with Adversarial Corruptions

We here show a regret bound for the stochastic regime with adversarial corruptions, which is the following regret bound:

$$ $\displaystyle R_{T}\leq\mathcal{R}^{\mathrm{LS}}+\mathcal{O}\left(CMR^{\mathrm{LS}}\right),$ (128) $$

where $\mathcal{R}^{\mathrm{LS}}$ is $\mathcal{O}\left(\sum\limits_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right)$ and $C$ is the corruption level defined in Section [2](https://arxiv.org/html/2509.09933v1#S2).

###### Proof.

In the stochastic regime with adversarial corruptions, using Lemma [C.5](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem5) with $m^{*}_{i}=\ell_{i}$ we have

$$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\alpha_{i}(t)\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-\mu_{i}\right)^{2}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)\Biggr{]}+\frac{5}{4}$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-l^{\prime}_{i}(t)+l^{\prime}_{i}(t)-\mu_{i}\right)^{2}+\log\left(1+\sum\limits_{t=1}^{T}a_{i}(t)\right)\Biggr{]}+\frac{5}{4}$ $\displaystyle\leq$ $\displaystyle\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4}+P^{\prime}_{i},$ (129) $$

where we define

$$ $\displaystyle P^{\prime}_{i}=\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-l^{\prime}_{i}(t)\right)^{2}\right].$ (130) $$

Hence, in a similar argument to that of showing ([102](https://arxiv.org/html/2509.09933v1#A3.E102)), by using ([129](https://arxiv.org/html/2509.09933v1#A3.E129)) instead of ([95](https://arxiv.org/html/2509.09933v1#A3.E95)), we obtain

$$ $\displaystyle\mathbb{E}\left[2\beta_{i}(T+1)-\beta_{i}(1)+2\delta_{i}\log\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\Biggl{[}2\sqrt{\beta^{2}_{i}(1)+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{1}{\gamma\beta^{2}_{i}(1)}\sum\limits_{t=1}^{T}\alpha_{i}(t)\right)\Biggr{]}$ $\displaystyle\leq$ $\displaystyle 2\sqrt{(\beta_{i}(1))^{2}+\frac{1}{\gamma}\left(\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4}+P^{\prime}_{i}\right)}-\beta_{i}(1)$ $\displaystyle+\delta_{i}\log\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\left(\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+\log\left(1+P_{i}\right)+\frac{5}{4}+P^{\prime}_{i}\right)\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{(\beta_{i}(1))^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}+\frac{1}{\gamma\beta_{i}(1)}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)+2\sqrt{\frac{P^{\prime}_{i}}{\gamma}}-\beta_{i}(1)$ $\displaystyle+\delta_{i}\log\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\left(\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}+P^{\prime}_{i}\right)\right)+\frac{\delta_{i}}{\gamma\left(\beta_{i}(1)\right)^{2}}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{(\beta_{i}(1))^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}+\frac{1}{\gamma\beta_{i}(1)}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)+2\sqrt{\frac{P^{\prime}_{i}}{\gamma}}-\beta_{i}(1)$ $\displaystyle+\delta_{i}\log\left(\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}\frac{\sigma^{2}_{i}}{n^{2}_{i}}P_{i}\right)\cdot\left(1+\frac{1}{\gamma{\beta_{i}(1)}^{2}}P^{\prime}_{i}\right)\right)+\frac{\delta_{i}}{\gamma\left(\beta_{i}(1)\right)^{2}}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{(\beta_{i}(1))^{2}+\frac{\sigma^{2}_{i}P_{i}}{n^{2}_{i}\gamma}}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}P_{i}}{\gamma\left(n_{i}\beta_{i}(1)\right)^{2}}\right)+\frac{\xi_{i}}{\gamma}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)$ $\displaystyle+2\sqrt{\frac{P^{\prime}_{i}}{\gamma}}+\delta_{i}\log\left(1+\frac{P^{\prime}_{i}}{\gamma\beta^{2}_{i}(1)}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{(\beta_{i}(1))^{2}+\frac{\sigma^{2}_{i}}{n^{2}_{i}}\frac{P_{i}}{\gamma}}-\beta_{i}(1)+\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}P_{i}}{\gamma\left(n_{i}\beta_{i}(1)\right)^{2}}\right)+\frac{\xi_{i}}{\gamma}\left(\log\left(1+P_{i}\right)+\frac{5}{4}\right)$ $\displaystyle+\left(2+\frac{\delta_{i}}{\beta_{i}(1)}\right)\sqrt{\frac{P^{\prime}_{i}}{\gamma}},$ $$

where the last inequality follows from $\log\left(1+x\right)\leq\sqrt{x}$ for $x\geq 0$. Combining this with ([46](https://arxiv.org/html/2509.09933v1#A3.E46)) and ([104](https://arxiv.org/html/2509.09933v1#A3.E104)), via a similar argument to that of showing ([106](https://arxiv.org/html/2509.09933v1#A3.E106)), we have

$$ $\displaystyle\frac{R_{T}}{\gamma}\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)+2\sum\limits_{i\in I^{*}}\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ $\displaystyle+\sum\limits_{i\in J^{*}}\left(2+\frac{\delta_{i}}{\beta_{i}(1)}\right)n_{i}\sqrt{\frac{P^{\prime}_{i}}{\gamma}}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)+2\sum\limits_{i\in I^{*}}\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ $\displaystyle+2\sum\limits_{i\in J^{*}}\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\sqrt{\frac{P^{\prime}_{i}}{\gamma}},$ (131) $$

where $2\leq\frac{\delta_{i}}{\beta_{i}(1)}$ and $\bar{f}_{i}$ is defined by

$$ $\displaystyle\bar{f}_{i}\left(x\right)=2\sqrt{\left({n_{i}\beta_{i}(1)}\right)^{2}+\sigma_{i}^{2}x}+n_{i}\delta_{i}\log\left(1+\frac{\sigma^{2}_{i}x}{\gamma\left({n_{i}\beta_{i}(1)}\right)^{2}}\right)+\frac{n_{i}\xi_{i}}{\gamma}\log\left(1+\gamma x\right)-n_{i}\beta_{i}(1).$ $$

We further have

$$ $\displaystyle\sum\limits_{i\in J^{*}}\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\sqrt{\frac{P^{\prime}_{i}}{\gamma}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}\sum\limits_{i\in J^{*}}P^{\prime}_{i}}$ $\displaystyle=$ $\displaystyle\sqrt{\frac{\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}\mathbb{E}\left[\sum\limits_{t=1}^{T}\sum\limits_{i\in J^{*}}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-l^{\prime}_{i}(t)\right)^{2}\right]}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}\mathbb{E}\left[\sum\limits_{t=1}^{T}\max\limits_{i\in[d],j\in[n_{i}]}\left|L_{i,j}(t)-L_{i,j}^{\prime}(t)\right|^{2}\right]}$ $\displaystyle=$ $\displaystyle\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}$ (132) $$

where the first inequality follows from the Cauchy-Shwarz inequality, the first equality follows from the definition of $P^{\prime}_{i}$ in ([130](https://arxiv.org/html/2509.09933v1#A3.E130)), and the second inequality follows from the fact that $\sum\limits_{i\in J^{*}}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\leq~|J^{*}|$. Combining ([131](https://arxiv.org/html/2509.09933v1#A3.E131)) and ([132](https://arxiv.org/html/2509.09933v1#A3.E132)), we obtain

$$ $\displaystyle\frac{R_{T}}{\gamma}\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)+2\sum\limits_{i\in I^{*}}\left(1+\delta_{i}\right)\sigma_{i}\sqrt{\frac{2}{\gamma^{\frac{3}{2}}}Q_{i}}+\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)$ $\displaystyle+\frac{1}{\gamma}\left(dW+d+2W\delta_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}n_{i}\xi_{i}\right)$ $\displaystyle+2\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}$ (133) $$

From ([133](https://arxiv.org/html/2509.09933v1#A3.E133)) and Lemma [C.4](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem4), for any $\chi\in(0,1]$, we have

$$ $\displaystyle\frac{R_{T}}{\log T}$ $\displaystyle=$ $\displaystyle(1+\chi)\frac{R_{T}}{\gamma}-\lambda\frac{R_{T}}{\gamma}$ $\displaystyle\leq$ $\displaystyle(1+\chi)\frac{R_{T}}{\gamma}-\frac{\lambda}{\gamma}\Biggl{(}\frac{1}{\lambda\left(\mathcal{A}\right)}\sum\limits_{i\in I^{*}}\Delta^{\prime}_{i,\mathrm{min}}Q_{i}+\frac{1}{\lambda_{\mathcal{A}}}\sum\limits_{i\in J^{*}}\Delta_{i,\mathrm{min}}P_{i}-2CM\Biggr{)}$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\left((1+\chi)\bar{f}_{i}\left(\frac{P_{i}}{\gamma}\right)-\lambda\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}\frac{P_{i}}{\gamma}\right)+\sum\limits_{i\in I^{*}}\left(2(1+\chi)(1+\delta_{i})\sqrt{\frac{2}{\gamma^{1/2}}\frac{Q_{i}}{\gamma}}-\lambda\frac{\Delta^{\prime}_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}^{\prime}}\frac{Q_{i}}{\gamma}\right)$ $\displaystyle+2(1+\chi)\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}+\frac{2\lambda CM}{\gamma}$ $\displaystyle+(1+\chi)\left(\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+\sum\limits_{i=1}^{d}n_{i}\delta_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}\xi_{i}n_{i}\right)\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\max_{x\geq 0}\left\{(1+\chi)\bar{f}_{i}\left(x\right)-\lambda\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}x\right\}+\sum\limits_{i\in I^{*}}\max_{x\geq 0}\left\{2(1+\chi)(1+\delta)\sqrt{\frac{2}{\gamma^{1/2}}x}-\lambda\frac{\Delta^{\prime}_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}^{\prime}}x\right\}$ $\displaystyle+2(1+\chi)\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}+\frac{2\lambda CM}{\gamma}$ $\displaystyle+(1+\chi)\left(\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+\sum\limits_{i=1}^{d}n_{i}\delta_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}\xi_{i}n_{i}\right)\right)$ $\displaystyle\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\max_{x\geq 0}\left\{(1+\chi)\bar{f}_{i}\left(x\right)-\lambda\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}x\right\}+\sum\limits_{i\in I^{*}}\frac{4\left(1+\lambda\right)^{2}(1+\delta)^{2}\lambda_{\mathcal{A}}^{\prime}}{\lambda\sqrt{\gamma}\Delta^{\prime}_{i,\mathrm{min}}}$ $\displaystyle+2(1+\chi)\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}$ $\displaystyle+(1+\chi)\left(\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+\frac{1}{\gamma}\left(dW+\sum\limits_{i=1}^{d}n_{i}\delta_{i}+\frac{5}{4}\sum\limits_{i\in J^{*}}\xi_{i}n_{i}\right)\right).$ (134) $$

Further, letting $\bar{\Delta}_{i}=\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}$, we have

$$ $\displaystyle\max_{x\geq 0}\left\{\left(1+\chi\right)\bar{f}_{i}(x)-\chi\bar{\Delta}_{i}x\right\}$ $\displaystyle=$ $\displaystyle\frac{1+\chi}{2}\max_{x\geq 0}\left\{2\bar{f}_{i}(x)-\frac{2\chi\bar{\Delta}_{i}}{1+\chi}x\right\}$ $\displaystyle\leq$ $\displaystyle\frac{1+\chi}{2}h\left(\frac{(1+\chi)\sigma^{2}_{i}}{2\chi\bar{\Delta}_{i}}\right)+\mathcal{O}\left(\frac{\log(1+\gamma)}{\gamma}\right)$ $\displaystyle\leq$ $\displaystyle\max\left\{\frac{(1+\chi)^{2}}{\chi}\frac{\sigma^{2}}{\bar{\Delta}_{i}}+c_{i}\log\left(1+\frac{\sigma_{i}^{2}}{\chi\bar{\Delta}_{i}}\right),(1+\chi)n_{i}\beta_{i}(1)\right\}+\mathcal{O}\left(\frac{\log(1+\gamma)}{\gamma}\right)$ $\displaystyle\leq$ $\displaystyle\max\left\{4\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+c_{i}\log\left(1+\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\right),2n_{i}\beta_{i}(1)\right\}+(1+c_{i})\left(\frac{1}{\chi}-1\right)\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\mathcal{O}\left(\frac{\log(1+\gamma)}{\gamma}\right)$ (135) $$

where $h(z)$ is defined as ([113](https://arxiv.org/html/2509.09933v1#A3.E113)), the first inequality follows from ([123](https://arxiv.org/html/2509.09933v1#A3.E123)), the second inequality comes from ([125](https://arxiv.org/html/2509.09933v1#A3.E125)) and $\chi\in(0,1]$, and the last inequality follows from

$$ $\displaystyle\frac{\left(1+\chi\right)^{2}}{\chi}$ $\displaystyle=\chi+2+\frac{1}{\chi}\leq 3+\frac{1}{\chi}=4+\left(\frac{1}{\chi}-1\right)$ $$

and

$$ $\displaystyle\log\left(1+\frac{\sigma^{2}_{i}}{\chi\bar{\Delta}_{i}}\right)\leq$ $\displaystyle\frac{1}{\chi}\log\left(1+\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\right)$ $\displaystyle\leq$ $\displaystyle\log\left(1+\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\right)+\left(\frac{1}{\chi}-1\right)\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}.$ $$

Using ([134](https://arxiv.org/html/2509.09933v1#A3.E134)), ([135](https://arxiv.org/html/2509.09933v1#A3.E135)), and $\chi\leq 1$, we obtain

$$ $\displaystyle\frac{R_{T}}{\log T}\leq$ $\displaystyle\sum\limits_{i\in J^{*}}\max\left\{4\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+c_{i}\log\left(1+\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}\right),2n_{i}\beta_{i}(1)\right\}+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)+2\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}$ $\displaystyle+2\chi\frac{CM}{\gamma}+(\frac{1}{\chi}-1)\sum\limits_{i\in J^{*}}(1+c_{i})\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\sum\limits_{i\in I^{*}}\frac{4\left(1+\chi\right)^{2}(1+\delta)^{2}\lambda_{\mathcal{A}}^{\prime}}{\chi\sqrt{\gamma}\Delta^{\prime}_{i,\mathrm{min}}}+\mathcal{O}\left(\frac{\log(1+\gamma)}{\gamma}\right)$ (136) $$

By choosing $\chi=\sqrt{\frac{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)}{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)+2CM}}$, we have

$$ $\displaystyle\chi\leq\sqrt{\frac{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)}{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)+2CM}}$ (137) $$

and

$$ $\displaystyle\frac{1}{\chi}-1=$ $\displaystyle\sqrt{1+\frac{2CM}{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)}}-1$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{2CM}{\gamma\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)}},$ (138) $$

which implies that

$$ $\displaystyle 2\sqrt{\frac{|J^{*}|\sum\limits_{i\in J^{*}}\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}}{\gamma}C}+\frac{2\chi CM}{\gamma}+(1+c)\left(\frac{1}{\chi}-1\right)\sum\limits_{j\in J^{*}}\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}$ $\displaystyle=$ $\displaystyle\mathcal{O}\left(\sqrt{\frac{C\max\left\{M,|J^{*}|\right\}}{\gamma}\sum\limits_{i\in J^{*}}\left(\frac{\sigma^{2}_{i}}{\bar{\Delta}_{i}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)}\right).$ (139) $$

From this and ([136](https://arxiv.org/html/2509.09933v1#A3.E136)), recalling that $\gamma=\log T$ and $\bar{\Delta}_{i}=\frac{\Delta_{i,\mathrm{min}}}{\lambda_{\mathcal{A}}}$, we obtain

$$ $\displaystyle R_{T}\leq$ $\displaystyle\Biggl{(}\sum\limits_{i\in J^{*}}\max\Biggl{\{}4\lambda_{\mathcal{A}}\frac{\sigma^{2}_{i}}{\Delta_{i,\mathrm{min}}}+c\log\left(1+\lambda_{\mathcal{A}}\frac{\sigma^{2}_{i}}{\Delta_{i,\mathrm{min}}}\right),2n_{i}\beta_{i}(1)\Biggr{\}}+2\sum\limits_{i\in I^{*}}n_{i}\beta_{i}(1)\Biggr{)}\log T$ $\displaystyle+\mathcal{O}\left(\sqrt{C\max\left\{M,|J^{*}|\right\}\sum\limits_{i\in J^{*}}\left(\lambda_{\mathcal{A}}\frac{\sigma^{2}_{i}}{\Delta_{i,\mathrm{min}}}+\left(\frac{n_{i}\delta_{i}}{\beta_{i}(1)}\right)^{2}\right)\log T}\right)$ $\displaystyle+\sum\limits_{i\in I^{*}}\frac{(1+\chi)^{2}}{\chi}\frac{4(1+\delta)^{2}\lambda_{\mathcal{A}}^{\prime}}{\Delta^{\prime}_{i,\mathrm{min}}}\sqrt{\log T}+o\left(\sqrt{\log T}\right)$ (140) $$

which completes the proof of the stochastic regime with adversarial corruption.
∎

###### Proof.

#### C.3.4 Proof for the Adversarial Regime

Proof for the adversarial regime. First, we prove $R_{T}\leq\sqrt{4WQ_{2}\log T}+\mathcal{O}\left(W\log T\right)+dW+d+2W\delta$. For any $\boldsymbol{q}^{*}\in[0,1]^{d}$, bounding the RHS of Lemma [C.3](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem3), we have

$$ $\displaystyle R_{T}$ $\displaystyle\leq$ $\displaystyle\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[2\beta_{i}(T+1)-\beta_{i}(1)+2\delta\log\left(\frac{\beta_{i}(T+1)}{\beta_{i}(1)}\right)\right]+dW+2\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}$ $\displaystyle\leq$ $\displaystyle 2\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[\beta_{i}(T+1)\right]+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle=$ $\displaystyle 2\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[\sqrt{\beta^{2}_{i}(1)+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\alpha_{i}(t)}\right]+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[\sqrt{\beta^{2}_{i}(1)+\frac{1}{\gamma}\Biggl{(}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-m^{*}_{i}\right)^{2}+\log\left(1+a_{i}(t)\right)+\frac{5}{4}\Biggr{)}}\right]$ $\displaystyle+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[\sqrt{\gamma\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)}{n_{i}}\right)}^{2}\left(k_{i}(t)-m^{*}_{i}\right)^{2}}\right]+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i=1}^{d}\left(\mathbb{E}\left[\sqrt{\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)}{n_{i}}\right)}^{2}\left(k_{i}(t)-m^{*}_{i}\right)^{2}}\right]\right)^{2}}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i=1}^{d}\mathbb{E}\left[\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)}{n_{i}}\right)}^{2}\left(k_{i}(t)-m^{*}_{i}\right)^{2}\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ (141) $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\mathbb{E}\left[\sum\limits_{t=1}^{T}\|\boldsymbol{k}(t)-\boldsymbol{q}^{*}\|_{2}^{2}]\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $$

where the second inequality follows from $\beta_{i}(T+1)=\mathcal{O}(T)$, the third inequality follows from Lemma [C.5](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem5), and the fifth inequality follows from the Cauchy-Schwarz inequality. Since $\boldsymbol{q}^{*}$ is arbitrary, we obtain the desired results by $\boldsymbol{q}^{*}=\bar{l}$.

Next, we prove $R_{T}\leq\sqrt{4\sum\limits_{i=1}^{d}{n_{i}}^{2}L^{*}\log T}+\mathcal{O}\left(d\log T\right)+dW+d+2W\delta$. By setting $\boldsymbol{q}^{*}=0$ in ([141](https://arxiv.org/html/2509.09933v1#A3.E141)), we have

$$ $\displaystyle R_{T}$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i\in\{j\in[d]|a_{j}(t)\geq 1\}}\mathbb{E}\left[\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)}{n_{i}}\right)}^{2}{k_{i}(t)}^{2}\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i\in\{j\in[d]|a_{j}(t)\geq 1\}}\mathbb{E}\left[\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)}{n_{i}}\right)}^{2}k_{i}(t)\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i\in\{j\in[d]|a_{j}(t)\geq 1\}}\mathbb{E}\left[\sum\limits_{t=1}^{T}{\left(\frac{a_{i}(t)-a^{*}_{i}}{n_{i}}\right)}k_{i}(t)+\frac{a^{*}_{i}}{n_{i}}k_{i}(t)\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\left(R_{T}+L^{*}\right)}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $$

where the third inequality follows from Jensen’s inequality. By solving this equation in $R_{T}$, we obtain

$$ $\displaystyle R_{T}\leq 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma L^{*}}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ (142) $$

which is the desired bound.

Finally, we prove $R_{T}\leq\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}(mT-L^{*})\log T}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$. By setting $\boldsymbol{q}^{*}=\mathbf{1}$ in ([141](https://arxiv.org/html/2509.09933v1#A3.E141)) and repeating a similar argument as for proving $R_{T}\leq\sqrt{4\sum\limits_{i=1}^{d}{n_{i}}^{2}L^{*}\log T}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$, we have

$$ $\displaystyle R_{T}\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i=1}^{d}\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-1\right)^{2}\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle=$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i=1}^{d}\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(1-k_{i}(t)\right)^{2}\right]}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\mathbb{E}\left[\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\sum\limits_{i=1}^{d}\mathbb{E}\left[\sum\limits_{t=1}^{T}a_{i}(t)\left(1-k_{i}(t)\right)\right]}\right]+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\Biggl{(}MT-\sum\limits_{t=1}^{T}a^{*}_{i}k_{i}(t)-\sum\limits_{t=1}^{T}k_{i}(t)\left(a_{i}(t)-a^{*}_{i}\right)\Biggr{)}}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\left(MT-L^{*}-R_{T}\right)}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right)$ $$

where the third inequality follows since $\sum\limits_{i=1}^{d}a_{i}(t)\leq M$ and the forth inequality follows from Jensen’s inequality. By solving this inequation in $R_{T}$, we obtain

$$ $\displaystyle R_{T}\leq 2\sqrt{\sum\limits_{i=1}^{d}{n_{i}}^{2}\gamma\left(MT-L^{*}\right)}+\mathcal{O}\left(W\gamma+dW+\sum\limits_{i=1}^{d}\delta_{i}n_{i}\delta_{i}\right),$ (143) $$

which completes the proof.

### C.4 Proof for the GD Method

Here, we provide proofs for the GD method. We can prove it by a similar discussion to that for the LS method. We first discuss the key lemma for this argument.

#### C.4.1 Preliminaries

###### Lemma C.8 .

Assume that $q_{i}(t)$ is given by ([8](https://arxiv.org/html/2509.09933v1#S4.E8)). Then, for any $i\in[d]$ and $u_{i}(1),\ldots,u_{i}(T)\in[0,1]$, we have

$$ $\displaystyle\sum\limits_{t=1}^{T}\alpha_{i}(t)\leq$ $\displaystyle\sum\limits_{t=1}^{T}a_{i}(t)\left(k_{i}(t)-q_{i}(t)\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-\eta}\sum\limits_{t=1}^{T}a_{i}(t)\left(k_{i}(t)-u_{i}(t)\right)^{2}+\frac{1}{\eta\left(1-2\eta\right)}\left(\frac{1}{4}+2\sum\limits_{t=1}^{T}|u_{i}(t+1)-u_{i}(t)|\right)$ (144) $$

###### Proof.

Take $i\in[d]$ satisfying $a_{i}(t)=1$. Then, it holds that

$$ $\displaystyle\left(k_{i}(t)-q_{i}(t)\right)^{2}-\left(k_{i}(t)-u_{i}(t)\right)^{2}$ $\displaystyle\leq$ $\displaystyle 2\left(k_{i}(t)-q_{i}(t)\right)\left(u_{i}(t)-q_{i}(t)\right)$ $\displaystyle=$ $\displaystyle 2(k_{i}(t)-q_{i}(t))(q_{i}(t+1)-q_{i}(t))+2(k_{i}(t)-q_{i}(t))(u_{i}(t)-q_{i}(t+1))$ $\displaystyle=$ $\displaystyle 2\eta(k_{i}(t)-q_{i}(t))^{2}+\frac{2}{\eta}(q_{i}(t+1)-q_{i}(t))(u_{i}(t)-q_{i}(t+1))$ $\displaystyle\leq$ $\displaystyle 2\eta(k_{i}(t)-q_{i}(t))^{2}+\frac{1}{\eta}(u_{i}(t)-q_{i}(t))^{2}-(u_{i}(t)-q_{i}(t+1)^{2}),$ $$

where the inequalities follow from $y^{2}-x^{2}=2y(y-x)-(x-y)^{2}\leq 2y(y-x)$ for $x,y\in\mathbb{R}$ and the last inequality follows from the definition of $q_{i}(t)$ in ([8](https://arxiv.org/html/2509.09933v1#S4.E8)). Hence, we have

$$ $\displaystyle(k_{i}(t)-q_{i}(t))^{2}\leq\frac{1}{1-2\eta}\left((k_{i}(t)-u_{i}(t))^{2}+\frac{1}{\eta}\left((u_{i}(t)-q_{i}(t))^{2}-(u_{i}(t)-q_{i}(t+1))^{2}\right)\right).$ (145) $$

From the definition of $\alpha_{i}(t)$ and ([145](https://arxiv.org/html/2509.09933v1#A3.E145)), we have

$$ $\displaystyle\sum\limits_{t=1}^{T}\alpha_{i}(t)\leq$ $\displaystyle\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-q_{i}(t)\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}(k_{i}(t)-u_{i}(t))^{2}$ $\displaystyle+\frac{1}{\eta(1-2\eta)}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left((u_{i}(t)-q_{i}(t))^{2}-(u_{i}(t)-q_{i}(t+1))^{2}\right)$ $\displaystyle=$ $\displaystyle\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}(k_{i}(t)-u_{i}(t))^{2}$ $\displaystyle+\frac{1}{\eta(1-2\eta)}\left(\sum\limits_{t=1}^{T}\left((u_{i}(t+1)-q_{i}(t+1))^{2}-(u_{i}(t)-q_{i}(t+1))^{2}\right)+(u_{i}(1)-q_{i}(1))^{2}\right)$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}(k_{i}(t)-u_{i}(t))^{2}$ $\displaystyle+\frac{1}{\eta(1-2\eta)}\left(\sum\limits_{t=1}^{T}\left(u_{i}(t+1)+u_{i}(t)-2q_{i}(t+1)\right)\left(u_{i}(t+1)-u_{i}(t)\right)+\frac{1}{4}\right)$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}(k_{i}(t)-u_{i}(t))^{2}$ $\displaystyle+\frac{1}{\eta(1-2\eta)}\left(2\sum\limits_{t=1}^{T}\left|u_{i}(t+1)-u_{i}(t)\right|+\frac{1}{4}\right),$ $$

which completes the proof.
∎

###### Lemma C.8 .

###### Proof.

#### C.4.2 Proof for the Stochastic Regime

From Lemma [C.8](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem8), setting $u_{i}(t)=k_{i}$ for all $i\in[d]$ and $t\in[T]$ and taking the expectation yield that

$$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\alpha_{i}(t)\right]\leq$ $\displaystyle\frac{1}{1-2\eta}\mathbb{E}\left[\sum\limits_{t=1}^{T}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-k_{i}\right)^{2}\right]+\frac{1}{4\eta(1-2\eta)}$ $\displaystyle=$ $\displaystyle\frac{1}{1-2\eta}\frac{\sigma_{i}^{2}}{n^{2}_{i}}P_{i}+\frac{1}{4\eta(1-2\eta)},$ $$

where $P_{i}$ is defined in ([96](https://arxiv.org/html/2509.09933v1#A3.E96)). By using this inequality instead of ([95](https://arxiv.org/html/2509.09933v1#A3.E95)) and repeating the same argument as that in Appendix [C.3.2](https://arxiv.org/html/2509.09933v1#A3.SS3.SSS2), we obtain that the upper bound of the regret is

$$ $\displaystyle\mathcal{O}\left(\frac{1}{1-2\eta}\sum_{i\in J^{*}}\frac{\lambda_{\mathcal{A}}\sigma^{2}_{i}}{\Delta_{i}}\log T\right).$ (146) $$

#### C.4.3 Proof for the Stochastic Regime with Adversarial Corruption

Here, we show a regret upper bound of the GD method under the stochastic regime with adversarial corruptions given:

$$ $\displaystyle R_{T}\leq R^{\mathrm{GD}}+\mathcal{O}(\sqrt{CMR^{\mathrm{GD}}})$ (147) $$

###### Proof.

Letting $u_{i}(t)=\mu_{i}$ for all $i\in[d]$ and $t\in[T]$ in Lemma [C.8](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem8) and taking the expectation yield that

$$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\alpha_{i}(t)\right]\leq$ $\displaystyle\frac{1}{1-2\eta}\mathbb{E}\left[\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-\mu_{i}\right)^{2}\right]+\frac{1}{4\eta(1-2\eta)}$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-2\eta}\mathbb{E}\left[\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-l^{\prime}_{i}(t)+l^{\prime}_{i}(t)-\mu_{i}\right)^{2}\right]+\frac{1}{4\eta(1-2\eta)}$ $\displaystyle=$ $\displaystyle\frac{1}{1-2\eta}\left(\frac{{\sigma_{i}}^{2}}{n^{2}_{i}}P_{i}+P^{\prime}_{i}\right)+\frac{1}{4\eta(1-2\eta)},$ (148) $$

where $P_{i}$ is defined in ([96](https://arxiv.org/html/2509.09933v1#A3.E96)) and the last inequality is obtained by a similar argument as for ([129](https://arxiv.org/html/2509.09933v1#A3.E129)). By using this inequality instead of ([95](https://arxiv.org/html/2509.09933v1#A3.E95)) and repeating a similar argument to that in the discussion of the LS method, we obtain the desired upper bound.
∎

###### Proof.

#### C.4.4 Proof for the Adversarial Regime

From Lemma [C.8](https://arxiv.org/html/2509.09933v1#A3.Thmtheorem8), we immediately obtain

$$ $\displaystyle\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\alpha_{i}(t)\leq$ $\displaystyle\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-u_{i}(t)\right)^{2}$ $\displaystyle+\frac{1}{\eta\left(1-2\eta\right)}\left(\frac{d}{4}+2\sum\limits_{t=1}^{T}\|\boldsymbol{u}(t+1)-\boldsymbol{u}(t)\|_{1}\right)$ (149) $$

for any $\boldsymbol{u}(t)=(u_{1}(t),\ldots,u_{d}(t))^{\top}\in[0,1]^{d}$.

First, we prove $R_{T}\leq\sqrt{\sum\limits_{i=1}^{d}n_{i}^{2}}\sqrt{\frac{\gamma}{\eta(1-2\eta)}(d+8V_{1})}+\mathcal{O}(W\gamma)$.
From ([46](https://arxiv.org/html/2509.09933v1#A3.E46)), letting $\boldsymbol{u}(t)=\boldsymbol{k}(t)$ in ([149](https://arxiv.org/html/2509.09933v1#A3.E149)), we can bound the regret as

$$ $\displaystyle R_{T}\leq$ $\displaystyle 2\gamma\sum\limits_{i=1}^{d}n_{i}\mathbb{E}\left[\sqrt{{\beta_{i}(1)}^{2}+\frac{1}{\gamma}\sum\limits_{t=1}^{T}\sum\limits_{t=1}^{T}\alpha_{i}(t)}\right]+\mathcal{O}\left(W\gamma\right)$ $\displaystyle\leq$ $\displaystyle 2\mathbb{E}\left[\sqrt{\gamma\left(\sum_{i=1}^{d}n^{2}_{i}\right)\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\alpha_{i}(t)}\right]+\mathcal{O}(W\gamma)$ $\displaystyle\leq$ $\displaystyle\frac{2\sqrt{\sum\limits_{i=1}^{d}n_{i}^{2}}}{\sqrt{\eta(1-2\eta)}}\mathbb{E}\left[\sqrt{\gamma\left(\frac{d}{4}+2\sum\limits_{t=1}^{T-1}\|\boldsymbol{k}(t+1)-\boldsymbol{k}(t)\|_{1}\right)}\right]+\mathcal{O}(W\gamma)$ $\displaystyle\leq$ $\displaystyle\sqrt{\sum\limits_{i=1}^{d}n_{i}^{2}}\sqrt{\frac{\gamma}{\eta(1-2\eta)}(d+8V_{1})}+\mathcal{O}(W\gamma),$ (150) $$

where the second inequality follows from the Cauchy-Schwartz inequality, the third inequality follows by setting $u_{i}(t)=k_{i}(t)$ for all $i\in[d]$ and $t\in[T]$ in ([149](https://arxiv.org/html/2509.09933v1#A3.E149)), and the last inequality follows from Jensen’s inequality. This becomes the desired path-length bound.

Next, we prove $R_{T}\leq\sqrt{\frac{1}{1-2\eta}\min\left\{L^{*},MT-L^{*},Q_{2}\right\}}$. For any $\boldsymbol{q}^{*}\in[0,1]^{d}$, letting $\boldsymbol{u}(t)=\boldsymbol{q}^{*}$ for all $t\in[T]$ in ([149](https://arxiv.org/html/2509.09933v1#A3.E149)), we have

$$ $\displaystyle\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\alpha_{i}(t)=\frac{1}{1-2\eta}\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(k_{i}(t)-m^{*}_{i}\right)^{2}+\frac{d}{4\eta(1-\eta)}.$ (151) $$

Using this inequality, we have

$$ $\displaystyle\mathbb{E}\left[\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\alpha_{i}(t)\right]\leq$ $\displaystyle\frac{1}{1-2\eta}\min\limits_{\boldsymbol{q}^{*}\in[0,1]^{d}}\left\{\mathbb{E}\left[\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{d}\left(\frac{a_{i}(t)}{n_{i}}\right)^{2}\left(l_{i}(t)-m^{*}_{i}\right)^{2}\right]\right\}+\frac{d}{4\eta(1-2\eta)}$ $\displaystyle\leq$ $\displaystyle\frac{1}{1-2\eta}\min\left\{R_{T}+L^{*},MT-L^{*}-R_{T},Q_{2}\right\},$ (152) $$

where in the last inequality, we set $\boldsymbol{q}^{*}=\mathbf{0}$ (resp. $\boldsymbol{q}^{*}=\mathbf{1}$) and use the same argument as that in Appendix [C.3.4](https://arxiv.org/html/2509.09933v1#A3.SS3.SSS4) for deriving the term with $R_{T}+L^{*}$ (resp $MT-L^{*}-R_{T}$), and $\boldsymbol{q}^{*}=\bar{\boldsymbol{\ell}}$ for deriving the term with $Q_{2}$, and this completes the proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: Please refer to the **Weaknesses** section above.
soundness: 3
strengths: 1. The author(s) compared the proposed algorithms and existing ones with Table 1.
2. The applications are discussed.
summary: The paper studied the regret minimization problem for combinatorial bandits where each arm is allowed to be pulled for more than once during each time step. It proposed and analyzed two algorithms for stochastic and adversarial settings respectively. It also conducted numerical results to indicate the superiority of proposed algorithms.
weaknesses: 1. Beginning from LINE 185, some applications of MP-CSB are discussed, where there is a contraint $\mathbf{a}\in \ldots$ for the optimal transport problem and another one for the knapsack problem. However, I failed to find a corresponding constraint in the problem formulation and hence feel a bit confused about the relation between the application scenarios and the studied formulation. 
My major concerns are as below:
1. A lower bound is discussed around LINE 176. However, the two works cited there studied the combinatorial bandits where one arm can be pulled at most once at each time step. I wonder how their results imply the lower bound here? Besides, if there is one, the lower bound should be included in Table 1.
1. The GenLBINFV algorithm is claimed to be best-of-both-world. However, there is no discussion on its comparison to a lower bound. How can the algorithm be claimed to be BOBW?
1. The pseudocode of GenLBINFV algorithm should be included in the main part of the manuscript as it is quite important.
4. More discussions on numerical results are appreciated.
1. This paper \url{https://proceedings.mlr.press/v51/jun16.html} also allowed multiple pulls of one single arm but focused on the pure exploration problem. Such works should be mentioned as related works.

Minor issue:
1. Table 1: The names of existing algorithms and the corresponding references should be included altogether.

---

confidence: 3
contribution: 1
initial_rating: 2
presentation: 1
questions: Several questions are included along with comments in the "Weaknesses" section above.
soundness: 2
strengths: - The authors consider a variant of the combinatorial semi-bandit problem with multiple-arm pulls (multiple base arms can each be pulled multiple times in a single round)    
- The authors propose a TS based algorithm (building on CTS from Wang and Chen 2018) for the multi-play CSB with stochastic environments and analyze regret and complexities (computational and storage)
- the authors propose a best of both worlds algorithm (building on LBINFV from Tsuchiya et al 2023) for multi-play CSB analyzing regret bounds for adversarial, stochastic, and stochastic with corruptions.  
- the authors include experiments, showing simple duplication and use of prior CSB methods is inefficient
summary: The authors consider a variant of the combinatorial semi-bandits problem where each arm can be played multiple-times in a round.  The authors propose a Thompson sampling based method for the stochastic setting as well as a best-of-both-worlds method, obtaining regret for stochastic regret for the former and adversarial (as well as stochastic rewards with adversarial corruptions) for the latter.  The authors also run experiments, showing their work outperforms combinatorial semi-bandit method baselines where arm duplications are used.
weaknesses: ### Major
- There is no discussion of technical challenges in the main paper in extending CSB methods to multi-play settings.  There may be some significant technical hurdles in the regret analyses, which could merit significance to the contribution, but they are not made clear in the main paper. 
    - The authors do contrast regret bounds and complexities against the trivial approach of duplicating arms and blindly applying CSB methods.  It is obvious that such an approach is wasteful (all the losses from playing arm $i$ should be used together).  There may be some significant technical hurdles in the regret analyses, which could merit significance to the contribution, but they are not made clear in the main paper. 
    - line 317 mentions generalizing LBINFV “is not straightforward.  We show that, by carefully leveraging $n_i$’s, LBINFV can be generalized to MP-CSB.” And terms like the regularizer (5) and parameters (6) include dependence on $n_i$, but from my reading I did not see a clear articulation of what was not straightforward.
- There is no discussion of, or even brief references to, past works on variants of “multi-play” bandits.  In terms of method design, analysis, and extent to which the changes from regular bandits is replicated here (in the change from CSB) vs extending CSB to multi-play has unique technical challenges?  from a quick search, I came across a few that sound relevant
    - “Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms” ICML 2022 this sounds fairly close to the setup considered in the paper, where each arm can be played multiple times (up to a capacity limit).  This ICML paper, interestingly, considers unknown capacities and an aggregate semi-bandit feedback for each arm (as opposed to a per-play feedback).     That presents challenges not present in the current work, as the capacity must be estimated.  

    - Komiyama et al. (2015) “Optimal regret analysis of Thompson sampling in stochastic multi-armed bandit problem with multiple plays” in ICML 2015 for multi-play MAB.  In this setting arms are not repeatable in a round).  This may have been later generalized by CTS  (there are also later multi-play TS methods like “Multiple-Plays Multi-armed Bandit with Accelerated Thompson Sampling” https://ieeexplore.ieee.org/document/10695179 )
    - There is also a large literature on multi-agent MAB (which is a generalization of multi-play MAB as the same arm can be played multiple times in the same round), including some with combinatorial action spaces (https://arxiv.org/abs/2405.05950 is one example came across, there are probably more that also consider combinatorial actions).   Works of this line would probably not generalize the problem the authors consider (e.g. the number of agents might need to match the per-round arm-play capacities $\{n_i\}$ for that to be the case), but there may still be relevant relations in terms of algorithm design and analysis that may merit discussion.     
    - More broadly speaking, there is a lack of references to recent works. From quick search of the pdf, there are no citations to works published or pre-prints posted in 2024 or 2025.  This brings concern about how well characterized the state of the related literature is.  CTS is from 2018, and 2023 is the latest of the CSB references.  

### Minor
- Table 1 references CTS and LBINFV but reports the regret bounds and complexities not of those works (designed for the single-play setting) but what they would be if the learner naively duplicated base arms and then applied those methods (oblivious to the duplication).  That is misleading to the reader.   It is fine to include those formulas as a simple baseline, but that should be in the text, not the table.  Instead, mark the sets of rows as being related but different problems and report CTS and LBINFV for the regret and complexity for the single-play settings they were designed for.
    - (minor) if the past works mentioned are not limited to linear, then that should be noted.
    - (minor) If there are any CSB works since 2018 that outperform CTS, they should be included (eg the table for CSB should not be limited to the two that are extended in this work)
    - (minor) I do not think linear bandit methods would be essential to include in the table
- I think using space in lines 256-311 to highlight improvements over the trivial duplication technique is not helpful (can keep it, but put it in the appendix), as duplication is obviously inefficient statistically and computationally.  Instead, it would have been much better that the authors discuss technical challenges (if any) in the regret analysis and high level descriptions of they overcame those challenges.

- For the motivating real-world applications, the descriptions need to be revised
    - line 198, for OT, a real-world application what is the “cost of edges it passes through”?  
    - The knapsack problem as described is not a multi-play problem.  There are simply $d$ items.  
- joint reward function non-linearity (for the stochastic setting)
    - Line 158 when does this assumption hold, other than linear?  If you want to claim your results hold for non-linear settings, you need to discuss what non-linear classes your results apply to.
    - the OT and knapsack examples have linear objectives (the authors later explicitly acknowledge that); the ad example does not explicitly state the objective function.  
- Figures 1 and 2 should have labels on the axes.  The main text does not clarify exactly what is plotted (what either axis is), just referring to figures as showing “the results”

### Very Minor
- line 307-311 memory discussion looks to be specializing to OT problem without mentioning that (I was confused by notation there at first)
- line 238 “output[s]”
- There are capitalization errors in the reference list, Kveton et al 2015 ref, Schrijver, combettes et al

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. What you describe at lines 161-164 is an adaptive (non-oblivious) adversary, right? If so, it would be better to clarify this aspect since it might not be straightforward to work with non-oblivious adversaries in partial feedback settings.
2. Could you comment on the different definition of the stochastic regime with adversarial corruption compared to the one from Ito (2021)? See my comment in **Weaknesses**.
3. The bands around the curves in the plots from the experiments section have semi-width equal to the standard deviation over the 100 trials, or don’t they? Please clarify this in the text.

**Minor comments and typos:**
- Line 137: the last $\\mathbb{R}$ is more precisely $[0,1]$ given line 133
- Line 155-156: “independent” random variables?
- Please, recall the definition of $N\_i(t-1) = \sum\_{s=1}^{t-1} a\_i(s)$ around eq. (3)
soundness: 3
strengths: The authors investigate a natural and interesting extension of the CSB problem, and clearly motivate their proposed techniques by observing crucial downsides coming from straightforward extensions of algorithms from prior work.
The generalized CSB problem considered in this submission is also well motivated by fundamental combinatorial optimization problems such as knapsack and optimal transport.
The proposed techniques work under assumptions with various degrees of generality, with the Thompson sampling algorithm in the stochastic setting with Lipschitz losses, as well as an INF-based algorithm that guarantees near-optimal regret even in adversarial environments.
summary: This work considers an extension of the well-studied combinatorial semi-bandits (CSB) problem, where at each round the learner selects a subset of base arms a loss that is a (Lipschitz) function of the losses of the individual selected arms, while they observe all of the latter losses.
The extension considered here allows the learner to select a single arm multiple times in the same round, hence seeing the choice at any round as a vector with non-negative integer values instead of a binary vector.
While this problem can be already solved by relying on existing approaches for linear bandits or CSB, the former approach would typically require to enumerate all combinatorial arms (which is generally impractical) while the latter requires to duplicate base arms and thus leading to possibly suboptimal performance and guarantees.
The authors show both a Thompson-sampling-based algorithm that achieves a variance-dependent logarithmic regret bound in the stochastic case where the loss can be any Lipschitz function of the losses of base arms, and an INF-based algorithm with log-barrier regularization and data-dependent learning rates that provides best-of-both-worlds regret guarantees in the case of linear losses.
Experiments on synthetic data further show the improvements achieved by the proposed algorithms for this generalized CSB problem, compared to the performance of adaptation of existing algorithms for the vanilla CSB problem via base arm duplication.
weaknesses: While the extensions of the algorithms lead to advantages compared to previous approaches, as underlined by the authors, the adaptation of existing techniques appears relatively straightforward.
Nonetheless, the authors show that carefully tuning the various steps of such algorithms (e.g., the extension of the log-barrier regularizer and the time-varying learning rate) and analyzing them carefully remain nontrivial tasks, at which they succeeded.

In the introduction, the description of the problem setting itself as an generalization of CSB in simple words is somewhat unclear and could benefit from a clearer presentation.
In particular, the authors mention decisions “taking non-negative integer values” without clearly stating in words what these integers represent.
One may intuitively deduce that these represent the multiplicity in the choice of each base arm, but this does not seem to be stated so explicitly, and a reader only truly understands this fact when reading the formal definition of the problem setting (which may be heavy to parse given the many objects that require a definition).

As a side note, the definition of the stochastic regime with adversarial corruptions at lines 168-171 seems slightly different from the more established one in Ito (2021).
In particular, the expectation in your definition is external, while Ito (2021) defines the corruption level $C$ by looking at mean losses of the stochastic ones and the corrupted ones (instead of the realized ones).
It would then seem that the $C$ you consider would need to be generally larger, and thus guarantees depending on your $C$ would be worse than depending on the original definition of the corruption level.
Anyhow, this is not a major weakness but it does require some comment in my opinion.

Another side note is about the values of $b\_i$’s from the duplication approach.
It is never specified, and thus left unclear, what values these parameters should be set to.
However, at first glance it would seem that setting $b\_i=n\_i$ would work as intended.
The authors, unfortunately, never comment on that and they also leave this point unaddressed (e.g., see line 424).
This should really be looked into in order to perform a fair comparison with existing approaches adapted by duplicating base arms, especially because previous algorithms would be at a clear advantage if it suffices to set $b\_i = n\_i$.

Finally, one of the main advantages of the proposed algorithms is runtime (and space) efficiency, but experiments never compare the runtime of the proposed algorithms to the baselines.
It then feels like experiments are not really covering all relevant aspects that should be empirically verified, leaving the reader with a sense of incompleteness.

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 3
questions: See Weak points.
soundness: 2
strengths: 1. A novel problem setting is addressed: MP-CSB extends CSB to non-binary, integer-valued actions, what extends MABs to broader scope of stochastic combinatorial optimization problems.
2. Algorithmic Efficiency: GenCTS avoids exponential enumeration of actions and produces in polynomial time
Regret bounds: both algorithms achieve state-of-the-art regret bounds
summary: This paper states the multi-play combinatorial semi-bandit (MP-CSB) problem, a generalization of the combinatorial semi-bandit (CSB) framework to multiple pulls per each arm on one round. This setting covers stochastic versions of optimal transport and knapsack problems, where binary decision CSB can hardly be applied. Two algorithms are proposed: GenCTS, a generalized Thompson sampling algorithm with O(log T) stochastic regret and GenLBINFV, and a best-of-both-worlds algorithm achieving variance-dependent logarithmic regret in the stochastic setting. Theoretical analysis guarantees improved regret bounds, and experiments confirm superior empirical performance.
weaknesses: 1. The practical motivation for the proposed MP-CSB setting is somewhat unclear. The authors propose two particular cases of the problem for practical inspiration: stochastic versions of the Optimal Transport problem and the knapsack problem. Unfortunately, they do not cite previous papers on the proposed cases, and their practical significance remains unclear.

2. The related work section seems incomplete. There are previous papers on non-binary combinatorial bandits, e.g., “Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit” by Nakamura et al. There are papers on stochastic versions of the Optimal Transport problem with bandits, e.g., “Bandit Optimal Transport” by Lorenzo Croissant. I expect a review with a comparison of the setting and algorithms to previous literature.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: 1. The authors claim that the GenCTS algorithm does not require enumerating all possible actions at the beginning of the game. However, for the stochastic setting, isn't this a property of the oracle rather than the algorithm itself? Isn't the competitor CTS or an algorithm like CUCB also computationally feasible when the action set is exponentially large in d? 

2. Is the compute complexity of the oracle included in the compute complexity of GenCTS? Isn't the competitor CTS also computationally feasible when the action set is exponentially large in d? The scalability of duplication CTS becomes an issue when the batch size is large. 

3. Many works in CMAB resort to approximation oracles. Combinatorial Thompson sampling may not work well with such types of oracles (See, e.g., Wang, Siwei, and Wei Chen. "Thompson sampling for combinatorial semi-bandits." International Conference on Machine Learning. PMLR, 2018). Does this mean that the results in this paper cannot be extended to learning algorithms that use approximation oracles? 

4. Multi-play setting is reminiscent of the batched-bandits setting (see, e.g., Gao, Zijun, et al. "Batched multi-armed bandits problem." Advances in Neural Information Processing Systems 32 (2019)). Please elaborate on how your work is connected to batched bandits.
soundness: 2
strengths: This paper bridges the gap between multi-play and combinatorial bandits. It focuses on a setup that includes stochastic and adversarial reward regimes as special cases. For different regimes, it proposes different algorithms inspired by Thompson sampling and best of both worlds algorithms from the literature. It offers rigorous theoretical analysis with regret bounds. The problem is relevant to applications where multiple actions must be selected simultaneously under constraints.
summary: The paper studies the multi-play combinatorial bandit problem, where at each round the learner selects a subset of arms (subject to combinatorial constraints) and receives a reward and observations from the selected arms with semi-bandit feedback. Under stationary and stochastic arm rewards, a variant of combinatorial Thompson sampling is shown to achieve $O(\log T)$ regret. When arm reward distributions are general, an algorithm that can adapt to attain best-of-both-worlds type guarantees is proposed. Its regret is bounded in the stochastic and adversarial regimes as well as a spectrum of regimes in between. Simulations are performed to compare the performances of the proposed algorithms with those from the literature.
weaknesses: 1. The main results extend known techniques rather than introduce fundamentally new methods. The writing of the paper does not clearly convey the technical novelty of the derivations; as a result, the technical novelty seems incremental. Please elaborate in detail why the multi-play CMAB setting is significantly more challenging to analyze than the single-play CMAB setting. 


2. Since this paper is highly theoretical in nature, the derivation of regret lower bounds for algorithms that do not use the duplication technique will greatly improve the contribution and will clearly demonstrate whether the derived upper bounds are optimal in some sense. 

3. The presentation is difficult to follow as the notation is very dense. While this is partly due to page limits, it negatively impacts the broader accessibility of the paper to the ICLR community. 

4. Simulations are limited in scope. No evaluation was performed in realistic settings where combinatorial multi-play naturally arises.


Decision: Reject