A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds
Authors: Taira Tsuchiya
Shinji Ito
Venue: NeurIPS 2024 poster (2024)
Keywords: follow-the-regularized-leader
adaptive learning rate
best-of-both-worlds algorithm
partial monitoring
graph bandits
online learning
Primary area: online_learning
TL;DR: We establish a new learning rate framework for FTRL in online learning with a minimax regret of $\Theta(T^{2/3})$ and then improve existing best-of-both-worlds bounds in partial monitoring and graph bandits.

Abstract: Follow-the-Regularized-Leader (FTRL) is a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of $\Theta(\sqrt{T})$ for the number of rounds $T$, and there are only a few studies on adaptive learning rates for problems with a minimax regret of $\Theta(T^{2/3})$, which include several important problems dealing with indirect feedback. To address this limitation, we establish a new adaptive learning rate framework for problems with a minimax regret of $\Theta(T^{2/3})$. Our learning rate is designed by matching the stability, penalty, and bias terms that naturally appear in regret upper bounds for problems with a minimax regret of $\Theta(T^{2/3})$. As applications of this framework, we consider three major problems with a minimax regret of $\Theta(T^{2/3})$: partial monitoring, graph bandits, and multi-armed bandits with paid observations. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adversarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of $\Theta(T^{2/3})$.

A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of (TT2/3) and its Application to Best-of- -ia--off-Btt--orlds
Taira Tsuchiya The University of Tokyo and RIKEN tsuchiya@mist.. t.u-tokoo.as ac.
Shinji Ito
The University of Tokyo and RIKEN chinji@mist. a.u-tokyo.ac ac.
Abstract
(FTRL) is powerful framework for various on- line learning problems. By designing regularizer and learning rate be adap- tive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of @(VT) for the number of rounds T, and there are only a few studies on adaptive learning rates for prob- lems with a minimax regret of @ which include several important problems dealing with indirect feedback. To address this limitation, we establish new adap- tive learning rate framework for problems with minimax regret of (TT2/3). Our learning rate is designed by matching the stability, penalty, and bias terms that natu- rally appear in regret upper bounds for problems with a minimax regret of (TT2/3). consider three major problems with min-
Bellowtth-Regulariieed
As applications of this framework, imax regret of (T72/3) partial monitoring, graph bandits, and multi-armed ban- dits with paid observations. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Woi Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adver- sarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of (T7233).
Introduction
Online learning is a problem setting in which a learner interacts with an environment for rounds with the goal of minimizing their cumulative loss. This framework includes many important online decision-making problems, such as expert problems [21, 38, 57], multi-armed bandits [6. 8, 33), linear bandits [1, 14), graph bandits [4, 42], and partial monitoring [9, 11].
For the sake discussion in a general form, we consider the following general online learning framework. In this framework, a learner is initially given finite action set A [k] := {1,..., k) and an observation set O. At each round t E [Z']. the environment determines a loss function e A [0, 1], and the learner selects action A, E AA based on past observations without knowing 4. The learner then suffers a loss ((4)) and observes a feedback or E O.O. The goal of the learner is to minimize the (pseudo-)regret RegT, which is defined as the expectation of the difference between the cumulative loss of the selected actions (Ar)²" and that of an optimal action a" E A fixed in hindsight. That is, Reg- E (A,) - Σ (e(a")] for a" arg minge E E (c(4)]. For example in the multi-armed bandit problem, the observation is o, = (At).
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

-eeon-tte--egulrizeeee (FTRL) is highly powerful framework for such online learning problems. In FTRL, probability vector 9: over A, which is used for determining action selection probability Pt so that A, ~ Pt, is obtained by solving the following convex optimization problem:
EE Scb(a)
ge arg min aigmin gEPa
where Pk is the set of probability distributions over A = [R]. e, Pk. R is estimator of loss function 6, Br > 0 is (a reciprocal of) learning rate at round 6, and d is convex regularizer. FTRL known for its usefulness in various online learning problems [1, 4, 8. 27, 37J. Notably, FTRL can be viewed as a generalization of Online Gradient Descent [63] and the Hedge algorithm [21, 38, 57], and is closely related Online Mirror Descent [36, 45].
The benefit of FTRL due to its generality is that one can design its regularizer vb and learning rate (Be), so that it can perform adaptively to various properties of underlying loss functions. The adaptive learning rate, which exploits past observations, is often used to obtain such adaptivity. In order to how it is designed, consider the following stability-penaate decomposition, well-known in the literature [36, 45]:
T
T 31h1 + > (B. -1-1) 2-2
Regr X
Zt
+
(2)
B
stability
penalty
Intuitively, the stability term arises from the regret when the difference in FTRL outputs, 2; and Tr-1, is large, and the penalty term is due to the strength of the regularizer. For example, in the Exp3 algorithm for multi-armed bandits [8], ht is the Shannon entropy of xa or its upper bound, and ,, is the expectation of - of the importance- estimator & or its upper bound.
Adaptive learning rates have been designed so that it depends on the stability or penalty. For ex- ample, the well-known AdaGrad [19, 44] and the first-order algorithm [2] depend on stability com- ponents {==) to determine 3e. More recently, there are learning rates that depend on penalty components (h.) 54] and that depend on both stability and penalty components [26, 28, 55].
However, almost all adaptive learning rates developed so far have been limited to problems with minimax regret of O (v)T), and there has been limited investigation into problems with minimax regret of (T2333 [25, 54]. Such online learning problems are primarily related to indirect feedback and includes many important problems, such as partial monitoring [9, 34], graph bandits [4], dueling bandits [51], online ranking [12), bandits with switching costs [18], and multi-armed bandits with paid observations [53]. The ( problem is distinctive also due to the classification theorem in partial monitoring [9, 34, 35], which is very general problem that includes wide range of sequential decision-making problems as special cases. is known that, the minimax regret of partial monitoring games can be classified into one of four categories: 0, ((VT), ((T2/3), or S((T). Among these, the classes with non-trivial difficulties and particular importance are the problems with minimax regret of ((VT) and (T72/3).
Contributions To address this limitation, we establish new learning rate framework for online learning with minimax regret of ((22/3). Henceforth, we will refer to problems with minimax regret of ((T2/33 as hard problems to avoid repetition, abusing the terminology of partial monitor- ing. For hard problems. it is common to combine FTRL with forced exploration [4, 17, 34, 51]. In this study, we first observe that the regret of FTRL with forced exploration rate Yt is roughly bounded as follows:
T
T - 1 (6--B-1)h/4 t=2
Regr
Zt
Bih1
(3)
Bev
stability term
penalty term
bias term
Here, the third term, called the bias term, represents the regret incurred by forced exploration. In the aim of minimizing the RHS of (3), we will determine the exploration rate "tt and learning rate
3 so that the above stability, penalty, and bias elements for each E [T] are matched, where the matching learning rate (SPB -Sttmhathingg. This
resulting learning rate is called PebblittyPeenlty

---

Table I: Regret bounds for partial monitoring, graph bandits, and multi-armed bandits (MAB) with paid observations. The number of rounds is denoted as T, the number of actions as k; and the mini- mum suboptimality gap as Amin- The variable cg is defined in Section 5, D is constant dependent on the outcome distribution. The graph complexity measures 6, 8*, satisfying 8* < á for graphs with no self-loops, are defined in Section 6, and 0 < ó is the fractional weak domination number [13]. The parameter e is the paid cost for observing a loss of actions. AwSB is the abbreviation of the adversarial regime with self-bounding constraint. MS-type means that the bound in AdvSB has form similar the bound established by Masoudian and Seldin [43].
Setting
Reference
Stochastic
Adversarial
AwSB
Partial
[30]
D log T
monitoring
[37]
(cgT))//(log (log k)
(with global
ob log T log(KT
observability)
[54]
A
(cgT))//9(1)) (log T (log()))))
c k logT
[56]
(co7)) (logT))//
A
c log le log'
[15]
(cc7) (log ((gg))//(loo k)1/3
A
c log k log A
Ours (Cor. 9)
(cg7) (log
V MS-type
Graph
[4]
(6 log 1)1/314/3
bandits
[13]
(ō" log k) ///33/33
(with weak
8 log T log(kT)
observability)
[25]
A2
log T log(k)))
8 log llo T
[15]
(6 log ////////3
A2 min
8 log k log
Ours (Cor. 11)
(6 log k)
MS-type
A min
MAB with
[S3]
(ck log k) 13///3 V
paid observations
max(c. log log &s log
Ours (Cor. 17)
(ck log + /Togk
MS-type
2
"The framework in [15] hierarchical reduction-based approach, rather than direct FTRL method, discarding past observations as doubling-trick.
"The hounds in [15] depend on 6, but their framework with the algorithm in [13] can achieve improved bounds replacing 8 with 8* 8.
was inspired by the learning rate designed by matching the stability and penalty terms for problems with minimax regret of @(vT) [26]. Our learning rate is simultaneously adaptive to the stability component in and penalty component h4, which have attracted attention in very recent years [26, 28, 55]. The SPB- 11--mathhing learning rate allows to upper bound the RHS of (3) follows:
Theorem (informal version of Theorem 6). There exists learning rate (3:), and exploration rate
(Tt) which the RHS of (3) is bounded by O( Ze log(sT)) 2/3 + (V (Vemax/maxx/8 2/33 for any = 2 1/T, where zmax m 2t and hmax m h4
Within the general online learning framework, this theorem allows us to prove the following Best- (BOBW) guarantee [10, 58, 61], which achieves an O(log T') regret in the stochastic regime and an (TT233) regret in the adversarial regime simultaneously:
Theorem 2 (informal version of Theorem 7). Under some regularity conditions, an FTRL-based algorithum with SPB SPB-matching achieves Regz S (mss)) 1/322/3 in the adversarial regime. In the stochastic regime, if Vzih, S/pr(1 qta") ) holds for FTRL output qe EPr and p1 > for all te (T), the same algorithm achieves Regr
P1 A log(T ( for the minimum suboptimality gap Amin-
To assess the usefulness of the above result that holds for the general online learning framework, this study focuses two major hard problems: partial monitoring with global observability, graph
3

---

bandits with weak observability, and multi aumee bandits with paid observations. We demonstrate that the assumptions in Theorem 2 are indeed satisfied for these problems by appropriately choos- ing the parameters in SPB-matching, thereby improving the existing BOBW regret upper bounds in several respects. To obtain better bounds in this analysis, we leverage the smallness of stability components 2t, which results from the forced exploration. Additionally, SPB-matching is the first unified framework to achieve a BOBW guarantee for hard online learning problems. Our learning rate is based surprisingly simple principle, whereas existing learning rates for graph bandits and partial monitoring are extremely complicated (see [25, Eq. (15) and [54, Eq. (16)]). Due to its sim- plicity, we believe that SPB- -matmhhin will serve as foundation for building new BOBW algorithms for a variety of hard online learning problems.
The SPB- 3PB-matching framework, though omitted from the main text due to the space constraints, also applicable to the multi-armed bandits with paid observations [53], whose minimax re- gret with costs is ((T2/3). We can show that the regret with paid costs, Regī. is roughly bounded by RegT
O log k)2/3372/3 + vT Voloo k) in the adversarial regime and Regr O(mxx fc, 1 } log & log T/4 in the stochastic regime for the cost of observation c. The bound for the adversarial regime is of the same order as [53, Theorem 3]. The detailed problem setup, regret upper bounds, and regret analysis can be found in Appendix G.
Although omitted in Theorem 2, our approach achieves a refined regret bound devised by Masoudian and Seldin [43] in the adversarial regime with self bounding constraint [61]. which includes the stochastic regime, adversarial regime, and the stochastic regime with adversarial corruptions [41] as special cases. We call the refined bound MS-r bound, named after the author. The MS-type bound maintains an ideal form even when C (T) or Amin @(1/VT) (see [43] for details), and our bounds are the first MS-type bounds for hard problems. A comparison with existing regret bounds summarized in Table
2 Preliminaries
Notation For natural number n E N, we let [n] (I...., n). For vector æ, let x; denote its i-th element and ||>||p the fy-norm for p E [o]. Let Pa = {p E [0, 1 ||p|| 1} be the (k- 1)- dimensional probability simplex. The vector is the i-th standard basis and 1 is the all-ones vector. Let 2x y) denote the Bregman divergence from y to x induced by a differentiable convex function vh: Des (zr, y) - (xx)) - (ly) (Vubyy, To simplify the notation, we sometimes write (a, ) as 01:T and f = O(g) as f We regard function f: A = [k] + R as k-dimensional vector.
General online learning framework To provide results that hold for wide range of settings, we consider the following general online learning framework introduced in Section 1.
At each round E [T) = (1,...,T): T):
1. The environment determines loss vector e;: A + [0, 1]:
2. The learner selects action A, E A based on pt E Ps without knowing ty;
3. The learner suffers loss of (A,) E [0, 1] and observes a feedback 0z E O.
This framework includes many problems such as the expert problem, multi-armed bandits, graph bandits, and partial monitoring special cases.
Stochastic, adversarial, and their intermediate regimes Within the above general online frame- work, we study three different regimes for sequence of loss functions (fz) In the stochastic regime, the sequence of loss functions is sampled from unknown distribution D in i.i.d. manner. The suboptimality gap for action a E A is given by A, = EE (a) - (,(a)) )} and the minimum sub- optimality gap by Amin min Ag. In the adversarial regime, the loss functions can be selected arbitrarily, possibly based on the past history up to round t- 1.
We also investigate, the adversarial regime with self-bounding constraint [61], which is an inter- mediate regime between the stochastic and adversarial regimes.
Definition 3. Let A E 1 and C > O. The environment is in an adversarial regime with a (A, C,T) self- bouldigunding constraint if it holds for any algorithm that Regr E [ AA, -C].

---

From the definition, the stochastic and adversarial regimes are special cases of this regime. Addition ally. the well-known stochastic regime with adversarial corruptions [41] also falls within this regime. For the adversarial regime with self- bofudinnndigg constraint, we assume that there exists unique opti- mal action a". This assumption standard in the literature of BOBW algorithms (e.g., [22, 39, 58
3
SBP-matching: Simple and adaptive learning rate for hard problems
This section designs new learning rate framework for hard online learning problems.
3.1 Objective function that adaptive learning rate aims to minimize
In hard problems. the regret of FTRL with somewhat large exploration rate 7t known to be bounded in the following form [4, 25, 54]:
T
T
T Σ 1=1
Regr -
(Be- - B1-1) + 3.7
2t
7
(4)
for some stability component 2; and penalty component he, where set 38+1 BT and 30 0 for simplicity. Recall that the first term is the stability term, the second term the penalty term, and the third term is the bias term, which arises from the forced exploration.
The goal when designing the adaptive learning rate to minimize (4), under the constraints that (3e), is non-decreasing and 3r depends (Zis,, hi or (Z1:--1 h1x). A naive way choose y to minimize (4) is to set "t / so that the stability term and the bias term match. However, this choice does not work well in hard problems because to obtain a regret bound of (4), a lower bound of %/ u4/ / for estimator &, (see e-g. Eq. (61) for partial monitoring and Eq. (79) for graph bandits). Therefore, we consider exploration rate of ? % + u Br for 7/ = / 3e and some u > O, where Y chosen so that the stability and bias terms are matched. With these choices,
u4 0 is needed. This lower bound is used to control the magnitude of the loss
Eq. (4)
-
T
2t.
+ (Be - Be-1) + 7/6
Ut 3r
))
Birk
1=1
2
+
+ (Be Be-1)dbe) = F(B FisT, W1.T h.T)).
(5)
Br
B
1=1
Note that the first two terms in F. 2 2 + ut/ Bt, come from the stability and bias terms and the last term, (B. hr, is the penalty term. In the following, we investigate adaptive learning rate (3.)²= that minimizes F (5) instead of (4).
3.2 -tabllity- matching learning rate
We consider determining (Be), by matching the stability bias terms and the penalty term as 2/2// Be + ut/B = (3t - 31-1)h4. Assume that when choosing Sr, we have an access to he such that h4 S Jy. Then, inspired by the above matching, we consider the following update rules:
21
Ut
Uc-1
(Rule 1) 8g = B +
2
(Rule 2) 3r = B +
2
(6)
Tte
3
3
7tg
B
3
We call these update rules Caabilit-Peenltyy following the simple principle of matching the stability, penalty, and bias elements, and Rules I and
Matching (SPB-matching). These are designed by
'This particularly the case when use the Shannon entropy or Tsallis entropy regularizers, which is weaker regularization than the log- barrier regularizer.
In each problem setting, we will prove h, S chç-1 for some constant e (sec Assumption (i in Theorem 7 and proofs of Theorems 8, 10 and 16). Hence if we set h + ch--1, we have ht < hu. Note that ft. can be calculated from the information available at the end of round f 1, and thus it can be used when determining 3r.
5

---

2 differ only in the way indices are shifted." 3 For the sake of convenience, we define 11 and G2 by
Gi(zu.,
Vz
1/3 Ga(uEr,hrr))
U
Eom1 V2a/l1a)
=== Ug/ha
Define Smax ma) Ze. Umax m Ue, and Amax maxe /y h4. Then, using SPB- matching rules (6), we can upper-bound F terms of G1 and G2 as follows:
Lemma 4. Consider SPB-matching (6) and suppose that he S hi for all t E [T]. Then, Rule achieves F(B1r, R1,, urr, hyr) S 3.2G1 (21:7, MET) + 2G2(u1:r, hur) and Rule achieves F(B1T,215 PI,T, WI.T, hrr) S 4G (Z1:T, h2rr-1 +-3r-))+332( (w1.T, (3 +10 Zmax/ B1 + 51 / B1 + B.h1.
The proof of Lemma 4 can be found in Appendix B.I. One can see from the proof that the effect of using 2 /3, + u/3. instead of % / only appears in G2, which has a less impact than G1 when bounding F. We can further upper- G1 as follows:
Lemma 5. Let (=))=1 S Rgo and (1e)==1
C Rz0 be any non-negative and positive se- 0, 0, 0 and 0g hmax and de-
quences, respectively. Let Og 01
fine Tj = [T] fj-1 2 h4 > 03} for j
E
[]]
and T541 = E (T] 0, 2 he). Then,
G1 G1(21,1 I 3 ==1 10,- EnET, zzz)
2/3
This implies that for all
holds that
T
3
G((E1T,hiT) I min (22
2gh1
+ 2-
Zmax Dmxx
T
Σ t=1
v Ve 2e
Combining Lemmas 4 and and the bound on G2 in [26, Lemma 3], we obtain the following theorem.
Theorem 6. Let (r) R2o and (ho S B Suppose that The satisfies he S Tor all t E [T]. Then, if Bi is given by Rule 1 in (6), then for all 1/T it holds that
V the Log(eT) + (V
(
F(Brr, 21, un.r har) S min
Σ
Pomaxx
Σ
V
T uhhe log(ET)
+
min
+ "mmax Rmax/
Ue Reaax
(8)
If Be is given by Rule 2 in (6), then-orr all e 2 1/T holds that
(V Zmaxx Baax
F(B1T1 uI.T h1T) S min Σ
V 2eh log(ET)
+
V2
Σ
Ze amax
min Σ uhet (o(ss)++ M Draxe
U Praax
Zmax
Umax
+ +
(9)
B
B
Note that these bounds are for problems with a minimax regret of @(T2/3). Roughly speaking, our 1/3 and differ from the existing stability-penalyy bounds have order of [Ern v seheer log
adaptive-type bounds of ΣT= 2 log for problems with a minimax regret of ((VT) [26, 55). We will see in the subsequent sections that our bounds are beneficial as they give nearly optimal regret bounds in stochastic and adversarial regimes partial monitoring, graph bandits, and multi- armed bandits with paid observations.

---

Algorithm/ 1: Best-of-both-worlde framework based on FTRL with mPB-matching learning rate and Tsallis entropy for online learning with minimax regret of (
input: action set .A, observation set O exponent of Tsallis entropy a, $1, 3
for f 1.2.... do
Compute 4: E Pk by (10) with loss estimator 4 Set h4
Ha (gt) and 2,, Me 2 0 defined for each problem. Compute action selection probability pt from I by (11).
Choose A, A so that Pr[At- = i Pt] Pri and observe feedback or O.
7
Compute loss estimator & based on Pt and Oz.
Compute Bu+1 by Rule of SPB- SPB-matching in (6) with h4+1 h4-
4 Best-of-both framework for hard online learning problems
Using the SPB-matching learning rate established in Section 3, this section provides a BOBW algo- rithm framework for hard online learning problems. We consider the following FTRL update:
1-1 (). + B.(H-H +
9: = arg min PEPN
a E (0, ā = a, (10)
where H. is the a-Taaalis entropy defined as = - Ep (pf -p.), which satisfies (p) 2 and (e;) = O. Based this FTRL output qt, set h4 Ha(a)) which satisfies h2 mmax- Additionally, for qe and some pa E Pk. we use the action selection probability E Px defined by
U 3
2t
Ut
Dr = (1 - 70) + To Po for 7t 1
(11)
B
3.
where 3n is chosen so that n E 1/2]. Let K /maax/ B1 + Umaax 11 + -1h1 + 3h for (1(1/k) and let E- be the expectation given all observations before round t. Then the above procedure with Rule 2 of SPB-matching in (6). summarized in Algorithm 1, achieves the following BOBW bound:
Theorem 7. Consider the general online learning framework in Section 2 with |1e I 1. Suppose that Algorithm 1 satisfies the following three conditions (i)-;;;):
(i) Regr S E
Σ (le a: ca-) +
Σ
Yt
(12)
(i) E (le.9 - 9+1) - (H. 4t)
2t BeTk"
(mi he S h--1
Then, the adversarial regime, Algorithm I achieves
Regr = =O( / 1/3/2/33 V Umaxhi +
(13)
In the adversarial regime with a (A, C, self----l-n constraint, further suppose that Vz, S Vpi (1 - )tar) and ugl, S p2 (1- (ta-)
(14)
are satisfied for some P1, P2 for all E [T]. Then, the same algorithm achieves
Regr =0 0 P
log (TA + ( (Chp
TAmin
))
1/3
(A2 2 log
+ kg'
(15)
A
min
min
C
for p (ax )2) and ni' = K + ((Emmxehh)) 1/3 + v Vumasch
hi
(1/A3
min + CC/A min
2/3
when T 2
1/43. min + C/Amin T, and Regr (1 2/3,2/13 117 when T <T.
The proof of Theorem 7 relies on Theorem 6 established the last section and can be found in
Appendix C. Note that the bound (15) becomes the bound for the stochastic regime when C = O.
'The information available for determining Br differs between Rule I and Rule 2, and Rule is included due to theoretical interest and will not be used after this section.
7

---

5
Case study (1): Partial monitoring with global observability
This section provides a new BOBW algorithm for globally observable partial monitoring games.
5.1 Problem setting and some concepts in partial monitoring
Partial monitoring games A Partial Monitoring (PM) game 9 = (C, Φ) consists of a loss matrix LE E [0, 1] and feedback matrix E E where l and are the number of actions and out- comes, respectively, and Σ is the set of feedback symbols. The game unfolds over T rounds between the learner and the environment. Before the game starts, the learner given L and @. At each round I E (7), the environment picks an outcome E [d]. and then the learner chooses action A, E [k] without knowing zt. Then the learner incurs an unobserved loss LA,z, and only observes a feed- back symbol 0r = Φ A.zz. This framework can be indeed expressed as the general online learning framework in Section 2, by setting O = Σ, (() = Lax, = e. Lez, and = PA...
We next introduce fundamental concepts for PM games. Based on the loss matrix L, we can decompose all distributions over outcomes. For each action a E [k], the cell of action a, de- noted as Ca, is the set of probability distributions over [d] for which action a is optimal. That is, C. {u Pa: maxbe[H)(&a
()) u s 0}, where la R is the a-th row of L.
To avoid the heavy notions and concepts of PM, we assume that the PM game has no duplicate actions * b such that la lg and its all actions are Pareto optimal; that is, dim(Ca) = d for all a E [M]. The discussion of the effect of this assumption can be found e.g. in [34, 37].
Observability and loss estimation Two Pareto optimal actions and b are neighbors if dim(C, n C,) = 2. Then, this neighborhood relations defines globally observable games, for which the minimax regret of (TT2/3) is known in the literature [9, 34]. Two neighbouring actions a and b are globally observable if there exists function We(a.)) : [k]] Σ - R satisfying
Ee=1 We(a,b) (c, 2cz) Lax Lae for all [d].
(16)
where e(a, b) = {a, bj. A PM game said to be globally observable if all neighboring actions are globally observable. To the end, we assume that G is globally observable." 4
Based on the neighborhood relations, we estimate the loss difference between actions, instead of estimating the loss itself. The in-tree is the edges of a directed tree with vertices [b:] and let 9 S [k] [k] be in-tree over the set of actions induced by the neighborhood relations with arbitrarily chosen root r E [k:]. Then, we can estimate the loss differences between Pareto optimal actions as follows. Let G(a, o)b Exepath yr (b) wa(a, 0)) for E [k)), where path o (b) is the set of edges from b E [ki] to the root r on T. Then, is known that this G satisfies that for any Pareto optimal actions a and b, > (G(c, 2ew)a - G(b, Pow)o) = Lor - Love for all x E [d] (e.g., [37, Lemma 4J). From this fact, one can see that we can use Tr G(A,, a (PA.../PP... \/PLA, E IR as the loss (difference) estimator, following the standard construction of the importance-weighted estimator [8. 36). fact, He satisfies Aecop, 1 Veol Ed= (G(c, oz)a Gic, ot)s) = Lax - Loz. We let eg = max(1, o| be a game- dependet constant, where ||''|| = (M) G(a,
5.2 Algorithm and regret upper bounds
Here, we present a new BOBW algorithm based on Algorithm 1. We use the following parameters for Algorithm 1. We use the loss (difference) estimator of Ee = De. We set Po in (11) to Po = 1/k. For T, E arg (aX Ut and tt- = min miin - (...) let
81 2 1
64c
32c
2
4eg
Σ
2-0 + qio ) Ut = 1 a 4e=
2-a
8eg 1-a
(17)
(1 (1-a) 22-
1 1- ar
Note that Zmax
I-a' Umax I-a'
4e2
8eg and /max hi 1k--a Then, we can prove the following:
Theorem 8. In globally observable partial monitoring, for any a E (0, 1), Algorithm I with (17)
satisfies the assumptions of Theorem 7 with p1 a1-aa and p2 = O Cgk' all-a]
"Another representative class of PM locally observable games, for which we can achieve minimax regret of O (VT)). See [9. 36, 37] for local observability and [54, 55] for BOBW algorithms for it.
8

---

The proof of Theorem 8 is given in Appendix E. Setting = 1 1/llg k) gives the following: Corollary 9. In globally observable partial monitoring with T 2 Algorithm I with (17) for a = 1/log k) achieves
0 ((cgT) 2/3 (log k) 1/3
+ 1))
in adversarial regime
o log h A
(C2c log
l
TTAmin
)) 1/3
Regr
log (TA +
log
+ +k'
(18)
A
C
in adversarial regime with a (A, -,es sellbbooidu constraint.
Here, if we use B1 = /4cg/(1 - a.). which satisfies (17), K O(e] log + / k)$/2) and
n = K O1(e) (log (log k)1/3 + /eg log k)( 1 +
Amin 2_)3
min
This regret upper bound is better than the bound based on FTRL in [54, 56] both stochastic and adversarial regimes, notably by a factor of log T or k in the stochastic regime. The bound for the adversarial regime with a (A, C, -ee-----buuundnng constraint is the first MS-type bound in PM. The upper bounds for the adversarial regime and stochastic regime are optimal in terms of T [9. 30]; however, even without considering BOBW guarantees, the optimality with respect to other variables k. m, and d is unclear (ef. [36, Section 37.9)), and exploring this is important direction for future work. As discussed in Section I, employing the black-box reduction approach in [15] also allows us to achieve an upper bound of the same order as upper bound. Nevertheless, previously mentioned, the blackbox approach is a complicated approach involving multi-stage reductions and has the drawback of discarding past observations, similar to the doubling-trice Hence, demonstrating that using the FTRL framework alone can achieve the same upper bound is a significant theoretical advancement.
6
Case study (2): Graph bandits with weak observability
This section presents a new BOBW algorithm for weakly observable graph bandits.
6.1 Problem setting and some concepts in graph bandits
Problem setting In the graph bandit problem, the learner is given directed feedback graph G
(V, F) with V = [k] and C V x V. For each i E V. let (1) = (j E V: (j,1) E E} and (o (i) {j V: (i,5) E) be the in-neighborhood and out-neighborhood of vertex i V, respectively. The game proceeds as the general online learning framework provided in Section 2, with action A V. loss function e; V + [0, 1]. and observation o, (fx(G): j E Nout (1.))
Observability and domination number Similar to partial monitoring, the minimax regret of graph bandits is characterized by the properties of the feedback graph G [4]. A graph G is ob- servable if it contains no self-loops, N Nin(i) * 0 for all i E V. A graph G' is strongly observable if i (i) or V\ {i) C (i) for all i E V. Then, a graph G weakly observable if it observable but not strongly observable." The minimax regret of the weakly observable is known be ((T2/3).
The weak domination number characterizes precisely the minimax regret. The weakly dominating set D V is set of vertices such that {i E V: & (oo)(())) S UveD (1). Then, the weak domination number 8(G) of graph G is the size of the smallest weakly dominating set. For weakly observable G. the minimax regret of (6'
is known [4]. Instead, our bound depends on the fractional domination number 8* (G), defined by the optimal value of the following linear program:
minimize Σiey
subject to ΣIEN T. 2 1 Vj E VV, 0 S x; ViViE..
(19)
We use (xj)sey to denote the optimal solution of (19) and define its normalized version u E Pk by u, = x Ljev zJ.. The advantage of using the fractional domination number mainly lies in its computational complexity; further details are provided in Appendix F.I.
"Siiilar to the locally observable games of partial monitoring, we can achieve an O(vT) regret for graph bandits with strong observability. See e.g. [4] for details.

---

6.2 Algorithm and regref analysis
Here, we present a new BOBW algorithm based on Algorithm We use the following parameters for Algorithm 1. We use the estimator & E F defined by lu = fas 1i E (ott((e) for Pa = EjeN"(g Ptj, which is unbiased and has been employed in the literature [4, 13]. We set po in (11)
Prc
to Po = u. For 1 arg ma Uti and gt+ min(g 1 9.F, let
640
32vk0
48
88
81 2 1
B
(1 V/3
Σ
98 + 2-a
2 2-a
Ur
4to 1-a (20)
GEV
Note that mmax I-a' Umax I-a' and hmaa h1 - Then, we can prove the following:
46"
88"
Theorem 10. In the weakly observable graph bandit problem, for any (0, Algorithm I with (20) satisfies the assumptions of Theorem 7 with p1 P2 θ
1-1--a) all-aj
The proof of Theorem 10 is given in Appendix F. Setting a 1 1/oo k) gives the following:
Corollary 11. In weakly observable graph bandits with T 2 max (log h)² r). Algorithm with (20) for a 11-11 1/oog k) achieves
( 2/3 (log ))3/3 + 1))
in adversarial regime
8" log A 2 min
log (Tn) (
CC28*
(C28+log log
T TTAiin
))
1/3
Regr
log
+ k²
(21)
A min
in adversarial regime with a (A, C, --se----l--uuuuniing constraint.
Here, if we use B1 = 646 /(1 - ox), which satisfies (20), k = O log + 13/2 k)5/2) and
n' + O(((5* log 1/3 3 + v log ( C (2/3)
Dmmin
Our bound is the first BOBW FTRL-based algorithm with the O(log T) bound in the stochastic regime, improving the existing best FTRL-based algorithm in [25]. Compared the reduction-based approach in [15], the dependences on T are the same. However, our bound unfortunately depends on the fractional domination number 8* instead of the weak domination number d, which can be smaller than 5t Roughly speaking, this comes from the use of Tsallis entropy instead of Shannon entropy employed for the existing BOBW bound [25]. The technical challenges of making bound depend on ô instead of 8* or the weak fractional domination number 8' are further discussed Appendix F.3. algorithm discards
Still, we believe that our algorithm can perform better since the reduction- past observations as the doubling trick. Furthermore, the bound for the adversarial regime with a (A, C, -re-ssff-oouddig constraint is the first MS-type bound in weakly observable graph bandits.
Conclusion and future work
In this work, we investigated hard online learning problems, that is online learning with minimax regret of ((T2/3), and established simple and adaptive learning rate framework called stability- penalty-bias matching (SPB-matching). The SPB-matching allows us to prove a regret bound of 2/3 for the stability component 2 and the penalty component h441, which bounds for problems with a minimax regret of O(VT) [26, 55]. We showed that FTRL with the SPB-matching learning rate and the Tsallis entropy regularizer improves the existing BOBW regret bounds based on FTRL for two typical hard problems with indirect feedback, partial monitoring with global observability, graph bandits with weak observability, We also showed that the SPB-matching can be applied to derive the first BOBW regret bounds for multi-armed bandits with paid observations.
differs from the existing
Interestingly, the optimal exponent of Tsallis entropy in these settings is 1 1-11(llg k), suggesting the
reasonableness of using Shannon entropy in existing algorithms for partial monitoring [37] and graph bandits [4]. Our learning rate is surprisingly simple compared to existing ones for hard problems [25, 54]. Hence, is important future work to investigate whether this simplicity can be leveraged to apply SPB-matching to other hard problems, such as bandits with switching costs [18] and dueling bandits with Borda winner [51].
10

---

Acknowledgments and Disclosure of Funding
The authors are grateful to the anonymous reviewers for their insightful feedback and constructive suggestions, which have helped to significantly improve the manuscript. TT was supported by JST ACT-X Grant Number JPMIAX210E and JSPS KAKENHI Grant Number JP24K23852.
References
[1] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing the dark: An efficient algorithm for bandit linear optimization. In The 21 Annual Conference on Learning Theory, pages 263 274, 2008.
[2] Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Interior-point methods for full- information and bandit online learning. IEEE Transactions on Information Theory, 58(7): 4164-4175, 2012.
[3] Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with new kind of smoothness. In Advances in Neural Information Processing Systems, volume 28, pages 2197- 2205, 2015.
[4] Noga Alon, Nicolò Cesa- Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feed- back graphs: Beyond bandits. In Proceedings of The 28th Conference Learning Theory, volume 40, pages 23-33 23-35,22 2015.
[5] Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory, volume 7, pages 1-122, 2009.
[6] Peter Auer. Using confidence bounds for exploitation-exxlorratoon trade-offs. Journal of Ma- chine Learning Research, 3994v2:397-422, 2002.
[7] Peter Auer and Chao- Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In 29th Annual Conference Learning Theory, volume 49, pages 116-120, 2016.
[8] Peter Auer, Nicoló Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1))48-77, 2002.
[9] Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Minimax regret of finite aatial-monitoring games stochastic environments. Proceedings of the 24th Annual Conference on Learning Theory, volume 19, pages 154, 2011.
[10] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 42.1-42.233 2012.
[11] Nicolò Cesa-Bianchi. Gábor Lugosi, and Gilles Stoltz. Regret minimization under partial mon- itoring. Mathematics of Operations Research, 31(3):562-580 2006.
[12] Sougata Chaudhuri and Ambuj Tewari. Online learning to rank with top-k feedback. Journal of Machine Learning Research, 18(103):1-50 2017.
[13] Houshuang Chen, zengfeng Huang, Shuai Li, and Chihao Zhang. Understanding bandits with graph feedback. In Advances in Neural Information Processing Systems, volume 34, pages 24659-24669, 2021.
[14] Varsha Dani, Thomas P. Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In The 21st Annual Conference Learning Theory, volume 2, pages 355- 366, 2008
[15] Chris Dann, Chen-Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. Proceedings of Thirty Sixth Conference on Learning Theory, volume 195, pages 5503-5570, 2023.

---

[16] Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the leader you can, Hedge if you must. Journal of Machine Learning Research, 15(37):1281-1316, 2014.
[17] Ofer Dekel, Ambuj Tewari, and Raman Arora. Online bandit learning against an adaptive adversary: from regret to policy regret. Proceedings of the 29th International Conference on Machine Learning, pages 1747-1754, 2012.
[18] Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T2/3 regret. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pages 459-467, 2014.
[19] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12661)22121-2159, 201
[20] Liad Erez and Tomer Koren. Towards best-of-all-wordde online learning with feedback graphs In Advances in Neural Information Processing Systems, volume 34, pages 285 18511-220 1-28521, 2021.
[21] Yoav Freund and Robert E. Schapire. A decision-theoreeie generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-133) 1997.
[22] Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In Proceedings of The 27th Conference on Learning Theory, volume 35, pages 176-196, 2014.
[23] Pratik Gajane and Tanguy Urvoy. Utility-based dueling bandits partial monitoring game. arXiv preprint arxiv: 150.00257 2015.
[24] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 2552-2583, 2021.
[25] Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both- worlds algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 28631 1 28643, 2022.
[26] Shinji Ito, Taira Tsuchiya, and Junya Honda. Adaptive learning rate for follow-th-rregulaiieed leader: Competitive analysis and best-of-both bothoooowoddds. In Proceedings of Thirty Seventh Con- ference on Learning Theory, volume 247, pages 2522-2563, 2024.
[27] Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: Stochastic and adversarial episodic MDPs with unknown transition. In Advances in Neural Information Pro- cessing Systems, volume 34, pages 20491-20502, 2021.
[28] Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-both-wee both-worlds guarantees for muulti-armer bandits: FTRL with general regularizers and multiple optimal arms. In Advances in Neural Information Processing Systems, volume 36, pages 30918-30978, 2023.
[29] Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on re- gret for online posted-price auctions. In the 44th Annual IEEE Symposium Foundations of Computer Science, pages 595.605, 2003.
[30] Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in finite stochastic partial monitoring. In Advances in Neural Information Processing Systems, volume 28, pages 1792-1800, 2015.
[31] Fang Kong, Yichi Zhou, and Shuai Li. Simultancously learning stochastic and adversarial bandits with general graph feedback. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 11473-11482, 2022.
[32] Joon Kwon and Vianney Perchet. Gains and losses are fundamentally different in regret mini- mization: The sparse case. Journal of Machine Learning Research, 17(227): 2016.
[33] L.. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in
Applied Mathematics, 6(1):4-22, 1985.
12

---

[34] Tor Lattimore and Csaba Szepesvári. Cleaning up the neighborhood: A full classification for adversarial partial monitoring. Proceedings of the 30th International Conference on Algo- rithmic Learning Theory, volume 98, pages 529-556, 2019.
[35] Tor Lattimore and Csaba Szepesvári. An information -htiooettcc approach to minimax regret in partial monitoring. In the 32nd Annual Conference on Learning Theory, volume 99, pages
21 2111-2139, 2019.
[36] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[37] Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 2020.
[38] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-26)) 1994.
[39] Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 1286-1 1384,4 2015.
[40] Haipeng Luo, Chen-Yu Wei, and Kai Zheng. Efficient online portfolio with logarithmic regret. In Advances in Neural Information Processing Systems, volume 31, pages 8235-8245, 2018.
[41] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to ad- versarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 11 112-122 2018.
[42] Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. In Advances in Neural Information Processing Systems, volume 24, pages
201 1.
[43] Saeed Masoudian and Yevgeny Seldin. Improved analysis of the Tsallis-IN algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corrup- tions. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 3330-3350, 2021.
[44] H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In The 23rd Conference on Learning Theory, pages 244-256, 2010.
[45] Francesco Orabona. 192.13191,.13213, 2019.
A modern introduction to online learning.
arXiv preprint
[46] Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Best of both worlds model selection.
In Advances in Neural Information Processing Systems, volume 35, pages 1883-1895, 2022.
[47] Antonio Piccolboni and Christian Schindelhauer. Discrete prediction games with arbitrary feed- back and loss (extended abstract). In Computational Learning Theory, pages 208-22222202 223, 2001.
[48] Chloé Rouyer and Yevgeny Seldin. Tsallis-NN for decoupled exploration and exploitation in multi-armed bandits. In Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 3227-3249, 2020.
[49] Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Biannee and Yevgeny Seldin. A oparimptimal best-of-both-worrld algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 35035-35048, 2022.
[50] Aldo Rustichini. Minimizing regret: The general case. Games and Economic Behavior, 29(1):
224-243, 1999.
[51] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In Proceed- ings the 38th International Conference on Machine Learning, volume 133, pages 9235-9244 2021.
[52] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and ad- versarial bandits. In Proceedings of the 31 International Conference on Machine Learning. volume 32, pages 1287-1295, 2014.
13

---

[53] Yevgeny Seldin, Peter Bartlett, Koby Crammer, and Yasin Abbasi-Yadkori Prediction with limited advice and multiarmed bandits with paid observations. Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 280-287, 2014.
[54] Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-both-worfe algorithms for partial moni- toring. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, pages 1415- 2023.
[55] Taira Tsuchiya, Shinji Ito, and Junya Honda. caability-penally-adee followthh-reeullaiizee leader:
Sparsity, game-dependency, and best-of-both-worldd. In Advances in Neural Informa- lion Processing Systems, volume 36, pages 47406-47437, 2023.
[56] Taira Tsuchiya, Shinji Ito, and Junya Honda. Exploration by optimization with hybrid regu- larizers: Logarithmic regret with adversarial robustness in partial monitoring. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 48768 48790, 2024.
[57] Vladimir Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop Computational Learning Theory, pages 371-383, 1990.
[58] Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. Proceed- ings of the 31st Conference On Learning Theory, volume 75, pages 1263-1291, 2018.
[59] Julian Zimmert and Tor Lattimore. Connections between mirror descent, Thompson Sampling and the information ratio. In Advances in Neural Information Processing Systems, pages 11973- 11982. 2019.
[60] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial ban- dits. In Proceedingy of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89, pages 467-475 2019.
[61] Julian Zimmert and Yevgeny Seldin. Tsallis-NNF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-499 2021.
[62] Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. Beating stochastic and adversarial semi- bandits optimally and simultaneously. Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 7683-7692, 2019.
[63] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In the Twentieth International Conference on Machine Learning, pages 928-935, 2003.
14

---

A Additional related work
algorithms The study of BOBW algorithms was initiated by Bubeck and Slivkins [10], who focused on multi-armed bandits. The motivation arises from the difficulty of determining in advance whether the underlying environment is stochastic or adversarial in worldworld problems. Since then, BOBW algorithms have been extensively studied [7, 16, 22, 40, 46, 52], and recently, FTRL is the common approach for developing BOBW algorithmss [24, 28, 60, 62]. One reason by appropriately designing the learning rate and regularizer of FTRL, we can prove a BOBW guarantee for various problem settings. Another reason is that FTRL-based approaches not only perform well in both stochastic and adversarial regimes but also achieve favorable regret bounds in the adversarial regime with seff-bounding constraint, intermediate settings including stochastically constrained adversarial regime [58] and stochastic regime with adversarial corruptions [41]. This intermediate regime is particularly useful, considering that real-world problems often lie between purely stochastic and purely adversarial regimes.
This study is closely related to FTRL with the Tsallis entropy regularization. Tsallis entropy in online learning was introduced in [3. 5]. and its significance for BOBW algorithms was established in [61]. In the multi-armed bandit problem. using the exponent of Tsallis entropy a = 1/2 provides optimal upper bounds, up to logarithmic factors, in both stochastic and adversarial regimes [61]. However, in the graph bandits, where the dependence on & is critical or in decoupled settings, optimal upper bounds can be achieved with a F 1/2 [26, 32, 48, 59]. In this work, we demonstrate that using the exponent tofo a 1- 11-17 1/olo k) for the number of actions k results in favorable regret bounds, as shown in Corollaries 9 and 11.
Partial monitoring Partial monitoring [11, 47, 50] is very general online decision fecision-making frame- work and includes a wide range of problems such as multi-armed bandits, (utility-based baliit-bbaed) dueling bandits [23), online ranking [12), and dynamic pricing [29]. The characterization of the minimax regret in partial monitoring has been progressively understood through various studies. It is known that all partial monitoring games can be classified into trivial, easy, hard, and hopeless games, where their minimax regrets are 0, O ((VT), (TT2/3) and ((T). For comprehensive literature, refer [9] and the improved results presented in [34, 35J. The games for which we can achieve a regret bound of O(T2/3) correspond to globally observable games.
There is limited research on BOBW algorithms for partial monitoring with global observability [54, 56). The existing bounds exhibit suboptimal dependencies on ie and T, particularly in the stochastic regime, which comes from the use of the Shannon entropy or the log- log-barrier regularization. By employing Tsallis entropy, our algorithm is the first to achieve ideal dependencies on both k and T'. It remains uncertain whether
upper bound in the stochastic regime is optimal with respect to variables other than T. While there is an asymptotic lower bound for the stochastic regime [30], its coefficient is expressed as complex optimization problem. Investigating this lower bound further is important future work.
Graph bandits The study the graph bandit problem, which is also known online learning with feedback graphs, was initiated by [42]. This problem includes several important problems such as the expert setting, multi-armed bandits, and label-efficient prediction. For example, considering a feedback graph with only self-loops, one can see that this corresponds to the multi-armed bandit problem. One of the most seminal studies on the graph bandit problem is by Alon et al. [4], who elucidated how the structure of the feedback graph influences its minimax regret. They demonstrated that the minimax regret is characterized by the observability of the feedback graph, introducing the notions of weakly observable graphs and strongly observable graphs. Of particular relevance to this study is the minimax regret of (8/22/3 for weakly observable graphs, where ó is the weak dom- ination number and Ô(-) ignores logarithmic factors. Recently, this upper bound was improved to (633) by replacing the weak domination number with the fractional weak domination num- ber 8" [13].
There are several BOBW algorithms for graph bandits [15, 20, 25, 31, 49]. However, only a few of these studies consider the weakly observable setting [15, 31J. The existing results based on FTRL rely on the domination number rather than the weak domination number [31] or exhibit poor dependence on T [25, 31], and the best regret bound of them still exhibited dependence on T of
15

---

T)² [25]. Our algorithm is the first FTRL-based algorithm in the weakly observable setting that achieves an Oloog T') stochastic bound.
B Proofs for SPB-matching learning rate (Section 3)
B.1 Proof of Lemma 4
Proof of Lemma 4. We first consider Rule in (6). The learning rate 3r is lower-bounded as
8//2 2 22/2 B1-1+
2 h4
3/2
2
2
2
(22)
B
h
hg
where the first inequality follows from the definition of 3e in (6) and the second inequality from the fact that (Be) is non-decreasing. We also have
Be z Br
Uc
3/2
Ut
U
(23)
hq
3e
h
h
Using the last two lower bounds on Bt, we can bound F in (5) as
T
F(BIT, FIT, uI.T, (T.)) S
Up
+
(3: - (Te
B
3
T
2t
+ 2 U1
Be
B1
T
T
Ut
4
+
2
2 (2Ex=
Vz,
1/3
==1
Eemr
ur/
3.2G (Z1.T, hL.)) 2G. ,,.r)
(24)
where the second inequality follows from the definition of B, in (6) and the third inequality from (22) and (23). This completes the proof of the first statement in Lemma 4.
We next consider Rule 2 in (6). In this case, we can bound F as follows:
T
F(Bur, Zv.r, uI.T, h < 2
21
+
81
+
31h
+
2
21
11
+ (Br - -B:-1
31
31
B
31
(=2
2
+
11111 +
Σ
2
Z1
2
2t-1 +
ut-1
B1
Br
B
3--1
t=2
2t
21
$ k1
+
(25)
3e
Br
where the equality follows from (6).
We then first consider bounding ETT
V Ze/BB. We can lower-bound 3,122 as
2212 2 82/2 (B-1
2 2--1
83/2
2
/
v /2g-1
=: (B/1)3/2
3/2 (26)
+ hy
V
3r-1
2
2
+2
h
8=2
where we define
2/3
2/3
8
93/2
+2
1
/
33/2
+
1-1
/ /2
S B
(27)
hr
hg+1
2=2
16

---

In the following, we will upper-bound Σt= 1=1 12/B S and and we then define S (t E [T]: 0441 I c² ) and S (T) \ S = (t E (T] 0241 > e² 2. From these definitions, we have
E --= v2/B,". Let 8) for 8 > 0
Σ
max
mmax B1
(28)
1 1/c V B1
rESt
SE
Hence, using the last inequality, we obtain
T
4t
1ES
LESt
2t
1
Zmax
1141
1/c V
31
LES
c Σ
2t
1
mmax
(2E, /zs/ (ts//oat))
2/3
1
1/c
1ES
Zmmax
Gi GI
(29)
21/3
c-1
B1
where the third inequality follows from the definition of 3(0 in (26). We next bound Σ ur/3z. We can lower-bound (3 as
3 2 Be 3 +
14-1 Ri
2 p +
4
B7
+
U1-1
=: (
(30)
B1-1
hrt
h2
where we define
t-1
8000
B7 +
Uz-1
37 +
Us S Br.
(31)
hg
hx+1
8=1
In the following, we will upper-bound Σ 1= uz/B: < ΣE= Ut B,.0 Let us define T
{t E [T]: 8 S cB(0) and T = (T] T = E [T]: 3 (,301) }. From these definitions,
we have
Σ
Ue
Mmax
Umax
<
Umax
(32)
g
3
31
1/c B1
TE
ET
Hence, using the last inequality, we obtain
3
3
LETc
U1
1
Umax
((2)
1/c
31
1ET
1
Umax
<c
+
1 1/c $1
E wa/hoot
1ET
V
=G h2TTT)) +
c 2max
(33)
c- B1
Finally, combining (25) with (29) and (33), we obtain
F(BEr, Pur, war, M - 3.2c Gz (21:1, hoZT+1) + 2c G2 G2(uT: (12:44))))))
+
2
Zmax
+
Umax
+ B1 h1.
(34)
B1
B1
Setting 1.25 completes the proof.
17

---

B.2 Proof of Lemma 5
Before proving Lemma 5, we prepare the following lemma, a variant of [45, Lemma 4.13].
Lemma 12. Let T S [7] (1...., T and (xt))ET be non-negative sequence. Then,
2/3
21
Σ Zt MET
(35)
1/3
EET
ExE(AnT T.)
Proof. Let St
EVELIUT 2g. Then,
Ft
S.
5, dz <
S.
1/3
S:
1/3
3
3
2//3
57-1
(36)
Ex ExE(jnT T.
1/3
S
81-1
2
Summing up the last inequality over T, we obtain
It
52/3
-
2/3
3 2/3
I
(37)
1/3
2
Σ
E> T.
TET
where the last inequality follows from the telescoping argument with the assumption that 2 0.
Proof of Lemma 5.
We upper-bound G1 as follows:
V
2t
Ci(2%r,,aa))
1/3
1/3
/z/h/a
j=1 tE
E v / hha)
J+1
J-1
V
V
1/3
1/3
j=1 TET
Σ ExETAN /2//h.)
j=1 TET
E V
2/3
1+1 Σ 3=1
V2r
J-1
V0j-1
(38)
1/3
2
TET
EEETTnI V².
J=l
1ET,
where the last inequality follows from Lemma 12. This completes the proof of the first statement in Lemma 5. Setting J = 0 and 0g- = 1max in (38) yields that
2/3
G GI h1T) 3
Σ
Zrlimax
(39)
Setting 8, 2- hmax for j E [0) U in (38) also gives
2/3
J+1
GI S
0
Σ
==1
TET,
2/3
2/3
-
zeh1
+
3
VOJ Σ 2
0g
LET,
LETs
2/3
2/3
3
V2
Zalte
+
2
J/2
Zeltmax
2
LET
LET)
2/3
2/3
22
V 20
+
2
J/2
Σ
2
j=1 IET
LETT
(Hölder's inequality)
18

---

2/3
3
2/3 mmax
22
+ 2
112 2-112
72/3
(40)
2
where the second inequality follows from (xr + y) < x2/3 2/3 + 2/2 for x, 2 0. Combining the last inequality and (39) completes the proof of the second statement Lemma
C Proof for best-of-both-worte analysis in general online learning framework (Theorem 7, Section 4)
This section provides the proof of Theorem 7.
Proof. From Assumption (i), the regret is bounded as
T
T (ee - + Σ
Regr S E
78
(41)
[=1
t=1
From the standard FTRL analysis [36, Exercise 12], we obtain
T
Σ 2h cx.)
(6. (6.9- - u+1) -..D((-..). + (Be BI-1)he) + Bh. (42)
Combining the last two inequalities, we obtain
(ft, 2++1) -Be -Be + (3r - Br Be-1)h4 + 2%x) ,3h
Regr < E
E
+ (Br -1--2)14 + 7/ -30--312)h4
3h
(Assumption (ii) in (12))
Bink
+ -3--1)44 + 1/ + Ut
Σ E
+ 3h
(definition of n in (11))
Bink
3r
$
Zt
+
Wt
+ (3: - -31-))
+ ,3
(definition of 7/ and Assumption (ii)
B1
Be
S E( #1.,, MI., -1) ,3h,
(43)
where the last inequality follows from (5). Now, since 3, follows Rule in (6) with he h1-1, Eq. (9) in Theorem 6 gives
F(BLT, "1T. 1)
+
Hehy +
Zmax
Umaa
+ Bih1, (44)
B
1=1
t=1
T
V Vzmazchy
3
F(BLr, Zir, Unr ho.T-1 S inf 221/T
zehe log(=T)
+
Σ uhy log(eT)
Umaxlh
Zmax
Umuax
+ B1h1 (45)
B1
B1
Hence, the adversarial regime, combining (43) and (44) gives
T
2/3
T
Regy S
Σ
Σ
uih
+ S (2maxch)) 1/372//3 + /umaxh + R, (46)
where we recall that K V 2maxx/ B1 Mmaxx 13 + Byhi + Bh. This completes the proof of (13).
19

---

We next consider the adversarial regime with a (A, -eTT)-selfbouudding constraint. aor & 2 combining (43) and (45) gives
1/T,
T wehe log(sT)
3
Regr x E
Σ
2rh4, log(ET))
+
V V2maxhi
Umax
+
e
T Veche
T ughs
VVmaxlty
$
Umaxli
E
Vlog(ET)
+
Σ
log(eT) +
+
+ 16
(47)
where the last inequality follows from Jensen's 's inequality. Now, using the assumption (14) and defin-
ing Q(a*) = E
E[Ei1 2
(ta
}]
E
[0, Tj. we have
2gh4
S VPI P1 E
)taa)
= Q(a)(a"),
(48)
T
T
uhh
S P2
E
(1 (ta*)
= p2 Q(a")
(49)
Since consider the adversarial regime with (A, CT),sss)- (eee)))-sf---ouiiii constraint, the regret is lower-bounded as
T
T
RegT
2
E
A
p)
-2
E
Σ 1=1
A 9)
-
1=1
T
1 min
A
E
Σ [(=1
(1
)ta:)
- C =
2 Amin Q(a")((()))
(50)
2
where the second inequality follows from p (1- + PPP 2 q: /2. Hence, combining (47)
with (48), (49) and (50), we can bound the regret for any X E (0, 1] as follows:
Regr- (1 ReRe ARegr
2/3
Q(a)) (1 (222((a))lggee" A
$ (1 + (PTQ(()) (1+
Vlog(eT)
Amin Q(a))
4
V2maaxh1
2/3
Umnaxh1 K
+1++A
+
8
(1 + 2)3
Pi log(ET))
(1 (1+2)2
P2 log(eT)
v V2maxti
2/3
Umaxh1
+
+ + AC
22
2
min
A
Amin
E
E
P1 log()T))
P2 log(ET)
P1 log(ET)
P2 lolg(ET))
2maxh
2/3
Umaxty
+
+
+ + + AC
A
min
Amin
X2
2 min
Amin
P plog(ETT)
1 plog(ET))
v /2max
2/3
h1
+ XC
(51)
A
X
A
where in the first inequality we used (47) with (48). (49), (50), and Jensen's 's inequality, in the second
inequality we used ax² - br < 4a 4a2/(276² for 2 0.b > 0 and > 0 and ar - bx < a² 22/(4b) for 2 0,b > and x 2 0 and in the third inequality we used A (0, 1). Setting
A
in the last inequality, we obtain
RegT S plog(ET) +
( (PPlog(ETT)
1/3
V /Vemax/a
2/3
Umaxx/1 + R.
2
2 min
min
Finally, when T 2 r 1/2 3 min + C/ Cmis setting
(52)
p3 min
+ Cp/ Amin
20

---

yields
T
Cºp log+
T
1/3
RegT
log+
A
1/4
min + C/Amin
A
1/A min
+ C.CCCmin
min
min
1
2/3
C
+ (2max/1) 12/3
v Umaxtii
+
+
A3
Amin
A3
Amin
min
min
log (T' + (
C
T T'mmin
1/3
log+
A
A
min
min
C.
2/3
+ (zmax + Umaxli)
+
+ K.
(53)
A
Amin
min
which completes the proof.
D Auxiliary lemmas
This section provides auxiliary lemmas useful for proving the BOBW gurantee.
Lemma 13. Let E 1) and i" [k.]. Then, the a-Tsallis entropy Ha is bounded from above as
& Hg(g) = Σ (sf - 4:) = (k: 11 )0
(54)
i=1
for any q E Pk.
Proof. From Jensen's inequality and the fact that x + xº is concave for a E (0, 1),
Σ 1=1
offf 4:) S Σ uff = =( (k- 1) Σ 1 - Lh S (N: -
7: カ- Σ qi
i9/'
if
iff
a
(k - -k-1)110
Σ qi sppi
(k 1) 1)'-a(1 90.
(55)
which completes the proof.
L
Lemma 14 ([26, Lemma 10]). Let E Pk and i E arg maxiele di For E RR,, if lesl s
I-a
min -- for all E [k], it holds that
max (L.g ( D(. S 1-a pEP
4
Σ
2-a l min 97}² 2
(56)
itf
Lemma 15 ([26, Lemmas 11 and 12)). Let T. E TRk and l RR and suppose that g, E Pk are given by
arg arggmin min ( (L.p) B - (H) + 3(-Ha(p))
PEP.
arg min (L (L+ E,p) + 5 (- B()-Ha(p))
(57)
PEP.
for the Tsallis entropy H. and Ha.
0< 3.. Suppose also that
(V2)a-1
(V2)
0-
|lelec I max
g. 0-1 3,
go
3
(58)
2
2
(1-(V2) 3, 1-
(v2)
8-1
0 3' 3 max
q.
(59)
v2
Then, it holds that H (r) < 2H.(g)
21

---

E
Proof for partial monitoring (Theorem 8, Section 5)
This section provides the proof of Theorem 8.
Proof of Theorem 8, It suffices to prove that assumptions Theorem are satisfied. We first vertify Assumptions (i)-(ii) in (12). Let start by checking Assumption (i). From the definition of the loss difference estimator Tt. the regret is bounded as
Regr
E
(CA... Larze)
(pc ca. Leaa)
1=1
(gc caa, Lexd)
+
Vt
qt Lese
k:
T
T
T
$
(ge Car, Lexit
+
=
E
Ita (Lax, - LLux,,) +
1=1
1=1
T
T
T
E
Ysa UTa Ih-) +
Σ
=
E
(at Car Tt)
(60)
1=1
where the incquality holds since C E [0, 1]kxdd This implies that Assumption (i) indeed satisfied.
We next check Assumption (ii) in (12). For any b E [K]
we have
G1) (G(A).o))ble
cg
cg
1-a 8
(min 9r. 1- (61)
Be
B.PrAc
Ben
Br7 41
where the third incquality follows from % 2 u//3 3. in (11) and the last equality follows from the
defintition of in (17). Hence, from Lemma 14 the LHS of Assumption (ii is bounded as
Y1 3,
Eg (et, a: a++)) Be D.D.HH.
B,LE,
9t
g1+1 D(-Ha)(gct1)
E.
4
Σ
Pis
a
Ves
(min 4zi, 3)
2--00
Vel.
B1
it
Σ
Qe
2 a
E,
Uis!
+
2- Ee
EE
22 Weie
(62)
3.(1 - a)
it
Since the variance of Te is bounded from above as
k
G(a,
k k|IG
og
E,
Pro
(63)
Pia
Vt
7t.
a=1
a=1
for any i e [k)], the LHS of Assumption (ii) is further bounded as
4r3
(e a: - q(+1) B,D (gc+1, 9:)l <
Σ
4z
+
<
3r7 - a))
Brtt.
Brr
(64)
which implies that Assumption (ii) in (12) satisfied.
Next, we will prove he+1 S ha of Assumption (ii) in (12). To prove this, we will check the conditions (58) and (59) in Lemma 15. For any [k).
||G||c
||| <
Cg.²
1-a B 1 1-
(V2)
B
<
(65)
PtA. %
ut
8
2 4
where the second inequality follows from Pto 2 kr the third inequality from Yo 2 un Br, and the last inequality from the fact that (1 x)/4 4 < - (V2)²-1 =-1 for E [0, 1). Thus, the condition (58)
is satisfied.
22

---

We next check the condition (59). Recalling qt= = min 1 - 9.s, t. the parameters and uz satisfy
20g
Σ
4ri 2-a
2Vkog 1- v1
U1. U
8eg 1-a
91+
(66)
VT
a
1
ifte
where the inequality follows from qts S 9tx for i + It. The penalty component h4 is lower-bounded as
h4 = Ha())= 1 [
Ch -4) 2
1 - (1(122
4+ 2
- a a
9:
(67)
4a
1=1
where the last inequality in (67) follows from - -11/2)²~ 2 (1 - x) for x S 0, and the first
inequality can be proven as follows: when 4i, 2 1//2, it holds that >x= (g qti) 2 Ci 4ii,
- -1/2)1 and when q., > 1/2, it holds that Gi (1 L. 2 Gi. (1 - (1/2) = =%
E- q:c) 2 - Lu - -12 2 Eiji 0u (1/2)² - 2 (Eizi, 91:) + (1/2)
(1 ),, )a + (1/2)a -1 1= = Li + (1/2) - 12 1 (1 - (1/2)1 1)) Using the bounds on 2t, Ut.
and he in (66) and (67), we have
Bet1 - Br = 1
24
U
4
1 Ut
+
h/-1
B
3/
h4
Be
h4 B
16acg /
1
32acg
1-2a
VBI(1 a333/2
4/x
VBI(1 - a) 465
< a.3gi 1-30
+ 0130l. 1-2a
R-a 2 1 (V2)a-1
s 2 -111-)330 39.
(68)
V2
where the first inequality follows from (66), (67), and the fact that 3, > B1 2 1, the second inequality
from the definition of /3 in (17), the third inequality from min (1
3 00. 2a)} 2 ā - a since
ā == a. and the last inequality from 1 < (1 (V2 for x < 1. Therefore, the
condition (59) is satisfied. Hence, from Lemma 15, we have h1411 = Ha (1++1) S (2 = 2h,, which implies that Assumption (ii) in (12) is satisfied.
Finally, we check the assumption (14) in Theorem 7. We first consider the first inequality in (14). From the definition of 2, and the fact that qu: S 9ri, for a Ie. the stability component 2 bounded as
4
Σ
2-
- --e,, 2-a
2t 1-a a
2-a
4e3
Σ
2-
Σ qti
1 a
2-a
2-a
802
8cg
<
Σ
Iti
Σ $#
qti
1 (1 - -Qta 3-a
(69)
1-a
a
i
where the second inequality holds from the inequality x" + 15" < (a + 4)ah for z, 2 0 and 2 1, and the third inequality from qs S q.f for i & It. From Lemma 13, we also obtain that
h H. (gt) < a (k- 1)1- qea )²
(70)
Hence, combining (69) and (70), we obtain 808
2 < 1 - (1 qta )2-a (k- - 1)a 1)-- - qea )a= 8cg(k - 11)1-a
(1 - qta ))a.) (71)
a(1 a)
=P1
23

---

We next consider the second inequality in (14). We can bound un from above as
1-a
Ut 1 1-a
80g
(min (et, -9t.))
1-a
S
8rg
Σ qti
a
itkle
1-a
8cg
80g (1 qro )1-0
Σ
qui
(72)
1
1
where the second inequality follows from 9t1, 2 qui for all i [k]. Hence, combining the last two inequality and (70),
uehe S 40g (k: 1)1-a
(1 (ta-).
(73)
a(1 - a))
=p2
Hence, the assumption (14) satisfied with above P1 and P2. and thus have completed the proof.
F
Proof for graph bandits (Theorem 10, Section 6)
This section provides the missing detail of Section 6.
F.1 Fractional domination number
Before introducing the fractional domination number, we define the domination number 3 S 8. A dominating set D C V is set of vertices such that V S UkED (i). The domination number O(G) of graph G is the size of the smallest dominating set. From the definition, the domination number 8 can also be written as the optimal value the following optimization problem:
minimize
Σ Z4 subject to
Σ (END))
z 4211jeV
E {0, vie V.
(74)
EV
where E [0, 1} binary variable indicating whether vertex is in the dominating set (z; 1) or not (z; = 0).
Then, one can see that the fractional domination number 8" is defined as the optimal value of the following optimization problem, which the variables (æt)εev are allowed to take values in [0, 1] instead of {0, 1}:
minimize
24 subject to
Σ (EN*
x4
0 VVEEV
(75)
NV
which is the linear program provided in (19). From the definitions, the fractional domination number less than or equal the domination number, 5" < 8. Another advantage using 8* instead of 5 is
that the fractional domination number 5 can be computed in polynomial time, while the computation of the domination number is NP-hard See [13] for more benefits of using the fractional version of the (weak) domination number.
F.2 Proof of Theorem 10
Here, we provide the proof of Theorem 10.
Proof. It suffices to prove that assumptions in Theorem 7 are satisfied. We first vertify Assumptions (i)-(i) (ii) in (12). We start by checking Assumption (i). The regret is bounded as
T
T
T
T
T
Regr = E
l((A.)
Σ
la(a")
= E
Σ
(l, Pr -aa))
=
Σ
(le,
- + Σ
(le,Pr 9r)
t=1
t=1
T
T
T
E
(Ei, ea-)
Σ
(h a: - u)
E
Σ
(Ce ge Ear)
Σ
7t
(76)
t=1
1=1
24

---

where the third equality follows from the definition of %.. This implies that Assumption (i) is indeed satisfied.
We next check Assumption (ii) in (12). Now, recalling the definition of the fractional domination number and the optimal value x² of (19), and in x Σjev Fij. have
" EjeNi(() 2j
Σ
1
(77)
Σiev 24
Eiey
8
JEN
where the inequality follows from the first constraint in (19). Hence, combining this with the defini- tion of Pt = (1 Ve9g + 7/ we can lower-bound Pai as
Ps Σ
Púj 2 7
Σ
Uj
2 7t
for all i E E.V.
(78)
8
(EN
JEN
This lower bound yields that for any iEV
Exi
li
8
8*
a
a
(79)
Be
PeP
Be
4
8
(min
(ui,
gei, 1-a
where the second incquality follows from (78) and the third inequality from m 2 w/BB in (11). Hence, from Lemma 14 we obtain
[
Ex (Ee. 2(+1) ) - Br D- Ho- ((- = -B
90+1 - -D(-u))(a+100))
(3.00
Br"
< E,
Be(1 a))
4
Yes
2- 2-a
+ (min 1 yes, 3)
2-0
NEVI
4
Σ
2-a
E
+ a:.
BB
(80)
(EV)
Then, by using the lower bound of P. in (78), for any E V the variance of the loss estimator Ess is bounded as
E2
8*
E2
Ptj p2
1 No
Σ
ptj
<
(81)
Pl
P
7t
jEV
iEEN)(()
Hence, combining (80) with (81), we obtain
E, K0r. 9++1) - De (2+11.001
B1r(1- aa) a)
48
Σ
Iúi
2-a +
2-a
Bi
2t
<
3c7
2t
(EE
(82)
which implies that Assumption (ii) in (12) is satisfied.
Next, we will prove het1 S ht of Assumption (ii) in (12). To prove this, we will check the conditions (58) and (59) Lemma 15. For any i V.
Pasl
<
1
8+
8
1 1
3 1 1- (V2)
a-1
3
(83)
Pu
7
Up
8
2
n
where the second inequality follows from (78), the third inequality from Y w2 3,, and the last inequality from the fact that (1 - x)
(V2)==1 for E [0, 1]. Thus, the condition (58) is
satisfied.
We next check the condition (59). Recalling qt. min (qui 1 1- }. observe that the parameters 2, and in satisfy
45*
Σ
2-a 2-a +
+
<
W 1- 3a
85*
4
1-a
(84)
1-
V1
1
(iEV(())
25

---

where the last inequality follows from qes S 9t for i o Ig. We can also bound h, as
h = Ha(
1 a
Σ Ch
qn)
1 (1/2) 1-o
Pt
1 - a
9:.
(85)
a
4a
which can be proven in the same manner in (67). Hence, using the upper bounds on 24, ue and h4 in (84) and (85), we have
2
Ut
24
4 h4
1
B4t - BB =
+
h4-1
B1
31
11g
B1
Be
1 VBI(1 0/3322
16av 1:6*
92x
1- 2
32a8*
46
1-20
V ax)
< 0,30ix 1- 3
+ 1,30/x 1-2a
s 2(1 3 2 1 (V2)a-1
Butt
(86)
V/2
where the first inequality follows from (84), (85), and 3r 2 B1 2 1, the second incquality from the definition of 3. the third inequality from min aa, 1 2ax} 2 ā - a since ā a, and the last inequality from 1 < (1 (V2)==1)/ 1/ /2 for x S 1. Thus the condition (59) is satisfied. Therefore, from Lemma 15, we have h1+1 Ho (1++1) I (H)( = 2h,, which implies that Assumption (iii) in (12) is satisfied.
Finally, we check the assumption (14) in Theorem 7. We first consider the first inequality in (14). From the definition of ze and the fact that qu: S 4si, for + It. we get
40
Σ (EV
2-a + (minf 9ci. 1 - 9ci, }1 2-a
-
2-
40
Σ
2-a +
Σ qui
iEV((L)
it
2-a
2-a
88"
Σ
88*
Σ Uti istta
1 - (1 900
88*
)2-a
(87)
1-a a
1
a
(EEV
where the second inequality holds from the inequality x² + +3 < (xr + y)ah for x, 2 0 and a 2 1, and the third inequality from qu S Qr.. Hence, combining (87) and the upper bound on h2 in (70), we obtain
zehe < 1-a a
88*
(1 Uta ) 2-
1 (k: 01 )co0)
1
88 (k: 1) 1)
q(aa)² (88)
a
a(1 - a))
=pi
We next consider the second inequality in (14). We can bound in from above as
1-a
Ur
85*
(min { Qet, 1
(e.,))
1-a
8
Σ
Isa
1
a
it
1-a
85*
88
qti
1- (1
yra 1
(89)
1 1-c
where the second inequality follows from yei, 2 Gee for all + To. Hence, combining the last inequality with (70).
45* - 1)2- a(1 a)
(1 q(a))
(90)
=P2
26

---

Hence, the assumption (14) is satisfied with above P1 and P2. and thus we have completed the proof.
F.3 Technical challenges to derive best-of-both-wodd bounds depending (fractional) weak domination number
Here, we discuss the technical challenges of making our upper bound in Theorem 10 depend on the weak domination number ò instead of the fracional domination number 5* or the weak fractional domination number 8" < 8.
First, we need to use Tsallis entropy to derive a regret upper bound with a stochastic bound of log T. While we can prove BOBW bound if we use the Shamnon entropy regularizer [25], the bound in the stochastic regime is (logg which is not desirable. Hence, a possible approach to use the log-barrier regularizer the Tsallis entropy. The log-barrier regularizer has a penalty term of (2(k) due to the strength of its regularization, and the regret upper bound in the final adversarial regime ((A2/5), which can much larger than 82/3, Therefore, the most hopeful solution would to use Tsallis entropy with appropriate exponent ~ 1, where note that the Tsallis entropy with a + corresponds to the Shannon entropy.
Recalling the definition of the weak domination number in Section 6, we can see that the weak dom- inating set dominates only vertices without self-loop U {i V: i E (i)] Thus, to achieve a BOBW bound that depends on the weak domination number, vertices with self-loop and those without self-loop should be treated separately by decomposing the stability term as follows:
-441) - 3e P(-HH))(ttt.)
= =Σ =E(Puleu - 99415) Be d( d(q Q.1)) + Σ IEU
(2u(995-(41.)) - 94+1.) - Bg d(9++1.:41.) 9..1)
SEVIU
where d(p, q) the Bregman divergence induced by the real-valued convex function + (x r). However, if we use this approach, we cannot use Lemma 14, which is useful to prove an upper bound with (1 (ta-) (see (14)). This because this lemma exploits the fact that q and are probability vectors. This prevents us from deriving an upper bound with an O(log T') stochastic bound depending on the weak domination number.
G Case study (3): Multi-armed bandits with paid observations
G.1 Problem setting and existing approach
Multi-armed bandits with paid observations, which is first investigated by Seldin et al. [53], is a variant of the multi-armed bandit problem. At each round E [T]. the environment determines loss vector t: A = [k] + [0, 1] and the learner observes cost vector E R Then, the learner selects an action A, [k]] and chooses set of actions S; S [k]. for which we can observe losses. Then the learner suffers a loss of lAA, Eies, Ct and observes set of losses fhe: i S.). The goal of the learner is to minimize the sum of the standard regret and the observation costs given by
T Σ
Reg
cost
= Regr + E
Cti
(91)
SES.
We next provide an existing approach determine the and estimate losses, which are given by Seldin et al. [53]. To determine S,, we prepare vector r, E [0,1]* For this r2, we then sample bu ~ Ber(rw) for each i [k)], and use this to construct the set of actions S, {i [k] by 1). We use the loss estimator defined by
Lu 1 S.),
E.s =
(92)
which is indeed unbiased, Es, [2xs] lei-
In the following, we assume that the cost is the same for each arm at each time, Cu c 2 0. Accordingly, we let ri [0, 10 for each i [k),, where we abuse the notation. Analyzing
27

---

algorithm based on FTRL with SPB-matching learning rate and Tsallis entropy in multi-armed bandits with paid observations
Algorithm 2:
input: action set A = [k), exponent of Tsallis entropy a, (31, /
2 for t = 1,2..... ......d. do
Compute q E Pk by (10) with loss estimator Eg in (92).
Set h4 Ha (ge) and 2t, Me 2 (94).
Compute action selection probability Pt q: without forced exploration.
For ri E 00, 1] in (93), sample by ~ Ber(rr) for each E A and let S: = {i E [K]] by = 13.
Choose A, [k] so that Pr[A;- = pe] Pri-
Observes the set of losses (bu: i E S.} and suffers a loss of les, + EvEs, Czi.
Compute loss estimator &, based on r, and S..
Compute Be+1 by Rule 2 of SPB-mat in (6) with het1 = h4-
10
where each action has a different cost and deriving an upper bound that depends on the cost of each action difficult. This essentially due to the same reason as the problem in graph bandits with self-loops, where the regret upper bound depends on the domination number (see Appendix F.3).
The setting of multi-armed bandits with paid observations is directly reducible the general online learning framework defined in Section 2. However, the parameter r' plays the same role as the forced exploration parameter "/e in partial monitoring and graph bandits, and thus their regret upper bounds have a similar structure. Roughly speaking, we will see in the regret analysis of multi- armed bandits with paid observations with cost 2 0 can be regarded as the general online learning setup with the exploration rate of y = ckrC.
G.2 Algorithm
We use FTRL provided in (10) and (11) for graph bandits and partial monitoring with no forced exploration. that is, Pt = qe. Here we recall that pa E Pp is the action selection probability at round t and ge Pt is the output of FTRL at round We use T E [0, 1] given by
Zt
U1
r1
(93)
Be
B
which plays a role of exploration rate nh We will choose 31 so that r2 S 1/2. Next we specify the parameters in (11). For I, E arg max4e[k] ls and qeu = min 1 9ei, J. we use
64 64 1)kk B1 2
32kVe (1 a
4ck
8 mmaxfc, 1]
Σ ifl
2-a + 2-a 14,
1-a
2
It.
1 1-a
a
a
(94)
8 mm,1 and Amax hi _K-ーa and the above B1 implies
Note that Zmax I-a' Umax
1-a
S 1/2. To follow the analysis in the general online learning framework, we also let r = 2 and 7/6 = ckri S Tt. To make the algorithm clear, we provide the full description of our algorithm in Algorithm 2.
G.3 Regret analysis
We can prove the following.
Theorem 16. In multi-armed bandits with paid observations, for any a (0,1), Algorithm 2 satis- fies the assumptions of Theorem with nt ckri, P1 0
a[1-a] and p2 O max//c.1kk a(I-o)
ch2
where the regret Regr in the statement is repalced with Reg
Note that here we are abusing the statement of Theorem 7 since Theorem 7 is for the general online learning framework given in Section 2 but the multi-armed bandits with paid observation is not a special case of the general online learning framework. Still, if we set the exploration rate " to
28

---

ckT,, then the minimization of the regret with costs, RegT cost in multi armed bandits with paid observation under paid cost e and parameter 7 can be seen as the minimization of the regret Regr in the general online learning framework with exploration rate " ckr₁, A formal proof of the theorem for multi-armed bandits with paid observations corresponding to Theorem 7 follows the same argument and we omit it.
Setting
(/og k) the last theorem gives the following:
Corollary 17. In multi-armed bandits with paid observation with T 2 T, Algorithm 2 with a = 1- 1/olg k) achieves
(((ck)1/32213 (log k)1/3 + Tooo k))
in adversarial regime
of maxte, 1)kk log k log (T4
( max(c, 13k log ki
(Tamin
1/3
RegT
cost cost
log
n²
A
2 min
in adversurial regime with (A, C, -,TT-sell--bbnneee constraint.
(95)
Here, if we use 31 64 max 11k/(1 a),, which satisfies (94), O(maxfc, 1 log k + (log 2))/2) and n¹ K + (((clog k) 1/3 + /max(c,11 log R)) A3
C )2/3).
Amn
This regret upper bound is the first BOBW bounds multi-armed bandits with paid observa- tions. The upper bound in the adversarial regime becomes D(VTllog as + 0, as observed in [53]. The bound the stochastic regime can also match the nearly optimal regret bound of
(log & log (mn) in the expert problem when - O. To formally check this, it suffices to refine the analysis Theorem by analyzing f1 and P2 separately, which unified into = max P2) for simplicity of notation in the proof of Theorem 7.
Proof of Theorem 16. From the observation that the variable plays the same role as the explo- ration parameter Tt, it suffices to prove that assumptions in Theorem 7 are satisfied. We first vertify Assumptions (i) (ii) in (12). We start by checking Assumption (i). The regret with costs is bounded
as
T
T Σ 1=1
Reg
cost
E
lAA
Σ
lea
+
Σ iEO.
E
(Ce ca.)
(re,
t=1
1=1
T
T
(Le. Pt - car)+ + Σ cl)
t=1
= E
Σ Cr.Pe - -ear) kc
(96)
where recall that abusing the notation that ras r, [0, 1]. This implies that Assump- tion (i) is satisfied with = ckri.
We next check Assumption (ii) in (12). For any E [k].
E
Pi Bei
1 Ut
1
<
<
(97)
(min 9.., 1 9ei, 9,,,)) 1-
where the first inequality follows from the definition of E,, the second inequality from r. 2 u//Br. and the last inequality from the definition of uy Note that this is where max/c, 1) in u, is used.
29

---

Hence, from Lemma 14 we obtain
E, (2, ((+1) ( Br D- (...)))((++1..) = Br /
Eg
D ((-ma
B3
91
g++1
S Ee
Be(1 - a)
Σ
9té
22 + (min| 9c.. dct. })
22
22,
4
Σ
2-
E1
+ 9za
"B,
12. (ir.)
(98)
3e(1 - a)
Now, for any E [k]] the variance of the loss estimator Z.s is bounded
C St)
1 -. Tt
R
E.
1 r
(99)
Hence, combining (98) with (99), we obtain
R. (ūe. Qt 9(+1) - Dos (9++1.9)]
$ Bcr(11 - a:)
4
Σ Iei
+ deo
2-x
4ck
Σ HK
9hs 2-a
+
2-a
2t
S
B6 -a) a)
Ben
Bink'
iifle
(100)
where the first equality follows from 7/ ckr. This implies that Assumption (ii) in (12) is satisfied.
Next, we will prove he+1 < h4 of Assumption (ii) (12). To prove this, we will check the conditions (58) and (59) in Lemma 15. For any E [k]]
Be
1 1-
B: Tz+
1 (V2)a=1 3
Rul
(101)
Ft
Tz+
where the second inequality follows from rı 2 u/BB and the last inequality from the fact that (1
/4 < 1 (V2)=-1 for [0, 1]. Thus, the condition (58) satisfied.
We next check the condition (59). Recalling 9t. = min(gi,, 1-9,,,) we observe that the parameters 2, and it satisfy
4ck
2K 1-ja V1 a
8 mmaxfc, 1}
V 2t
Σ iil
lei
2-a + dix
41x
W 1 a
2te
1-a
(102)
where the inequality follows from Uss S qe for + It.
We can also lower bound h4
(1/2)1-a 1-
h H. (a) a
(n) 2 a le
(103)
4a
which be proven by the same manner in (67). Hence, using the upper bounds 2t, 4r and hy (102) and (103), we have
1
21
21
1 4
3
+
h+11
3
Br
h
3
h 3r
16a
/kc
/kc
1- 3a
32a max c, 1} 1-20
9t
Vi - ax) 9t-
VBi 003/3
< 3,,911 10 + a,391 1-20 1-20
1-
-V(22)a-
< 2(1 a) Bq
a-a
<
3
â-a
(104)
V2
30

---

where the first inequality follows from (102), (103). and 8, 2 91 2 1, the second inequality from since ā a, - (1 (v2)= for < 1. Thus the condition (59) is
the definition of B, the third inequality from min 30 1 2xx 2
and the last inequality from satisfied. Therefore, from Lemma 15, have h441 Ho (go+1) 2H. (g:) 2h,, which implies that Assumption (mi in (12) is satisfied.
Finally, check the assumption (14) in Theorem 7. We first consider the first inequality in (14). From the definition of 2 and the fact that qui I 9.1, for i + 4t, get
4ck
Σ if
2-a + (min qui (ni, Oei
qei, 2-
2t
Cx
2-cx
4ck
Σ
2-a +
Σ qci
Ati
-
it
ittl
2-n
2-a
8ck
Σ i
4t
Sck
Σ iplia
Qei
8ck:
(1
9ta )²-a
(105)
where the second inequality holds from the inequality x + 1f (xr + y) for H. y 0 and 1, and the third inequality from qea S "ei," Hence, combining (105) and the upper bound on hr in (70), obtain
Sck:
1 -ks 1)1-a(1 - 2ta )a Sck(( 1)1-a (1 yra )
2hh1 S 1 - a
(1 Uta )2 (106)
a - a))
=p1
We next consider the second inequality in (14). We can upper bound ut
1-a
8 max (c, 1} U1 1 1
mmxx(c) (c, 1}
(min {ee., --i,))))
S -
Σ qti
it
1-a
8 max ma 1-a a
8 Smaxfc. 1}
Σ
qti
(1 qua 1
(107)
1-a a
where the second inequality follows from 9eh. 2 qti for all + Ic. Hence, combining the last inequality with (70),
hg mmxxfc, () 1) 1-a
(1 (bo-)
(108)
a<1 a)
=P2
Hence, the assumption (14) satisfied with above P1 and p2. and thus we have completed the proof.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we claim that we consider adaptive learning rate in online learning with minimax regret of ((T2/3) and develop best-of-both-wee -ooldd algorithms in partial monitoring, graph bandits, and multi-armed bandits with paid obser- vations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provide a comparison of our regret bounds with existing regret bounds in Table 1 and after Corollaries and 11.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
32

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The problem settings are detailed in Sections 1, 2, and 6 and Appendix G and
assumptions fully provided of each proposition. The complete proofs are fully provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: This study is primarily theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
the contribution
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path reproducing verifying the results.
33

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification: This study is primarily theoretical and does not provide open access to the data nor code.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nipp cc/
ssooiiicccyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so Noo is an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips... cc/public/guidee lttggggiidee/deuuueaaeee CCodeSubeeiiicccc
onPolicy)
more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specifyy all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: This study is primarily theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This study is primarily theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
34

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI. if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This study is primarily theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:://eeuuuppeeeeee c htwphhhhhicciieeeeeeee.e.
Answer: [Yes]
Justification: This study is primarily theoretical and does not include contents that can vio- late the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Does the paper discuss both potential positive societal impacts and negative so- cietal impacts of the work performed?
Question:
Answer: [NA]
Justification: This study is primarily theoretical and does not have societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address socictal impact.
35

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the tech- nology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This study is primarily theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model implement- ing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This study is primarily theoretical and does not involve experiments using existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi paperswithcode thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged reach out the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This study is primarily theoretical and does not involve any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicaalle). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This study is primarily theoretical and does not involve crowdsourcing and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contri- bution of the paper involves human subjects, then much detail possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This study is primarily theoretical and does not involve study participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "U7sjvnxzom", "reviewer": "Reviewer_5JDu", "summary": "The paper introduces a novel adaptive learning rate framework for Follow-the-Regularized-Leader (FTRL) tailored to online learning problems characterized by a minimax regret of Θ(T^2/3). This new learning rate, termed Stability-Penalty-Bias (SPB) matching, is designed by balancing stability, penalty, and bias terms within the decomposition of the regret as $\\text{Reg}\\_T \\\\leq \\\\sum\\_{t=1}^T \\\\frac{z\\_t}{\\\\beta\\_t \\\\gamma\\_t} + \\\\beta\\_1 h\\_1 + \\\\sum\\_{t=2}^T (\\\\beta\\_t - \\\\beta\\_{t-1}) h\\_t + \\\\sum\\_{t=1}^T \\\\gamma\\_t$. The paper demonstrates the efficacy of this approach through its application to two significant “hard” online learning problems: partial monitoring and graph bandits, both of which involve indirect feedback. The proposed framework improves upon existing Best-of-Both-Worlds (BOBW) regret bounds, providing simpler yet effective learning rates compared to existing methods and consequently achieving $O(\\\\log T)$ regret in the stochastic regime and $O(T^{2/3})$ in the adversarial regime.", "questions": "- The possibility of adopting similar ideas to other “hard” online learning problems is suggested in the conclusions. However, while the hardness of the problems considered here is mainly related to the observability of the losses, other problems have different characteristics that make them “hard”. For example, the additional hardness of bandits with switching costs is about the loss being adaptive to the previous action of the learner, leading to an extra cost whenever the learner changes the action to play. On the other hand, SPB-matching is related to the presence of the bias term due to having extra exploration to tackle the limited observability. Do the authors believe a variant of SPB-matching could help with these additional problems? Or do they believe these problems would require different novel ideas? Just some vague intuition about this would be appreciated.\n- What are the lower bounds for partial monitoring with global observability? I think being clearer about this would help the reader understand the quality of your regret bound for this problem.\n\nMinor comments/typos:\n- Line 211: “literature” instead of “litarature”\n- Line 221: l.h.s. of the inline equation should be $\\\\sum\\_{c=1}^k \\\\bigl( G(c,\\\\Phi\\_{cx})\\_{a} - G(c,\\\\Phi\\_{cx})\\_{b} \\\\bigr)$\n- Line 695: duplicate “which is not desirable.”\n- Line 700: “Shannon” instead of “Shanon”\n- Lines 701-702: “dominating” instead of “domination”", "limitations": "The authors address potential limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work proposes a novel and interesting unified framework for analyzing regret in online learning problems, inspired by previous work with similar methods of regret decomposition.\nThis enables new BOBW guarantees for the problems of partial monitoring with global observability and graph-feedback bandits with weak observability, significantly improving over previous work.\nThe main results are also introduced with sufficient generality that can help the application and adoption of the proposed SPB-matching technique to other “hard” problems as suggested by the authors.\nAdditionally, the same method is shown to retrieve regret bounds under the more general setting with self-bounding constraints.\n\nThe algorithm is simple to understand for readers who have familiarity with the related work. It is a variant of the well-known follow-the-regularized-leader (FTRL) with additional exploration (given the weak observability of the considered problems), negative Tsallis entropy regularizer (with an appropriate tuning of its parameter $\\\\alpha = 1-1/(\\\\log k)$), and careful tuning of the learning rate via the proposed SPB-matching.\nEven considering the simplicity of the main methodology, the observations and ideas behind it are nontrivial and clever.\nThey required some care to have all the pieces fit together to achieve the final results.\n\nA secondary but nontrivial observation made in this work is that the generality of the Tsallis entropy provides an improvement to the regret bounds compared to using only Shannon entropy and log-barrier.\nA similar phenomenon has already been noted in previous work, but to the best of my knowledge, this is the first time this observation has been made for the problems considered here.\n\nFinally, the presentation slowly introduces the SPB-matching technique and the ideas behind it help understand how the algorithm works for providing the desired guarantees.\nThis might also help in adopting similar techniques in other settings, possibly providing new and improved BOBW results in additional “hard” online learning problems.", "weaknesses": "There is a clear effort by the authors to provide a smooth and clear description of the SPB-matching technique.\nHowever, the large number of parameters made it hard to fully understand how each would exactly influence the analysis of the final regret bound of the algorithm.\nOnly after multiple reads did the full details click and it was clear how all the pieces nicely fit together.\nIn any case, this appears to be caused by the generality of this unified framework and is likely to be unavoidable.\n\nFurthermore, the regret bounds in Corollaries 9 and 11 are not fully clear because of the presence of $\\\\kappa$ and $\\\\kappa’$.\nGiven that all the other parameters have specific values for the two problems considered here, and both $\\\\kappa$ and $\\\\kappa’$ are a function of them, replacing them and thus having an explicit dependence on the actual parameters of the problems could make it easier to understand the regret guarantees in the two corollaries and to compare them with previous related results.\nEven a simple comment on the influence of $\\\\kappa$ and $\\\\kappa’$ to the regret bound for in these two specific cases would help the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable time and thorough review.\nRegarding the minor comments and typos, we will address and correct them in the revised version.\nBelow is our response to the review:\n\n> the regret bounds in Corollaries 9 and 11 are not fully clear because of the presence of $\\kappa$ and $\\kappa'$. Given that all the other parameters have specific values for the two problems considered here, and both $\\kappa$ and $\\kappa'$ are a function of them, replacing them and thus having an explicit dependence on the actual parameters of the problems could make it easier to understand the regret guarantees in the two corollaries and to compare them with previous related results. Even a simple comment on the influence of $\\kappa$ and $\\kappa'$ to the regret bound for in these two specific cases would help the reader.\n\nThank you for your valuable comments.\nFor the partial monitoring problem, when we use $\\beta_1 = 64 c_{\\mathcal{G}}^2 / (1 - \\alpha)$, which satisfies the first inequality in Eq. (17), we have $\\kappa = O(c_{\\mathcal{G}}^2 \\log k + k^{3/2} (\\log k)^{5/2})$ and \n$\\kappa' = \\kappa + O\\left( ( c_{\\mathcal{G}}^{2/3} (\\log k)^{1/3} + \\sqrt{c_{\\mathcal{G}} \\log k} ) ( \\frac{1}{\\Delta_{\\min}^2} + \\frac{C}{\\Delta_{\\min}} )  \\right)$.\nFor the graph bandit problem, when we use $\\beta_1 = 64 \\delta^* / (1 - \\alpha)$, which satisfies the first inequality in Eq. (20), we have $\\kappa = O(\\delta^* \\log k + k^{3/2} (\\log k)^{5/2})$ and \n$\\kappa' = \\kappa + O\\left( ( (\\delta^* \\log k)^{1/3} + \\sqrt{\\delta^* \\log k} ) ( \\frac{1}{\\Delta_{\\min}^2} + \\frac{C}{\\Delta_{\\min}} )  \\right)$.\nIn the revised version, we will make the influence of $\\kappa$ and $\\kappa'$ explicit.\n\n> Do the authors believe a variant of SPB-matching could help with these additional problems? Or do they believe these problems would require different novel ideas? Just some vague intuition about this would be appreciated.\n\nThank you for pointing out this important point. \nWe believe that our approach may not be applicable to all problems with the minimax regret of $\\Theta(T^{2/3})$ (hard problems), and as the reviewer suggests, different novel ideas might be required. \nStill, if a hard problem has a structure similar to hard graph bandits and partial monitoring problems that requires additional exploration, we believe that the best-of-both-worlds bounds can be achieved by SPB-matching.\n\nFor instance, the authors found after the submission that it is possible to achieve best-of-both-worlds bounds in multi-armed bandits with paid observations [53] by SPB-matching. \nIn this setting, the learner can observe the loss of any action by paying a cost, and the goal of the learner is to minimize the sum of the regret and total paid costs for observations.\nThe cost of observations behaves similarly to the bias term in the stability–penalty–bias decomposition, and thus our SPB-matching learning rate can be applied.\nIn particular, we can show that the sum of the regret and paid costs is roughly bounded by \n  $\n    O\\big(\n      (c k \\log k)^{1/3} T^{2/3}\n      +\n      \\sqrt{T \\log k}\n    \\big)\n  $\n  in the adversarial regime and by\n  $\n    O\\big(\n      \\max\\\\{c,1\\\\} k \\log k \\log T / \\Delta_{\\min}^2\n    \\big)\n  $\n  in the stochastic regime for the cost of observation $c$.\n  This is the first best-of-both-worlds bounds for multi-armed bandits with paid observations, and the bound for the adversarial regime is of the same order as [53, Theorem 3],  demonstrating the effectiveness of the SBP framework.\nThe proof is almost the same as in the cases of graph bandits and partial monitoring. The revised version will include this discussion.\n\n> What are the lower bounds for partial monitoring with global observability?\n\nTo the best of our knowledge, beyond the dependency on $T$, little is known about the lower bound for partial monitoring (with global observability). \nIn the adversarial regime, the dependency on $T$ is known to be $\\Omega(T^{2/3})$ [9, 34, 35]. \nHowever, little is understood about the dependencies on the variables $k$, $d$, and $m$, which is also mentioned in Section 37.9 of [36]. \nIn the stochastic regime, an asymptotic distribution-dependent lower bound of $\\Omega(D (\\nu^* )\\log T)$ is known [30], where $D(\\nu^*)$ denotes the optimal value of a certain complex optimization problem. \nHowever, it is not clear how this $D(\\nu^*)$ depends on $k$, $d$, and $m$, and investigating this is important future work. \nIn the revised version, we will discuss that little is known about the dependencies other than $T$ for the lower bound in partial monitoring.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OBUnSFbtdW", "reviewer": "Reviewer_YZuC", "summary": "This paper considers the online problems with a minimax regret of $\\Theta(T^{2/3})$ and proposes a new learning rate tuning based on the FTRL algorithm to tackle these problems. The development of the learning rate is straightforward and simpler compared to previous works. The proposed algorithm is versatile in various applications, and the authors prove that it can achieve improved best-of-both-worlds regret bounds.", "questions": "Could the author respond to the concerns in the 'Weaknesses'?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is technical solid though the discussion for the techniques is easy-to-follow.\n- It proposes a simpler and straightforward tuning strategy, which leads to better best-of-both-world theoretical guarantees in partial monitoring and graph bandit problems.\n- The applications justify their findings.", "weaknesses": "The main technique of designing learning rates so that the stability and bias terms are matched seems to already appear in the cited paper [26], and the development of the method seems to focus on how to solve the additional term introduced by the 'forced exploration' strategy. With a quick glance at the cited paper [26], in Section 5.1, this paper also employs the 'forced exploration' strategy, except that the balance ratio $\\gamma$ is fixed. It would be beneficial to further discuss the difficulties encountered when tackling the 'hard problem'.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable time and helpful comments.\nBelow is our response to your comments.\n\n> With a quick glance at the cited paper [26], in Section 5.1, this paper also employs the 'forced exploration' strategy, except that the balance ratio is fixed. It would be beneficial to further discuss the difficulties encountered when tackling the 'hard problem'.\n\nThe primary difficulty in our paper lies in finding a beneficial form of regret upper bounds that simultaneously depend on both stability and penalty for problems with a minimax regret of $\\Theta(T^{2/3})$. \nFor problems with a minimax regret of $\\Theta(\\sqrt{T})$, it is known that the form of $O\\Big(\\sqrt{\\sum_{t=1}^T z_t h_{t+1} \\log T}\\Big)$ for the stability component $z_t$ and the penalty component $h_t$ allows us to derive best-of-both-worlds bounds [26, 28, 55]. \nHowever, for problems with a minimax regret of $\\Theta(T^{2/3})$, it is non-trivial to determine the form of regret upper bounds that are useful for achieving best-of-both-worlds bounds. \nWe found that the form of $O\\Big( \\big(\\sum_{t=1}^T \\sqrt{z_t h_{t+1} \\log T} \\big)^{1/3} \\Big)$ is beneficial. To our knowledge, this form of regret upper bound is new.\nIn the revised version, we will include a discussion on these points.\n\nRegarding the difference on the exploration rate from Section 4.1 of [26] (we believe Section 5.1 is a typo for Section 4.1), they only consider problems with a minimax regret of $\\Theta(\\sqrt{T})$, and they set the exploration rate $\\gamma_t$ either to $\\gamma_t = 0$ or $\\gamma_t \\simeq z_t / \\beta_t$. \nWhen $\\gamma_t \\simeq z_t / \\beta_t$, the additional regret due to this exploration is of the same order as the stability term, and thus a tuning strategy of the learning rate $\\beta_t$ remains the same.\nIn contrast, in problems with a minimax regret of $\\Theta(T^{2/3})$, due to the nature of handling indirect feedback, forced exploration becomes necessary. As a result, the magnitude of the loss estimator increases, resulting in $\\gamma_t$ appearing in the denominator of the stability term (see Lines 134--140). Hence, if we use $\\gamma_t \\simeq z_t / \\beta_t$, the stability term becomes excessively large. Setting a larger exploration rate, $\\gamma_t \\simeq \\sqrt{z_t / \\beta_t}$, resolves this issue.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OR8bjC8tXC", "reviewer": "Reviewer_TQWF", "summary": "In this work, the authors propose a simple and adaptive learning rate for FTRL, which can achieve the minimax regret of $O(T^{2/3})$ for some hard online learning problems. Specifically, they have applied their algorithm (FTRL with the proposed learning rate) to achieve the best-of-worlds regret bounds for partial monitoring (with global observability) and graph bandits (with weak observability), respectively. For the first problem, compared with the best existing results, this paper achieves an $\\log(T)/\\log(k)$ improvement in the stochastic setting, and an $(\\log(T)+\\log^2(T)/\\log(k))^{1/3}$ improvement in the adversarial setting. But, for the second problem, compared with the best existing results, it seems that this paper can only achieve worse regret bounds (by a factor of $\\delta^\\ast/\\delta$) in the stochastic and adversarial settings.", "questions": "Besides the concerns discussed above, I also have the following two questions.\n1) Can the authors provide a detailed comparison between the proposed algorithm and existing algorithms in works [26, 54]?\n2) It seems that Dann et al. [15] propose a black-box approach to best-of-worlds regret bounds in bandits. Can their approach be utilized to solve the partial monitoring problem?", "limitations": "The authors have provided some discussions on the limitations of this work.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Compared with previous studies, this paper has the following strengths.\n1) A simple and adaptive learning rate is proposed for FTRL with forced exploration, which can achieve the minimax regret for some hard online learning problems, such as partial monitoring (with global observability) and graph bandits (with weak observability).\n2) The authors have improved the best-of-worlds regret bounds for partial monitoring by utilizing the proposed learning rate. Specifically,  compared with the best existing results, this paper achieves an $\\log(T)/\\log(k)$ improvement in the stochastic setting, and an $(\\log(T)+\\log^2(T)/\\log(k))^{1/3}$ improvement in the adversarial setting.", "weaknesses": "However, I have some concerns about this paper.\n1) The proposed learning rate is highly inspired by an existing adaptive learning rate in a recent work [26]. Although the existing one can only be utilized to achieve the minimax regret bound of $O(\\sqrt{T})$ for some relatively easy problems, the only difference for the proposed learning rate is to further trade off a bias term (with the stability term), which does not bring enough challenges.\n2) The motivation for such a learning rate for FTRL is to deal with some hard online learning problems (e.g., partial monitoring and graph bandits) that have been well-studied before. Although this paper has applied their algorithm (FTRL with the proposed learning rate) to achieve the best-of-worlds regret bounds for partial monitoring and graph bandits respectively, it does not bring significant advantages compared with existing results, i.e., only logarithmic improvements for partial monitoring and even worse results for graph bandits.\n3) In Section 3, two update rules are proposed for the simple and adaptive learning rate. However, in Sections 4 and 5, it seems that only the second update rule is utilized. So, it is confusing why the authors propose the first update rule and spend non-ignorable spaces in the main text to introduce the corresponding results.\n4) The writing of this paper needs to be improved. For example, the majority of the literature review is only proposed in the appendix, which indeed reduces the readability of this paper. In addition, in line 273, the authors emphasize that \"Our bound is the first BOBW FTRL-based algorithm with the $O(\\log T)$ bound ...\". Although this is not wrong, it is not much to be particular about, because there already exist other non-FTRL-based algorithms to achieve the  $O(\\log T)$ regret bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your thorough and thoughtful review of our work. Here are our responses to your feedback.\n\n> The proposed learning rate is highly inspired by an existing adaptive learning rate in a recent work [26]. ...  which does not bring enough challenges.\n\nYes, as the reviwer pointed out, the proposed adaptive learning rate is highly inspired by [26]. \nThe primary challenge in our paper lies in finding a beneficial form of regret upper bounds that simultaneously depend on both stability and penalty for problems with a minimax regret of $\\Theta(T^{2/3})$. \nWe found that the form of $O\\Big( \\big(\\sum_{t=1}^T \\sqrt{z_t h_{t+1} \\log T} \\big)^{1/3} \\Big)$ is beneficial. To our knowledge, this form of regret upper bound is new.\nIn the revised version, we will include a discussion on these points.\nDue to the space constraint, please refer to *primary challenge in our paper* in Global Comments for further details.\n\n> ... only logarithmic improvements for partial monitoring and even worse results for graph bandits.\n\nand \n\n> ... the authors emphasize that \"Our bound is the first BOBW FTRL-based algorithm with the $O(\\log T)$ bound ...\". it is not much to be particular about, ... \n\n\n**Logarithmic improvement**\n\nFirst, logarithmic improvement is important. Historically, significant efforts have been dedicated to achieving an $O(\\sqrt{kT})$ regret upper bound without the logarithmic term in multi-armed bandits [3,5]. Attempts to improve this logarithmic term have subsequently led to the development of the notable best-of-both-worlds algorithm in multi-armed bandits [61]. Furthermore, beyond multi-armed bandits, there are numerous efforts aimed at improving the logarithmic factor to enhance performance, for example, (Kwon and Perchet 2016; Zimmert and Lattimore 2019; Eldowa et al. 2023). Based on these points, we can see that the improvement of the logarithmic factor is important.\n\nReferences\n- Kwon and Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case, JMLR 2016.\n- Zimmert and Lattimore. Connections between mirror descent, Thompson sampling and the information ratio, NeurIPS 2019.\n- Eldowa et al. On the Minimax Regret for Online Learning with Feedback Graphs, NeurIPS 2023.\n\n\n\n**Comparison with graph bandits result in Dann et al. [15]**\n\nAs pointed out, the regret upper bound for our graph bandits indeed deteriorates compared to the bound of Dann et al. [15] (this difference arises because the (fractional) weak domination number in Dann et al. becomes the fractional domination number in our bound, and note that this change only worsens the bound when the feedback graph has a self-loop).\n\nHowever, the approach of Dann et al. [15] employs a highly complex, multi-stage reduction approach. Moreover, it has the disadvantage of discarding past observations, similar to the doubling-trick.\nWe have demonstrated that the framework of Follow-The-Regularized-Leader alone can achieve an upper bound similar to that accomplished by this highly complex approach, which is a significant theoretical advancement.\n\n**Generality to other problem settings**\nUsing our SPB-matching, we believe that best-of-both-worlds algorithms can be developed for a wide range of problems with a minimax regret of $\\Theta(T^{2/3})$.\nFor instance, the authors found after the submission that it is possible to achieve best-of-both-worlds bounds in multi-armed bandits with paid observations [53] by SPB-matching. \nDue to the space constraint, please refer to *Generality to Other Problem Settings* in Global Comments for further details.\n\n\n> ... two update rules are proposed for the simple and adaptive learning rate. However, in Sections 4 and 5, it seems that only the second update rule is utilized. So, it is confusing ...\n\nThank you for your suggestion.\nRule 1 was included for theoretical interest, and as the reviewer pointed out, it is not used in Sections 4 and 5.\nIn the revised version, we will emphasize that only Rule 2 is used in Sections 4 and 5.\n\n> ... the majority of the literature review is only proposed in the appendix, ... \n\nDue to page constraints, much of the literature review had to be included in the appendix. In the revised version, we will aim to include as much of the literature review as possible in the main text.\n\nBelow, we provide replies to the questions.\n\n> It seems that Dann et al. [15] propose a black-box approach to best-of-worlds regret bounds in bandits. Can their approach be utilized to solve the partial monitoring problem?\n\nThank you for your question. By employing their black-box reduction approach, it seems possible to achieve an upper bound of the same order as our upper bound in globally observable partial monitoring.\nApologies for not realizing this at the time of submission. This is because Dann et al.'s method cannot be used in partial monitoring games with minimax regret of $\\sqrt{T}$ unless the loss of the selected action is observed [56].\nNevertheless, as previously mentioned, the approach by Dann et al. [15] is a complicated approach involving multi-stage reductions and has the drawback of discarding past observations, similar to the doubling-trick.\nHence, demonstrating that using the FTRL framework alone can achieve the same upper bound is a significant theoretical advancement.\nIn the revised version, we will include the regret upper bound obtained by Dann et al. in Table 1 and describe the differences between their method and the advantages of using FTRL directly.\n\nDue to space constraints, we will respond to the items that are considered to have a relatively small impact on the evaluation in the following Comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "suX5eJNj7Y", "reviewer": "Reviewer_7rt1", "summary": "The paper aims to develop a new adaptive learning rate framework for the Follow-the-Regularized-Leader (FTRL) algorithm that addresses online learning problems with a minimax regret of $\\Theta(T^{2/3})$. \n\nIt specifically targets problems with indirect feedback, such as partial monitoring and graph bandits, and demonstrates the efficacy of the proposed framework in improving Best-of-Both-Worlds (BOBW) regret upper bounds.", "questions": "1. **Extension to High-dimensional Sparse Bandits:** The $\\Theta(T^{2/3})$ regret reminds me of the results in high-dimensional sparse linear bandits [1*]. The regret in [1*] is $\\Theta(s^{1/3}T^{2/3})$ (where $s$ is the level of sparsity), and the algorithm in [1*] also depends on a sort of \"forced exploration.\" Is it possible to apply the framework developed in this paper to this high-dimensional and sparse setting?\n   \n    -  [1*] Hao, Botao, Tor Lattimore, and Mengdi Wang. \"High-dimensional sparse linear bandits.\" Advances in Neural Information Processing Systems 33 (2020): 10753-10763.\n\n2. **Other Upper Bounds:** The introduction of the minimax regret $\\Theta(T^{2/3})$ is somewhat abrupt. It makes me wonder whether in some cases, there is a minimax regret like $\\Theta(T^{a/(a+1)})$ for some parameter $a>0$ and why the case $a=2$ is so special that we should focus on it.\n\n3. **General Lower Bound:** Is there any general lower bound for the regret in Theorem 2? While particular cases may have existing lower bounds, a general tight lower bound is expected given that the paper starts from a general framework and provides a general upper bound.\n   \n\n4. **Clarification on Exploration Rate Requirement:** Could the author explain why $\\gamma_t \\ge u_t/\\beta_t$ (in line 138) is needed? In which lemma or proof is this condition necessary?\n   \n5. **Comparison of SPB-Matching Rules:** Which rule is better in theory or practice: Rule 1 or Rule 2 in (6)?\n   \n6. **High-Level Explanation of Regret Improvement:** Could the author briefly explain why the regret is improved after applying the established framework in Sections 5 and 6? Is there any high-level explanation beyond the technical details?", "limitations": "See the Weaknesses and Questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Innovative Approach:** The SPB-matching learning rate is a novel contribution that simplifies the design of adaptive learning rates for complex online learning problems. It has the potential to be applied to other settings.\n2. **Unified Framework:** It successfully unifies the BOBW guarantee for hard problems, representing a good theoretical advancement. Its application to partial monitoring and graph bandits provides tangible improvements over existing methods.", "weaknesses": "1. **Practical Consideration:** The effectiveness of the SPB-matching framework depends on the proper tuning of parameters, which might limit its practical applicability without further optimization techniques. Furthermore, there are no experiments, as a result of which, it is unclear how the proposed method works in practice, even in the simulation. \n2. **Clarity and Accessibility:**  The paper is difficult to follow due to its technical nature. Some equations and results are presented without sufficient explanation, and the extension to the two case studies introduces many new concepts that are hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to carefully review our paper and for providing many questions. Below are our responses to your review.\n\n> The effectiveness of the SPB-matching framework depends on the proper tuning of parameters, which might limit its practical applicability without further optimization techniques. \n\nThank you for your comment about practical applicability.\nHowever, we may not fully understand the reviewer's intent, so if you have time, we would appreciate it if you could be more specific about what further optimization techniques mean.\n\nIf the further optimization problem refers to the optimization of the fractional domination number in graph bandits as described in Eq. (19), note that this optimization problem can be computed efficiently by solving a linear programming problem once before the game begins [13].\n\nAdditionally, note that the tuning of parameters can be determined based on past observations, without the need to solve any optimization problem other than FTRL. This is standard in many best-of-both-worlds algorithms (e.g., [26,54,62]).\n\n\n> there are no experiments, as a result of which, it is unclear how the proposed method works in practice, even in the simulation.\n\nThank you for your comment. This paper focuses on theoretical aspects, and investigating the numerical performance in simulations or practical scenarios is an important future work.\n\n> ... there is a minimax regret like $\\Theta(T^{a/(a+1)})$ for some parameter $a > 0$ and why the case $a=2$ is so special ...\n\nThank you for pointing out this important point.\nThe case where $a=2$ is special due to the classification theorem in partial monitoring. Partial monitoring is a very general problem that includes a wide range of sequential decision-making problems as special cases. It is known that, depending on the relationship between the loss matrix $\\mathcal{L}$ and the feedback matrix $\\Phi$, the minimax regret can be classified into one of four categories: $0$, $\\Theta(\\sqrt{T})$, $\\Theta(T^{2/3})$, or $\\Omega(T)$ (see line 484). Among these, the classes with non-trivial difficulties and particular importance are the problems with a minimax regret of $\\Theta(\\sqrt{T})$ and $\\Theta(T^{2/3})$. \nThis paper focuses on the problems with a minimax regret of $\\Theta(T^{2/3})$ due to this classification theorem. \nIn the revised version, we will explain why we particularly focus on the $\\Theta(T^{2/3})$ case.\n\n> Is there any general lower bound for the regret in Theorem 2? While particular cases may have existing lower bounds, a general tight lower bound is expected given that the paper starts from a general framework and provides a general upper bound.\n\nUnder the general online learning setup given in Section 2, it is almost impossible to prove a lower bound for Theorem 2. \nThis general online learning setup is extremely general. \nFor instance, it includes partial monitoring as a special case. However, partial monitoring itself is very complex, and even when focusing solely on the adversarial regret, no lower bound that depends on variables other than $T$ is known (see Item 14 of Section 37.9 in Lattimore and Szepesvari's book [36]). \nSince constructing a lower bound within the general online learning framework is far more challenging than considering a lower bound for partial monitoring, it is almost impossible to prove a lower bound for Theorem 2.\n\nStill, the results for graph bandits (Corollary 9) obtained as a special case of Theorem 2 match the lower bound. Additionally, as mentioned in Global Comments, in the setting of multi-armed bandits with paid observations, the upper bound obtained by SPB-matching in the adversarial regime also matches the lower bound. From these observations, we can see that Theorem 2 matches the lower bound in several problem settings.\n\n> Could the author explain why $\\gamma_t \\geq u_t / \\beta_t$ (in line 138) is needed? In which lemma or proof is this condition necessary?\n\nThis condition is used to bound the magnitude of the loss estimator $\\hat{\\ell}_t$. \nFor example, in partial monitoring it is used in Eq. (61), and in graph bandits it is used in Eq. (79). Thanks to this lower bound of $\\gamma_t$, we can apply Lemma 14 to control the stability term of FTRL (The LHS of (56)).\nIn the revised version, we will provide a more detailed explanation in line 138 about why this condition is necessary. \n\nSuch efforts to bound the magnitude of the loss estimator are not unique to this paper but frequently appear in FTRL-related analyses. For instance, in the Exp3 algorithm [8], which is equivalent to FTRL with Shannon entropy, they employ exploration to bound the magnitude of the *gain* vector.\n\n> Could the author briefly explain why the regret is improved after applying the established framework in Sections 5 and 6? Is there any high-level explanation ...?\n\nThe high-level reason for the improvement is that the introduction of SPB-matching allows us to use the Tsallis entropy regularizer with an appropriate exponent $\\alpha$. Such improvements have been known in various contexts, such as multi-armed bandits [3,5], sparse bandits (Kwon and Perchet, 2016), and (strongly observable) graph bandits (Zimmert and Lattimore, 2019 and [26]). \nTo achieve best-of-both-worlds using Tsallis entropy, we need to derive a regret upper bound that depends simultaneously on stability and penalty components [26,28,55]. \nOur paper makes this possible even for problems with a minimax regret of $\\Theta(T^{2/3})$.\n\n- Kwon and Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case, JMLR 2016.\n- Zimmert and Lattimore. Connections between mirror descent, Thompson sampling and the information ratio, NeurIPS 2019.\n\nDue to space constraints, we will respond to the items that are considered to have a relatively small impact on the evaluation in the following Comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TlA0wTrHyV", "reviewer": "Reviewer_gjM7", "summary": "This paper provides a new adaptative learning rate framework for hard problems, called Stability-Penalty-Bias matching learning rate (SPB-matching). Using this SPB-matching learning rate, the paper proposes a Best-of-both-worlds (BOBW) algorithm framework for hard online learning problems. It not only achieves simultaneous optimality in the stochastic and adversarial regimes but also achieves the MS-type bound in the adversarial regime with a self-bounding constraint. The paper further shows the utility of their frameworks by studying two hard problems: partial monitoring and graph bandits.", "questions": "- Can the authors provide more explanations on the terms $z_t$, $h_t$, and $u_t$?\n- On page 5, line 146, the paper assumes access to $\\hat{h}_t$, which upper bounds $h_t$. Why is this always the case in reality?\n- Why does Theorem 7 not depend on $p_0$?\n- Why are $z_t$ and $u_t$ chosen as they are in the two examples? What is the practical meaning behind this choice? How should $z_t$ and $u_t$ be decided for other examples?\n- Typo: In Lemma 5, line 163, it should be $J \\in \\mathbb{N}$ instead of $j \\in \\mathbb{N}$.", "limitations": "See weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- **Clear structure**: The paper is well-organized, starting with the establishment of the framework for the learning rate, followed by the introduction of an algorithmic framework based on this learning rate, and finally exploring two applications of their frameworks.\n- **Relatively comprehensive study**: The paper considers both the stochastic and adversarial regimes, as well as an intermediate regime termed the adversarial regime with a self-bounding constraint. It provides algorithms and theoretical guarantees, along with specific parameter choices in Algorithm 1 for two particular problems.", "weaknesses": "- **Need more background introduction**: The authors should consider including an optimization problem aligned with (1) to better illustrate the hard problems. Additionally, more explanation is needed for the terms $z_t, h_t, u_t$ in the introduction or preliminaries sections to enhance understanding.\n- **Strong assumptions**: Although the assumptions in Theorem 7 are checked for two specific problems, they are quite strong and may not hold for many hard problems. The authors should add more discussion about these assumptions, explaining the meaning of each assumption and identifying scenarios in which these assumptions hold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your valuable time and detailed review.\nBelow are our responses to the review.\n\n> The authors should consider including an optimization problem aligned with (1) to better illustrate the hard problems.\n\nThank you for the comment regarding optimization problems.\nBut, we may not understand the reviewer's intent, so if you have time, we would appreciate it if you could be more specific about what optimization problems should be included.\n\n> Additionally, more explanation is needed for the terms $z_t, h_t, u_t$ in the introduction or preliminaries sections to enhance understanding.\n\nThank you for your suggestion. \nWe will add an intuitive explanation of $z_t$ and $h_t$ in the introduction, along with an example in the expert setting. \nAs for $u_t$, it is a parameter that depends on the problem setting, and we provided examples in the sections on partial monitoring and graph bandits in the main text.\n\n\n> Although the assumptions in Theorem 7 are checked for two specific problems, they are quite strong and may not hold for many hard problems. The authors should add more discussion about these assumptions, explaining the meaning of each assumption and identifying scenarios in which these assumptions hold.\n\nThank you for your comment. From a high-level perspective, these assumptions hold even for partial monitoring, which includes many sequential decision-making problems as special cases, as confirmed in Section 5. In this sense, we do not consider them to be strong assumptions. \n\nBelow, we provide a detailed explanation of each assumption:\nAssumptions (i) and (ii) naturally arise in the analysis of FTRL. In particular,\nAssumption (i): This is very standard because this is satisfied if we use an unbiased estimator $\\hat{\\ell}$. For example, it can be found in Chapter 11 of Lattimore and Szepesvari's book [36].\nAssumption (ii): This is an upper bound on the stability term of FTRL, which can be controlled if the magnitude of the loss estimator is bounded favorably, and it is standard assumption in the analysis of bandit algorithms. For example, it can be found in Chapter 29 of Lattimore and Szepesvari's book [36].\nAssumption (iii): This can be satisfied by ensuring the stability of the output of FTRL and has been investigated in various settings, for example, [55,26,28] and (Bubeck et al. 2018). \nFor these reasons, Assumptions (i), (ii), and (iii) are considered relatively mild.\nThe second condition in Eq. (14) has been used in existing research on best-of-both-worlds [26,28]. The first condition in Eq. (14) is new but can be seen as a natural extension of the second condition in Eq. (14) to problems with the minimax regret of $\\Theta(T^{2/3})$.\n\n- Bubeck et al. Sparsity, variance and curvature in multiarmed bandits. ALT 2018.\n\n> On page 5, line 146, the paper assumes access to $\\hat{h}_t$, which upper bounds $h_t$. Why is this always the case in reality?\n\nThank you for your valuable comment to improve the paper. \nFrom Assumption (iii) we have $h_t \\leq c h_{t-1}$ for some constant $c$.\nHence if we set $\\hat{h}\\_t \\leftarrow c h_{t-1}$, we have $h_t \\leq \\hat{h}\\_t$.\nNote that $h\\_{t-1}$ can be calculated from the information available at the end of round $t-1$, so it can be used when determining $\\beta_t$.\nIn the revised version, we will include this discussion.\n\n\n> Why does Theorem 7 not depend on $p_0$?\n\nThe parameter $p_0$ is a parameter that should be appropriately determined according to the problem setting. \nWe design $p_0$ in Algorithm 1 to satisfy Assumption (ii). For example, in partial monitoring, we set $p_0 = 1/k$, and in graph bandits, we set $p_0 = u$ (see Line 265).\nTo improve the current text, we will revise the statement in Theorem 7 to, \"If Algorithm 1 satisfies Assumptions (i)--(iii), then its regret is bounded as ...\".\n\n> Why are $z_t$ and $u_t$ chosen as they are in the two examples? What is the practical meaning behind this choice? How should $z_t$ and $u_t$ be decided for other examples?\n\nThe values of $z_t$ and $u_t$ are determined by the problem setting and the regularizer. \nIn general, $u_t$ is chosen to satisfy the condition for stability (the assumption of Lemma 14 in our paper). Controlling the magnitude of the loss estimator by adding appropriate exploration to manage the stability term is common in the literature of FTRL in bandit problems (e.g., [8,26,54] and [36, Chapter 27]).\n\nRegarding $z_t$, it is difficult to provide a general determination strategy within the limited space, as it varies depending on the form of the adaptive bounds that the algorithm designer aims to achieve. However, in the context of best-of-both-worlds bounds, it is common for $z_t$ to be determined based on the output of FTRL, $q_t$, to satisfy conditions similar to Eq. (14) in Theorem 2 [61,62,55,26,28].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you very much for your valuable time and thorough, insightful reviews. 
While we have replied directly to each reviewer, there are some important points that we could not fully explain due to space constraints.
Therefore, we are addressing these points as global comments here. Please feel free to let us know if you have any further questions.

**Primary challenge in our paper**

The primary challenge in our paper lies in finding a beneficial form of regret upper bounds that simultaneously depend on both stability and penalty for problems with a minimax regret of $\Theta(T^{2/3})$. 
For problems with a minimax regret of $\Theta(\sqrt{T})$, it is known that the form of $O\Big(\sqrt{\sum_{t=1}^T z_t h_{t+1} \log T}\Big)$ for the stability component $z_t$ and the penalty component $h_t$ allows us to derive best-of-both-worlds bounds [26, 28, 55]. 
However, for problems with a minimax regret of $\Theta(T^{2/3})$, it is non-trivial to determine the form of regret upper bounds that are useful for achieving best-of-both-worlds bounds. 
We found that the form of $O\Big( \big(\sum_{t=1}^T \sqrt{z_t h_{t+1} \log T} \big)^{1/3} \Big)$ is beneficial. To our knowledge, this form of regret upper bound is new.
In the revised version, we will include a discussion on these points.

**Generality to other problem settings**

Using our SPB-matching, we believe that best-of-both-worlds algorithms can be developed for a wide range of problems with a minimax regret of $\Theta(T^{2/3})$.
For instance, the authors found after the submission that it is possible to achieve best-of-both-worlds bounds in multi-armed bandits with paid observations [53] by SPB-matching. 
In this setting, the learner can observe the loss of any action by paying a cost, and the goal of the learner is to minimize the sum of the regret and total paid costs for observations.
The cost of observations behaves similarly to the bias term in the stability–penalty–bias decomposition, and thus our SPB-matching learning rate can be applied.
In particular, we can show that the sum of the regret and paid costs is roughly bounded by 
  $
    O\big(
      (c k \log k)^{1/3} T^{2/3}
      +
      \sqrt{T \log k}
    \big)
  $
  in the adversarial regime and by
  $
    O\big(
      \max\\{c,1\\} k \log k \log T / \Delta_{\min}^2
    \big)
  $
  in the stochastic regime for the cost of observation $c$.
  This is the first best-of-both-worlds bounds for multi-armed bandits with paid observations, and the bound for the adversarial regime is of the same order as [53, Theorem 3],  demonstrating the effectiveness of SBP-matching.
The proof is almost the same as in the cases of graph bandits and partial monitoring. The revised version will include this discussion.

Meta-review: Reviewers expressed mostly positive opinions on the novelty and significance of this work. Mild doubts about the level of contribution not reaching the bar of NeurIPS were discussed but were eventually dismissed. I recommend acceptance (poster) with the caveat that the authors commit to addressing the reviewers' comments in the revised version.
Decision: Accept (poster)