Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds
Authors: Taira Tsuchiya
Shinji Ito
Junya Honda
Venue: NeurIPS 2023 poster (2023)
Keywords: follow-the-regularized-leader
adaptive learning rate
multi-armed bandits
partial monitoring
data-dependent bound
sparsity
game-dependency
best-of-both-worlds
TL;DR: This study establishes a generic learning rate for FTRL, yielding a regret bound dependent stability and penalty. It enables us to handle sparsity, game-dependency, and best-of-both-worlds in multi-armed bandits and partial monitoring.

Abstract: Adaptivity to the difficulties of a problem is a key property in sequential decision-making problems to broaden the applicability of algorithms. Follow-the-regularized-leader (FTRL) has recently emerged as one of the most promising approaches for obtaining various types of adaptivity in bandit problems. Aiming to further generalize this adaptivity, we develop a generic adaptive learning rate, called stability-penalty-adaptive (SPA) learning rate for FTRL. This learning rate yields a regret bound jointly depending on stability and penalty of the algorithm, into which the regret of FTRL is typically decomposed. With this result, we establish several algorithms with three types of adaptivity: sparsity, game-dependency, and best-of-both-worlds (BOBW). Despite the fact that sparsity appears frequently in real problems, existing sparse multi-armed bandit algorithms with $k$-arms assume that the sparsity level $s \leq k$ is known in advance, which is often not the case in real-world scenarios. To address this issue, we first establish $s$-agnostic algorithms with regret bounds of $\tilde{O}(\sqrt{sT})$ in the adversarial regime for $T$ rounds, which matches the existing lower bound up to a logarithmic factor. Meanwhile, BOBW algorithms aim to achieve a near-optimal regret in both the stochastic and adversarial regimes. Leveraging the SPA learning rate and the technique for $s$-agnostic algorithms combined with a new analysis to bound the variation in FTRL output in response to changes in a regularizer, we establish the first BOBW algorithm with a sparsity-dependent bound. Additionally, we explore partial monitoring and demonstrate that the proposed SPA learning rate framework allows us to achieve a game-dependent bound and the BOBW simultaneously.

Stabllity-eenall--ddaiiie follow-the-rguuariieellledd Sparsity, game-dependency, and best-of-both-worlds
Taira Tsuchiya"
Shinji Ito NEC Corporation/ RIKEN
The University of Tokyo tsuchiya@mist. i. u-tokyo ac. jp.jp
i-shinj1@hec.com
Junya Honda Kyoto University / RIKEN
honda@i kcoto-u.ac..
Abstract
Adaptivity to the difficulties of problem is key property in sequential berision-making problems to broaden the applicability of algorithms. Follow- the-regularized-leadde (FTRL) has recently emerged as of the most promising approaches for obtaining various types of adaptivity in bandit problems. Aiming to further generalize this adaptivity, we develop generic adaptive learning rate, called stability-penalle aadapativ (SPA) learning rate for FTRL. This learning rate yields regret bound jointly depending on stability and penalty of the algorithm, into which the regret of FTRL is typically decomposed. With this result, we establish several algorithms with three types of adaptivity: sparsity, game- game-dependency, and ofst-of-bothh worlds (BOBW). Despite the fact that sparsity appears frequently in real problems, existing sparse multi-an armed bandit algorithms with k-arms assume that the sparsity level < k is known in advance, which is often not the case in real-world scenarios. To address this issue, we first establish s-agnostic algorithms
with regret bounds of Ö(V+T) in the adversarial regime for rounds, which matches the existing lower bound up logarithmic factor. Meanwhile, BOBW algorithms aim to achieve near-ope opttmml regret in both the stochastic and adver- sarial regimes. Leveraging the SPA learning rate and the technique for s-agnostic algorithms combined with a new analysis to bound the variation in FTRL output in response changes in regularizer, bound. Additionally, we explore partial monitoring and
establish the first BOBW algorithm
with a sparsity-depencee demonstrate that the proposed SPA Icarning rate framework allows to achieve a game-dependent bound and the BOBW simultancously.
Introduction
This study considers the multi-armed bandits (MAB) and partial monitoring (PM). the MAB problem, the learner selects one of & arms, and the adversary simultaneously determines the loss of each arm, l, = (fe1...... lxx) in [0, 1ja or [-1, _| After that, the learner observes only the loss for the chosen arm. The learner's 's goal is to minimize the regret, which is the difference between the learner's s total loss and the total loss of an optimal arm fixed in hindsight. PM a generalization of MAB, and the leamer observes feedback symbols instead of the losses.
'This work was done when the author was with Kyoto University and RIKEN.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One of the most promising frameworks for MABs and PM is follow-the-reguie setbe--gularized-leadeee (FTRL) [5, 12], which determines the arm selection probability each round by minimizing the sum of the cumulative (estimated) losses so far plus convex regularizer. Note that the well-known Exp3 algorithm developed in [5] is equivalent to FTRL with the (negative) Shannon entropy regu- larizer. FTRL is also known to perform well for the classic expert problem [17] and reinforcement learning [52]. Furthermore, when the problem is "benign", it is known that FTRL can exploit the underlying structure to adaptively improve its performance. Typical examples of such adaptive improvements are (i) data-dependent bounds and (ii) best-of-bothhworrd (BOBW).
Data-depended bounds have been investigated to enhance the adaptivity of algorithms to given structure of losses in the adversarial regime, where feedback (e.g., losses in MABs) decided in an arbitrary manner. There are various examples of data-dependen bounds, and this study considers sparsity-dependen boundy and game-dependen, bounds.
A sparsity-dependent bound is an important example of data-dependent bounds, as sparsity frequently appears in real-world problems. For example, in online advertisement allocation, it is often the case that only a fraction of the ads is clicked. Although there are some studies for sparse MABs [10, 27, 51], all of them assume that (an upper bound of) sparsity level 2 ||e/|lo = i[ [A] ba A 03 is known beforehand, which in many practical scenarios does not hold.
The concept of game-dependen bound was recently introduced by Lattimore and Szepesvári [32] to derive a regret upper bound that depends on the game the learner is facing. As the authors suggest, one of the motivations for the game-dependent bound is that previous PM algorithms are "quite conservative and not practical for normal problems". For example, whereas the Bernoulli MAB is expressed PM, algorithms for PM do not always achieve the minimax regret of MAB [5]. The game-dependent bound enables the learner to automatically adapt to the essential difficulty of the game the algorithm is actually facing.
The BOBW algorithm aims to achieve near-optimal regret bounds in stochastic and adversarial regimes, where the feedback is stochastically generated in the stochastic regime. Since we often do not know the underlying regime, it is desirable for an algorithm to simultaneously obtain a near-optimal performance both for the stochastic and adversarial regimes. For multi- bandits, Bubeck and Slivkins [9] developed the first BOBW algorithm, and Zimmert and Seldin [53] proposed the well-known Tsallis algorithm, which achieves the optimal regret for both regimes. The Tsallis-INF algorithm also achieves favorable regret guarantees in the adversarial regime with a self-bounding constraint, which interpolates between the stochastic and adversarial regimes.
To realize the aforementioned adaptivity in FTRL, the adaptive learning rate (a. time-varying learning rate) is one of the most representative approaches. This approach adjusts the learning rate based on previous observations. In the literature, adaptive learning rates have been designed to depend on stabiliry or penalty, which are components of a regret upper bound of FTRL. The stability term increases if the variation of FTRL outputs in the adjacent rounds is large, and uubility--ependeen learning rates have been used in a considerable number of algorithms available in the literature, e.g., [32, 37, 38] and references therein. In contrast, the penalty term comes from the strength of the regularization, and recently penalty-depene guarantees [22, 46). However, existing mabillty-dependern (resp. penalty- dependent) learning rates are designed with the worst-case penalty (resp. stability), which could potentially limit the adaptivity and performance of FTRL. (There are numerous studies related to this paper and we include additional related work in Appendix C.)
learning rates were considered achieve BOBW
1.1 Contribution of this study
In this paper, in order to further broaden the applicability of FTRL, we establish a generic framework for designing an adaptive learning rate that depends on both the stability and penalty components simultaneously, which we call a saability-penally penalry-adaptive (SPA) learning rate (Definition 2). This
enables us to bound the regret approximately by Ö(v VVT 2ch4+1) for stability component (zt),
and a penalty component (hz),, which we call SPA regrei bound (Theorem 1). With appropriate selections of and hr, this result yields the three important adaptive bounds mentioned earlier, namely sparsity, game-dependency, and BOBW. In particular, our contributions are as follows (see also Tables and 2):

---

Table 1: Regret upper bounds with
bounds in multi-armed bandits. T is the time horizon. Σ the level of sparsity losses. Let L2 Σx= |lee].. and ||éello s implies L2 Σ ||e|| < sT since |4 - 1. Amin is the minimum suboptimality gap. Adv. and Stoc. are the abbreviations of the adversarial and stochastic regime, respectively. Reference
s-agnostic?
Range of tei
Regime
Regret bound
Kwon and Perchct [27]
[0, 1]
Adv.
((VsT)
Kwon and Perchet [27]
No
[0, 1]
Adv.
2/e xT (k/(
Ours (Sec. 5.1.1, Cor. 2)
Yes
[0.1]
Adv.
2v2 La log k O(KK ((KTToog)))
Bubeck et al. [10]
No
[-1,1]
Adv.
10 L2 log 20k log T
Ours (Sec. 5.1.2, Cor. 3)
Yes
[-1,1]
Adv.
4v L2 log k + 2k log
Ours (Sec. 5.2, Thm. 4)
Yes
[-1,1]
Adv.
1v L2 log k log T + (k log
Stoc.
( log( log(k:)) Amin))
Table 2: Regret bounds for non-degenerate local PM games. V,, V,, and V are game-dependent quantities satisfying V, S V/' < V (see Section 6 and Appendix B for definitions). H(4:) is the Shannon entropy for FTRL output yr-
Reference
Game-dependent?
BOBW?
Order of regret bound
Many existing studies on PM
No
No
Lattimore Szepesvári [32]
No
Vi log l
Tsuchiya et al. [46]
No (only game-olas--dependem))
Yes
"IT H(g+1)
Ours (Sec. 6, Cor. 5)
Yes
Yes
EEE VoH(g
(Section 5.1) We initially provide new algorithms for sparse MABs as preliminaries for establishing a BOBW algorithm with sparsity-deennden bound. In Section 5.1.1, we propose novel estimator of the sparsity level, which is linked to stability component and induces L2 =
-",1" < sT. We demonstrate that a learning rate using this estimator with the Shannon uniform exploration immediately results in an OVv log regret bound for 4 [0, 1 Section 5.1.2, we investigate possibly negative losses [-1, 1]k We employ the time-invariant log-barrier proposed in [10] to control the stability term. This allows us to achieve an O(vT,2 log k) regret bound for losses in [-1, 1] even without the (((7)) -2/3) 2/3) uniform exploration. This a key component for developing the BOBW guarantee that we discuss next. Note that Section 5.1 serves preliminary findings for the subsequent section.
entropy regularizer and (((TT)
(Section 5.2) We establish BOBW algorithm with sparsity-dependent bound. In order to achieve this goal, we make another major technical development: we analyze the variation the FTRL output when the regularizer changes (Lemma 7), which holds thanks the iieeinnarian log-barrier and may be of independent interest. This analysis is necessary since we use time- varying learning rate to obtain BOBW guarantee, whereas Bubeck et al. [10] uses constant learning rate. This technical development successfully allows us to achieve the goal (Theorem 4) in combination with the SPA learning rate developed in Section 4 and technique for exploiting sparsity in Section 5.1.2.
(Section 6) We show that the SPA learning rate established in Section 4 can also he used to achieve a game-dependent bound and BOBW guarantee simultaneously, which further highlights the usefulness of the SPA learning rate.
2 Setup
This section introduces the preliminaries of this study. Sections 2.1 and 2.2 formulate the MAB and PM problems, respectively, and Section 2.3 defines regimes considered in this paper.

---

Notation Let || || and || be the Euclidian, L1-, and -norms for a vector 2, respectively.
Let ||æ||o be the number of non-zero elements for a vector x. Let Px = {p E [0, 1] |lpll1 = 1) be the (k 1) d-dimensional probability simplex. A vector e; E {0, 1] is the i-th standard basis of IR*, and is the all-one vector. Let Dv be the Bregmun divergence induced by differentiable convex function t i.e., Do (v, 7) = (p)) (())= (V q)- Table 3 in Appendix A summarizes the notation used in this paper.
2.1 Multi-armed bandits
In MAB with k-arms, at each round [2] = (I,2...., the environment determines the loss vector & = (L11 f22,.... ., l(x)T in [0, 1) or 1-1, 1]k. and the learner simultaneously chooses an arm A, E [k] without knowing l. After that, the learner observes only the loss 4, for the chosen arm. The performance of the learner is evaluated by the regret Regz. which is the difference between the cumulative loss of the learner and of the single optimal arm, that is,
arg min TF E ftal
and Regr- Ei=1(Ces randomness of the algorithm and the randomness of the loss vectors (f))==1-
le )].
where the expectation is taken with respect to the internal
2.2 Partial monitoring
Formulation A PM game = (C, b) with k-actions and d-outcomes is defined by pair of loss matrix & [0, 1]ked and feedback matrix t Ekxd, where Σ is set of feedback symbols. The game is played in a sequential manner by a learner and an opponent across rounds. The learner begins the game with knowledge of L and 4. For every round t [T]. the opponent selects an outcome H, E [d], and the learner simultaneously chooses an action A, E [k:). Then the learner suffers an unobserved loss L A, and receives only feedback symbol σN & &A,Z, where Low is the (a, 2-)th element of L. The learner's performance in the game is evaluated by the regret Regr as in the MAB case: a" arg mi] E E> Lav.] and Regr- E
Laa
E
1= (eA. - , where la E Rd is the a-th row of L.
Several concepts in PM Let m - |Σ| be the maximum number of distinct symbols in a single row of + E D Different actions a and are duplicate if la = la- We can decompose possible distributions of outcomes in Pa based the loss matrix. For every action [k). cell e, {u Pa maX [K] (fa 4 I 0} is the set of probability vectors in Pa for which action is optimal. Each cell is a closed convex polytope.
Define dim(C.) ( as the dimension of the affine hull of e,, Action is said to be dominated if e, 0. For non-dominated actions, action is said to be Pareto optimal if dim(C.) if dim(C.) < d 1. Let IT be the set of Pareto optimal actions. Two Pareto optimal actions a, h E II are called neighbors if dim (e,, n ne,) = d 2, which used to define the difficulty of PM games. PM game is said to be non-degenerate if it has no degenerate actions. We assume that PM game is non-degenerate and contains no duplicate actions.
and degenerate
The difficulty of PM games is characterized by the following observability conditions. Neighbouring actions a and b are locally observable if there exists wab : [k] x Σ + R such that was(c, o) = 0 for e ø {a, b} and Σ Was(c, <xx) = Lax Lix for all x E [d]. A PM game is locally observable all neighboring actions are locally observable, and this study considers locally observable games.
Loss difference estimation Let H be the set of all functions from [k] x E to Rd. For any
locally observable games, there exists G E H. such that for any b, E II, Σx (G Par)) G(a, Pax)c) = Lax fex for all x E [d] [32]. For example, we can take G = Go defined by Gola, 0)L E Eegpath (b) (a o) for relations and path y (b) the set of edges from E IT to an arbitrarily chosen root e on T [32]. See Appendix C and [31, Chapter 37] for a more detailed explanation and background of PM.
II, where T is tree over II induced by neighborhood

---

2.3 Considered regimes
We consider three regimes on the assumptions for losses in MABs and outcomes in PM. In the stochastic regime, a sequence of loss vector (&x) in MAB and that of outcome vector (mz) in PM follow an unknown distribution v in an i..d. manner. Define the minimum suboptimality gap in Amin minazaa A. for A, = E [Lea - lta) in MAB and A. = Exzrer [(fa la ex. in PM. Note that the definitions of l in MAB and PM are different.
In contrast, the adversarial regime does not assume any stochastic structure for the losses or outcomes, and they can be chosen in an arbitrary manner. In this regime, the environment can choose l, for MAB and 24 for PM depending the past history until the (t 1)-th round, (Aa)==i-
We also consider, the adversarial regime with a self-bounding constraint [53], an intermediate regime between the stochastic and adversarial regimes.
Definition 1. Lei A E 20 and C 2 0. The environment is in an adversarial regime with a (A, C) self-bounding constraint if holds for any algorithu that Regr E I - C].
One can see that the stochastic and adversarial regimes are indeed instances of this regime, and that well-known stochastic regimes with adversarial corruptions [36] are also in this regime (sce [53] and [46] for definitions in MAB and PM, respectively).
We assume that there exists a unique optimal arm (or action) a", which was employed by many studies aiming at developing BOBW algorithms [18, 34, 49, 53].
3 Preliminaries
This section provides preliminaries for developing and analyzing algorithms. We first introduce FTRL, upon which we develop our algorithms, and then describe the self- holl-boundin technique, which is a common technique for proving BOBW guarantec.
hollow-the-rggllaiieed-eeddd In the FTRL framework, an arm selection probability pr E Pp at round is given by
q: arg min gEP,
Σ To. 9
+ (() and Pe Jz(g().
(I)
where D. E R is an estimator of loss l at round t, p,; Pa + strongly convex regularizer, and T.: Ps PA. is a map from the output of FTRL d. to an arm selection probability vector pt.
In the analysis of FTRL, it is common to evaluate Σt (Tt, Pt p) = -Ei (Tt, 4e p) + E (We. Pt q.) for some p E Py. known (see e.g., [31, Exercise 22) that quantity 21=1 (Tt, p) is bounded from above by
(p((+t)) - +1+1 + @T+1(p)
(1(1)) Σ (ge ge+1 1, 0.) Do, (4++1, (2)
penalty term
stability
We refer to the terms in (2) as a penalty and stability terms, and to the quantity (Dr. Pt qt) as transformation term. Note that, though this study focuses on examples in which 4 is not dominant, this term may be dominant dependent on the choice of regularizers.
Self-bounding technique A self-bounding technique is a common method for proving BOBW guarantee [18, 49, 53]. In the self-bounding technique, we first derive regret upper and lower bounds in terms of a variable dependent on the arm selection probabilities (pt); or the FTRL outputs (q: ) and then derive regret bound by combining the upper and lower bounds. We use version proposed in [22]. We consider Q(1), Q(),, P(i), and P(i) for i [k] defined by Q(i) Σt= qıs),
((i) = E [Q()) P(t) = ET=(11 Pts), and P(i) = E [P(i)]. Note that Q(1,, P(i) [0, for any E [k). terms of Q(1) or P(i), we can obtain the lower bound of the regret for the adversarial
regime with self-bounding constraint follows:
5

---

Lemma ([46, Lemma 4)), In the adversarial regime with self bounding constraint (Definition 1), there exists c' E (0, 1] such that Pti 2 for all t E [T] and i [Ke], then Regr 2 Pmnn C 22e d A mmn Q(an)(a))))))))))a))))))) C.
It is known that the sums of the entropy H() of (pe), is bounded by P(i) as follows: Lemma 2 ((22, Lemma 4)). Let (qt) be any sequence of probability vectors and define Q(1)
E (1 - qu)). Then for any i E [k]. Σ (())) S Q(1) (oggeeT//Q())
Based on Lemmas and 2, it suffices to show Regr S E VV H(ae) polylog(T) BOBW guarantee in MAB. This is because, for the adversarial regime, using H (q.) - log k immedi- ately implies Ö(vT) bound, and for the stochastic regime, using Lemmas I and 2 roughly bounds the regret as Regr = 2Regr - Regr S vQ(a*) (Tlylog(T)
prove
(olylog))) - Amin AminQ((a)) z polylog(T)) /minn
4 Stability-penaly-aaapii (SPA) learning rate and regret bound
This section proposes a new adaptive learning rate, which yields regret upper bound dependent on both the stability component 2, and penalty component Ie for various choices of 2; and ht. When we use learning rate 7hs the analysis of FTRL. boils down to the evaluation of
SP Regr
: 7/
hct1 +
Σ 7 for some A > 1.0
7
In particular, when we use the Exp3 algorithm. h; is the Shannon entropy of the FTRL output at round f. This can be confirmed by checking the existing studies (e.g., [22, 46]) or the proofs in --SP SP
Appendices F, G. H.2, and I. To favorably bound Regr we develop new learning rate framework, which we call the jointly stability- and cenalty-adaptivy learning rate, or the stability-penally penally (SPA) learning rate for short:
learning rate). Let ((he, 21, a)) be non-negative reuls such that h1 2 for all t E [T]. (ž,h1 + E'm sche+1)(= non non-eecraa,ing. and žeh1 2 zehe+1
Definition 2
for all t E [T. Let c1, C2 > 0. Then, a sequence of (nm)T= is a SPA learning rate if it has a form of
2
17: B. B1 > 0, and B411 31
V C2 2₂h1 E.= zgha+1
Remark. To the best of our knowledge, this is the first learning rate that depends on both the stability and penalty components. Note that when we set the penalties to their worst-case value, that is, he = h for all E [T] (recalling he S h1), the SPA learning rate in (4) becomes equivalent to the standard type of the learning rate, which depends only on the stability and has the form
of 3e = 1/1. = 3 +1 Σ žs On the other hand, when we set the stabilities to be their worst-case value, that is, 2 max Zr, the SPA learning rate in (4) corresponds to the learning rate dependent only on the penalty in [22, 46].
SP
Using learning rate (ne) in (4), we can bound Reg follows.
penalty- regret bound). Let (mo)r= be a SPA learning rate in Defini- Theorem SP
tion2 2. Then Regr in (3) is bounded as follows:
(I) If ((hr, ze, Tm in (m)) satisfies Vertichi (stability condition (S1)), then
(Br + B.) 2 + 2e for all L (T) some
C1
SP RegT
< c1 +
(
A log
1+
T
Ru
))
C2 + Er +
Σ
T
21141
(5)
C1
mml
(II) hf = hn for all 1. E [T], C2 0, and ((hr, 2z, Z, T in (1)) satisfies Br > Vhi
E 2s for
SP some a > (stability condition (S2)), then Regr S (1 + a Vhn Σi= 2.

---

The proof of Theorem I can be found in Appendix D. In Part (1) of Theorem 1, we can see that Regr is bounded by v Et=1 21h411, which will enable us to obtain BOBW and data-dependent bounds
SP
simultaneously. Note that Regr which is the component of the regret, often becomes dominant in particular when we use the Shanon entropy regularizer. Thus, checking the stability condition (S1)
and applying Theorem to bound Regr almost complete the regret analysis. In Section 6, we will that applying Theorem immediately provides BOBW bound with game-dependent bound for PM. In contrast, when deriving BOBW W with a dependey- bound for MAB in Section 5, we will develop additional techniques and conduct further analysis, for example, to satisfy the stability condition (S1), making use of the time-invariant log-barrier regularizer.
depeseny bounds in multi-armed bandits
This section establishes several sparsity-dependee bounds. We use the FTRL, framework in (1) with the inverse weighted estimator De E R given by Tr = E, 1 [A, = i//pH. This estimator is common in the literature and is useful for its unbiasedness, i.e., E Ep,-pe [T Pr. = lz- We first propose algorithms that achieve sparsity-depende preliminaries for the subsequent section. Following that, in Section 5.2, we establish a BOBW algorithm with sparsity-dependees bound based on the SPA learning rate. More specific steps are summarized as follows.
bounds using stability-depende
learning rates in Section 5. as
Section 5.1.1 discusses the case of 4 E [0, 1]"h and shows that appropriately choosing in the SPA learning rate (4) with the Shannon entropy regularizer and @((AT) -2/3) uniform exploration achieves a (VTTa log A)) regret for l, E [0, 1] without knowing L2.
Section 5. considers the case of 4, E [-1, 1J*, which is known to be more challenging than & E 1].. We show that the time-invariant log- log-barrier enables us to choose a "tighter" 2 in (4), which removes the uniform exploration used in Section 5.1.1. This not only results in the bound of OL log k) for & E 1] but also becomes one of the key properties to achieve BOBW.
bound using the technique developed in Section 5.1 and Theorem 1. While Theorem itself is a strong tool leading directly the result for PM (Section 6), its application does not lead to the desired bounds. In particular, in
Section 5.2 presents BOBW algorithm with
this setting the Ö(VIT -- 2che+1) term derived through Theorem does not immediately imply a BOBW guarantee with a sparsity-dependeen bound. To solve this problem, we develop a novel technique to analyze the variation in FTRL outputs q: in response the change in regularizer (Lemma 7), and prove a BOBW bound with a sparsity-dependen bound of ((TTz2 log l log T))
5.1
Parameter-agnostic -parsity-dependent bounds
This section establishes s-agnostic algorithms to achieve sparsity-dependent bounds for the adversarial regime, which are preliminaries for Section 5.2.
5.1.1 Le Lg-agnostic algorithm with O log k) bound for & E [0, 1
Here, we use Pa Ty (g.) for Tz(g) = (1 7)1 + 11 and y (log k/ and assume y E 1/2] 73/3
(this holds when 2 /8k log K)), which implies 2p: 2 qt. We use the Shannon entropy regularizer
(p(p) = (p) = 1 ns (p) Σ ps log p. with learning rate n = 1/8, and
201
k
ClW
G PtA.
B
B 3.
for Wi
(6)
Vin
7
Vlg bogk/z + Σ1- W.
which corresponds to the learning rate in Definition with hy <- H(q)= log k, 2z f- wis 5, < k/ k/7, and <- 0. The uniform exploration is used to satisfy stability condition (S2) in Theorem 1, the amount of which is determined by balancing the regret coming from the uniform exploration and stability condition (S2). Theorem immediately gives the following bound.
7

---

Corollary 2. When T 2 Voglog k. the above algorithm with = 1/v2 achieves Regr S 2v2VTT2 log k- + (2v2+1)00 + Regr- S (4v2+ +
log k)//3 without knowing L2. In particular, when T 2 7k2
The proof is given in Appendix F. The most striking feature of the algorithm is its L2 (or aaagnssii property. This essentially made possible by the learning rate using the data-dependent quantity we
in (6), which satisfies E
- VV B(w))
B(us) = - VI ex VT2. The leading
constant of the bound is better than the existing bounds, as shown Table I, despite its agnostic property. Note that while the first-order bound in [49] implies the above sparsity-dependen bound when & E [o. 1J this does not hold when l E [-1, 1], which we investigate in the following (see Appendix K for details). We will see in Section 5.1.2 that this assumption can be totally removed by adding a invariint log-barrier regularization.
5.1.2 L--agnostic algorithm with O(VL2 log + k log T) bound for & E 1-
Here, we consider the case of l [-,, It is worth noting that the negative loss cannot be handled by simply shifting the loss since it removes the sparsity from the losses (4t); see [10, 27] and Appendix K for further details. We directly use the output d. as Pt, that is, Pt. 9:- We use the hybrid regularizer consisting of the negative Shannon entropy and the log-barrier function,
(p) = 1 ( + 240lB(p) (p), where (p) = E log(1/2;). We use learning rate T/p = 1/3
and
of 8h1
for 1 we min {1, PtA,
C14t
B1
Bet1 = Be
2n S
(7)
Mogky ue + E Vs
where we is defined in (6). Learning rate (7) corresponds to that in Definition with he H(qi)
log k. zt & Vt, 2t x- Vt, and C2 + 0. We then have the following bound:
Corollary 3. If we run the above algorithm with e₁ 22, Regr S 4/2 L2 log 2k 22 T k+ 1/4, which implies that Regr S 4v/2/5T log E + 2k log + kk 1/4.
The proof is given in Appendix G. Corollary 3 removes the assumption of T 2 / in Corollary 2, and it also improves the leading constant of the regret in [10]. Note that one can prove a bound of the same order, but with worse leading constant, by setting 31 2 15k: and combining the analysis similar to that in Section 1. and the stability bound [10]. We successfully remove the assumption of T > 7k2 / thanks to the following lemma, which serves one of the key elements in achieving a BOBW guarantee with a sparsity-dependee bound (The proof is given in Appendix G.):
Lemma (Stability bound for negative losses). Let E [-1, 11 and Tis l, [A, il/pu be the inverse weighted estimator. Assume that q: < op. for some ò 2 1. Then the stability term of FTRL bounded as
with the hybrid regularizer 2; 1 Lins + 25 v.
Gr PeA.
{ PLA. 27p
(g. 9t-1: v1) Da, (g(+1, q)) S 8n
min
Remark. We observe from Lemma 3 that the stability term is bounded in terms of Pt, and the most important observation is that this vg is bounded by the inverse of the learning rate 1/(27)) = =3//2. i.e., Pt < B./2. This enables us to guarantee the stability condition (S2) Theorem without needing to mix the (((kT) -2/3) uniform exploration used Section 1. Moreover, this will be key property to prove BOBW with pparsity-dependee bound in the next section.
As minor contribution, by directly bounding the stability component, the RHS of Lemma 3 has smaller leading constant than the bound obtained by using the bound in [10].
5.2 Best-of-both-worlds guarantee with -ppredey-dependent bound
Finally, ready to establish BOBW algorithm with sparsity bound and derive its regret bound. We use Pt Je(gt) (1 7)9. + 2 with 7 $ (i.e., ((1/T) uniform exploration)
8

---

and assume y E 10, 1/2]. which implies 2p: 2 9e and is S T. We use the hybrid regularizer
$ + wmm + 4xbLB with learning rate = 1/8 and
B1 = 15k, B4+1 = Be
4
with he
1 H(p.),
(8)
8le + whet + Σ5= Pglis11
&
where v, is defined in (7). Note that this learning depends on both the stability and penalty components. This corresponds to the SPA learning rate in Definition 2 with =q <- 1/2 = + vs u / h1, and 22 f 81c². One can see that stability assumption (S1) in Part (I) Theorem are satisfied thanks to Vt S 3t (see Appendix H for the proof). We then have the following bounds.
Theorem 4 (BOBW with sparsity bound). Suppose that T 2 2k. Then the above
algorithm with 12 (1 T/B,) (Algorithm 2 in Appendix H) achieves
Regr S 4 T2 log(1 + +T) + O(k log T))
in the adversarial regime,
Regr o s (log(T) log(kTT)
Cslog(T) log(A())
Amin
Amin
in the adversarial regime with (A, self-bounding constraint, and Regr O L. log())
in the stochastic regime.
The proof is given in Appendix H. This is the first BOBW bound with the dependent) bound. Note that the bounds in the stochastic regime and the adversarial regime with a self-bounding constraint can also exploit the propoerty the underlying losses. The bound in the stochastic regime is suboptimal in two respects: its dependence on Amin and (log T Concurrently, two separate studies improve each suboptimality ([25) for Amin and [13] for (log T)²), but it is highly uncertain if we prove a BOBW with dpersily-deeendenl bound based on their approach, and it an important future work to investigate this problem.
(Io2-
Key elements of the proof In the following, we describe some key elements of the proof of Theorem 4. We need to solve one remaining technical issue. Using Part (I) of Theorem 1, we can
show that the regret is roughly bounded by E v V 1rhe+1 S VVE B[ush1+1]. However, this
quantity cannot be straightforwardly bounded since h++1 depends on Vt-
To address this issue, we analyze the behavior of arm selection probabilities when the regularizer changes. In particular, we first prove in Lemma 7 that h++1 h, + k (Be41 / 1) he+1- This lemma can be proven by novel analysis evaluating the changes of the FTRL outputs when the learning rate varies (given in Appendices H.1 and H.2) which is not considered and required when we use time-invariane learning rate (e.g., [10]. Using the last in-
equality, we have v VIT B[ycket1] S VET B[veke] + k ETn BiPr (Be+1/Be 1) h4411] X
T [VEra vehi
El Elushe] + lo Et B[(B++1 B.) 1et is y Et Blunhd B[uche) + +
V Ei= E[u.h + k which holds thanks again to 1 S Br and based on the fact that x S Va ba for a, b x > 0 implies x S vT + a (here we ignore some logarithmic factors). This combined with the self- leff-hounding technique leads to BOBW guarantee in the stochastic regime.
Implementation One may wonder how to compute 31+1 satisfying (8) since h = het (Br+1) depends on B.41. In fact, this can be computed by defining F, [3,, 3 + +T] + R as F.(a) =
B. + c / 81c + v1h4t1(a) + E'= v.hst1) and setting 3t+1 to be root of F.(a) 0. Such a can be computed using the bisection method because F, is continuous (proved in Proposition in Appendix H.3). The detailed discussion can be found in Appendix H.3.

---

Best-of-both-worlds with game-dependent bound for partial monitoring
This section discusses the result of a BOBW guarantee with game-dependent bound for P.M. The desired bound is obtained by direct application of the SPA learning rate and Theorem 1, which highlights the usefulness of the SPA learning rate. Due to the space constraints, the background and algorithm are given in Appendix B.
We rely the Exploration by Optimization (EbO) by Lattimore and Szepesvári [32]. Define
(y 2 (T)Tes
biasa. (G;
1 M
("Cla, $az)) )
ST G3 nt)
max #E|d
Pa Vo
(9)
?
Pa
where Tn is learning rate, (z( (q, exp())))) + 1) and bias,(G;z)
(q: Lex
Ea_, G(a, Par)) + maxeen G(aa Par)e Laz) the bias of the estimator. Note that the first and third terms in (9) correspond to the stability and transformation terms. Then in EbO we choose (Pt, G2) E Pk x by
arg min (pt,Gi) PEP (P.) GE
(T Ge) for P)(())= (p E PA: p g/
(10)
where (/(()) is the feasible set proposed in [46]. Let opt (n.) be the optimal value of the optimization problem and V/ = max(0, opt (nt} be its truncation.
Remark. It is worth noting that V/ = max(0, opt (n:) captures game difficulty the learner is facing discussed in [32]. As discussed above, ST G) in (9), the objective function that determines opt', (1)²), correspond to the components of the regret upper bound of FTRL. Hence, the smaller (T G) can become by optimizing p and G, the smaller the regret can become, and thus opt, q. (1)) captures the game difficulty.
Now we are ready to state our result.
Corollary 5. For any non-degenerate PM games, there exists an algorithm based on a SPA learning rate achieving Regr = O V logo(())) log(1 + +T) + mk? /log(k) log(T) in the adver- sarial regime, and Regr O(m² 1 (og(T) log(kT)/A / + /Cm² h log(T) log(kT)/ Amia mkk /Tog(k) (T)( in the adversarial regime with a (A, C, T) self-bounding constraint.
An extended result and the proof are given in Appendices B and I, respectively. Recall that V = max (0, opt' (ne) in the bound reflects the difficulty of the game the learner is facing, rather than the worst-case difficulty of the class of the game. The bounds in both regimes are optimal up to logarithmic factors, and further detailed comparisons are given in Table 2 and Appendix B.
7 Conclusion and future work
In this paper, we established the stability-penalty provides the regret upper bound that jointly depends on the stability and penalty components of FTRL (Theorem 1). This learning rate combined with the technique and analysis for bounding stability terms allows us to achieve BOBW and data-dependent bounds (sparsity- and game-dependent bounds) simultaneously in MAB and PM.
(SPA) learning rate (Definition 2), which
There are some remaining questions. First of all, it would be important future direction apply the SPA learning rate to other online decision-making problems or regularizers. For example, it is as to investigate online learning with feedback graphs [3]. in which the Shannon entropy regularizer (or the Tsallis entropy with the exponent larger than 1 1/ log k) is necessary to achieve nearly optimal regret bounds. Another interesting example to employ the Tsallis entropy regularizer in the SPA learning rate, for instance, to improve logarithmic dependences on the regret bounds, while this paper we only focused on the Shannon entropy. Second, it is an open question whether we can achieve the bound of O(vsT ST log(k/s)) the pparity-ddpendenn bound without knowing the sparsity level Finally, while we only considered PM games with local observability, investigating the game-dependent bound with the BOBW guarantee is possible for PM with global observability is important future work.
dominant
10

---

Acknowledgments and Disclosure of Funding
TT was supported by JST, ACT-X Grant Number JPMJAX2 10E, Japan and JSPS, KAKENHI Grant Number JP21J21272, Japan. JH was supported by JSPS, KAKENHI Grant Number JP21K11747, Japan.
References
[1] Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smoothness. In Advances in Neural Information Processing Systems, volume 28, pages 2197-2205, 2015.
[2] Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák. Hannan consistency on- line learning in case of unbounded losses under partial monitoring. In International Conference on Algorithmic Learning Theory, pages 229-2433, 2006.
[3] Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 23-35, 2015.
[4] Jean-Y Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory, volume 7, pages 1-122, 2009.
[5] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-71) 2002.
[6] Gábor Bartók. A near-optimal algorithm for finite partial-monitriigg games against adversarial opponents. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30, pages 696-710, 10, 2013.
[7] Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Minimax regret of finite parial-monitoring games in stochastic environments. In Proceedings of the 24th Anmual Conference on Learning Theory, volume 19, pages 133-154, 2011.
[8] Gábor Bartók, Navid Zolghadr, and Csaba Szepesvári. An adaptive algorithm for finite stochastic partial monitoring. In the 29th International Conference on Machine Learning, pages 1-20, 2012.
[9] Sébastien Bubeck and Aleksandrs Slivkins. The best both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 42.1 12.2-4 2012.
[10] Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature in multi- armed bandits. In Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 111-127 2018.
[11] Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. Improved path-length regret bounds for bandits. In Conference on Learning Theory, pages 508-528, 2019.
[12] Nicolò Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Regret minimization under partial monitoring, Mathematics of Operations Research, 31(3):562 580. 2006.
[13] Christoph Dann, Chen- Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. arXiv preprint 23V:22302.0939, 2023.
[14] Liad Erez and Tomer Koren. Towards ofst-of-all-woote online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 34, pages 28511 1-25221,, 2021.
[15] Dean Foster and Alexander Rakhlin. No internal regret via neighborhood watch. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22, pages 382-390, 2012.
11

---

[16] Dylan Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. In Advances in Neural Information Processing Systems, volume 29, pages 1734-4743 2016.
[17] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1): 19-139, 1997.
[18] 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.
[19] Elad Hazan and Satyen Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(4), 2011.
[20] William W Hogan. Point-to-set maps in mathematical programming. SIAM review, 15(3): 591-603, 1973.
[21] Shinji Ito. Parameter-fiee 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.
[22] Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-bothhworlds algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, 2022.
[23] Shinji Ito, Taira Tsuchiya, and Junya Honda. Adversarially robust multi-armed bandit algorithm with variance -ieranneedeeeeeett regret bounds. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pages 1421-1422) 2022.
[24] 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 Processing Systems, volume 34, pages 20491-20502, 2021.
[25] Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-bothh botth-hooohsss guarantees for multi-armed bandits: Ftrl with general regularizers and multiple optimal arms. arXiv preprint 2xX::23302.13344 2023.
[26] 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.
[27] Joon Kwon and Vianney Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case. Journal of Machine Learning Research, 17(227): 2016.
(28) Joon Kwon, Vianney Perchet, and Claire Vernade. Sparse stochastic bandits. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1269-1270, 2017.
[29] T. L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[30] Tor Lattimore and Csaba Szepesvári. Cleaning up the neighborhood: A full classification for adversarial partial monitoring. Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98, pages 529 556, 2019.
[31] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[32] 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.
[33] Chung- Wei I Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 2516-25516 2564,, 2020.
12

---

[34] Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: AdaNormalHedde.. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 1286-1304, 2015.
[35] 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.
[36] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 14-122, 2018.
[37] Brendan McMahan. Follow-theerrgullriieedd-
and mirror descent: Equivalence theorems and regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15, pages 525-533, 2011.
[38] Francesco Orabona. A modern introduction online learning. CoRR, 1bs.1192//111...1133.... 2019.
URL http://arxiy... http://wwwwvriro//.///// httg/abs/1912. 13213.
[39] Antonio Piccolboni and Christian Schindelhauer. Discrete prediction games with arbitrary feedback and loss (extended abstract). In Computational Learning Theory, pages 208-223,
2001.
[40] Roman Pogodin and Tor Lattimore. On first-order bounds, variance and gap-dependent bounds for adversarial bandits. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 894-904, 2020.
[41] Aldo Rustichini. Minimizing regret: The general case. Games and Economic Behavior, 29(1): 224-243, 1999.
[42] Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 19011-19022 2022.
[43] Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 1743-1759, 2017.
[44] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1287-1295, 2014.
[45] Taira Tsuchiya, Junya Honda, and Masashi Sugiyama. Analysis and design of Thompson sampling for stochastic partial monitoring. In Advances in Neural Information Processing Systems, volume 33, pages 8861-8871, 2020.
[46] Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-both--orldd algorithms for partial monitoring. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, 2023.
[47] Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-wondd algorithm for combinatorial sandiba. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 8117-8144, 2023.
[48] Hastagiri P Vanchinathan, Gábor Bartók, and Andreas Krause. Efficient partial monitoring with prior information. In Advances in Neural Information Processing Systems, volume 27, pages 1691-1699, 2014.
[49] Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceed- ings of the 31st Conference On Learning Theory, volume 75, pages 1263-1291, 2018.
[50] Chen- Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in non-stationary stochastic environments. In Advances in Neural Information Processing Systems, volume 29, pages 3972- 3980, 2016.
13

---

[51] Kai Zheng, Haipeng Luo, llias Diakonikolas, and Liwei Wang. Equipping experts/bandits with long-term memory. In Advances in Neural Information Processing Systems, volume 32, pages 9929-5939, 2019.
[52] Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems, volume 26, pages 1583-1594 2013.
[53] Julian Zimmert and Yevgeny Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-4) 2021.
14

---

A
Notation
We first describe the approach of EbO by Lattimore and Szepesvári [32], which is strong technique bound the regret in PM with local observability. The key idea behind EbO is to minimize a part regret upper bound of the FTRL with the Shannon entropy. Table 3 summarizes the symbols used in this paper.
Table 3: Notation
Symbol
Meaning
P&
(k- 1iddienniin probability simplex
T E N
time horizon
k E
number of arms actions) arm (or action) chosen by leamer at round t
A E
[R]
$ k
max,/1&]lo, lla, sparsity level of losses 16,2
L2
C E [0, 10.1)
loss matrix
of feedback symbols
① Exxd
feedback matrix
deR
number outcomes
EN
maximum number of distinct symbols in single row of &b
V1 E [4]
outcome chosen by opponent at round /.
ai P.P Pr E Px
output of FTRL at round arm selection probability round regularizer of FTRL at round & learning rate of FTRL round
p,: PA + R
1) = 1/3, > 0
nnn R4 + R
Σ
Ze 2i log 4ú, negative Shannon entropy
LBB R + R
--1 1og(1/x;), log-barrier
R. + R
3 log
LB R. R
log(1/x)
h
penalty component at round stability component round
2t
We
stability component 2, introduced in (6) (Section 5.1.1)
stability component 2, introduced in (7) (Section 5.1.2) stability component 2, introduced in (13) (Appendix B)
V(
C 2 0
corruption level
B Detailed background and algorithm description omitted from Section 6
This section supplements the material that was briefly explained in Section 6. We also consider full information (FI) and MAB as well as non-degenerate locally observable PM (PM-local), and let M be a such underlying model.
B.1 Exploration by optimization and its extension
ppploration-by-ootiiizze
Recall that H is the of all functions from [k] x Σ to R Then EbO consider the choice of (pe, G+) E Px x H to minimize the sum of the stability and transformation terms for the worst-case
outcome given follows (also defined in (9)):
q)) T Lex bias (G:z). (p
mnG((a, Paw)) )} (11)
ST G: qt. Tp)
Σ Pa Me a=1
2E|d]
T/t
T
Pa
Note that the first and third terms in (11) correspond to the stability and transformation terms (divided by the learning rate n)), respectively. We define the optimal value of the optimization problem by
15

---

Algorithm 1: BOBW algorithm with a game-dependent bound for locally observable games
input: B
for 1 t= ..2....du do
Compute de using (1).
Solve (10) to determine Vi max opt (nt) and the corresponding solution Pr and G..
Sample A, Pt and observe feedback d; E Σ.
Compute 3r = Gr(A,, oc)/PeA and update 3 using (13).
opt, = min p. x (p. G; qr.7) 11) and its truncation at round t by V2 = max(0, opt (7:) (appeared in Table 2). Note that this optimization problem is convex and can be solved numerically by using standard solvers [32].
While the vanilla EbO is strong tool to derive regret bound in PM-local, it only has a guarantee for the adversarial regime. Recall that in the self-bounding technique, we require lower bound of the regret expressed in terms of qi (see Lemma 1). However, when we use the vanilla EbO, it may make a certain action selection probability Pto for some action a become extremely small even when the output of FTRL qto is far from zero [32], which makes impossible for us to use the self-bounding technique.
Extending asploration-by-optiiiiae
To solve this problem, the vanilla EbO was recently extended that is applicable to the stochastic regime (and the adversarial regime with oef-bbounding constraint) for PM-local [46]. We define P (q. M) for a class of games M, which the extended version of 2 (g) in (10). by
if M is FI or MAB, if M is PM-local.
M) {p E Ps cond(g, M)} with cond M)
(p g/ (2k)
We then consider the following optimization problem, which can be seen as slight generalization of the approach developed in [46]:
(pt, G+)
arg min (M. Gear
ST(p, G;
(12)
where the feasible region Px of p is replaced with (g, We define the optimal value of (12) by opt, (1). M) and its truncation at round t by V/(M) = max(0, opt', (7), We will abbreviate M when it is clear from a context. The following proposition shows that the component of the regret in (9) can be made small enough even if the feasible region is restricted to P (g. M) C Pk-
Proposition 1. Let M be an underlying model. M is FI, MAB, or PM-local with rj S 1/(2mk²).
1/2
if is FI if M is MAB
opt = sup (n) S V(M)
k/2
gEPe
km2k3
M is PM-local.
One can immediately obtain this result by following the same lines as [32, Propositions 11 and 12] and [46, Lemma 5].
B.2 Algorithm
We use the negative Shanon entropy regularizer 4 m with
Ln for (1) with learning rate т) = 1/3
log(1 1 + T') log k
c V
81 BV
and 3 = Br +
(13)
Vh, + Σl-l Vih
where B = 1/2 for FI, B = k/2 for MAB, and B 2mk for PM-local, which corresponds to the learning rate in Definition with hy + H(g)), 2t < V/. E +- O. and 02 f- Algorithm summarizes the proposed algorithm.
16

---

B.3
Main result
r'y be if M FI or MAB, and 2k M is PM-local. Then we have the following bound.
Corollary 6 (Extended version of Corollary 5). Let M be FI, MAB, or PM-local. Then the above algorithm with C1 Vlog(1 + T)/2 (Algorithm 1) achieves
Regr S E
2 t=1
Vi log(k)) log(1 + + LOBBBlooge log(T))
in the adversarial regime, and
Regr o T' V log (T) log log(kT)
CrM (rrVllo(()) log(T)oogkkT)
+ B log(k) log(T)
min
Amin
in the adversarial regime with a (A, C)T) self- reff-bounding constraint.
The bound for the adversarial regime with a belf-bounding constraint with C' = yields the bound in the stochastic regime, which is optimal up logarithmic factors in FI and MAB, and has the same order as the bounds in [46, Theorem 6].
The bound for the adversarial regime has a form similar to [32] and is game-dependent in the sense that it can be bounded by the empirical difficulty V of the current game. addition, we can also obtain the worst-case bound by replacing V with its upper bound V. This bound is optimal up to ITg(T) factor in and log(k) log(T) factor MAB, and is factor of vlog worse than the best known bound in [32]. which can be seen the cost for the BOBW guarantee (see also Table 2).
C Additional related work
This appendix provides additional related work that could not be included in the main body due to the numerous studies related to this paper.
Multi-armed bandits In the stochastic regime, it is known that the optimal regret is approximately expressed as Reg, = O log m/Amin) [29]. In the adversarial regime (a.k.a. non-stochastic regime), it is known that the Online Mirror Descent (OMD) framework with the (negative) Tsallis entropy regularizer achieves O ((VTT) regret bounds [1, 4], which match the lower bound of Q( kkT) [5].
Data-dependent bound In the adversarial MAB, algorithms with various data-dependent re- gret bounds have been developed. Typical examples of such bounds are first-order bounds depen- dent on the cumulative loss and second-order bounds depending on sample variances in losses. Allenberg et al. [2] provided an algorithm with first-order regret bound of O(VkL" log k) for L min A Σ (l),a). Second-order regret bounds have been shown in some studies, e.g.. [10, 19, 49], In particular, Bubeck et al. [10] provided the regret bound of O(VQ2 log k) for E112. Other examples of dependettnd bounds include path-length bounds in the form of O(VkV, log 7') for V/2 Dr-1e |e, f ll as well as a sparsity-dependent bound, which have been investigated [10, 11, 27, 49, 51].
== = -i=1l114
Sparsity-dependeer bound The study on Perchet [27], who showed that when E, E [0, 1]$, the OMD with Tsallis entropy can achieve the bound of Regr S 2/ee// / log(k/s)) and prove the matching (up to logarithmic factor) lower bound of Reg, = 2(v=T') when T > <=s(4. Bubeck et al. [10] also showed that OMD with hybrid-regularizer consisting of the Shannon entropy and lor-barrier can achieve Reg, S 10 log k 20k log T when l, [-1, 1| Zheng et al. [51] investigated the sparse MAB problem in the context of the switching regret. Although their result is not directly related to our study, they show that sparsity is useful in some cases. Note that all of these algorithms assume the knowledge of the sparsity level and do not have a BOBW guarantee. The study to exploit the sparsity was investigated also in the stochastic regime by Kwon et al. [28). However, they define the sparsity level s by the number of arms with rewards larger than or equal to (i.e., losses smaller than or equal to 0), and hence the definition of sparsity is different from that in our paper.
bound was initiated by Kwon and
17

---

Adaptive learning rate The references therein). To our knowledge, the literature on the penalty- -neend-dependent bound is quite scarce in bandits and considered in the context of BOBW algorithms [22, 46], both of which consider the Shannon entropy regularizer.
learning rate is quite ubiquitous (see [38] and the
Since the seminal study by Bubeck and Slivkins [9], BOBW algorithms have been developed for many online decision- making problems. Although they have been investigated mainly in the context of an MAB [43, 53], other settings have also been investigated, [18, 24, 49], to name a few.
FTRL and OMD are now one of the most common approaches to achieving a BOBW guarantee owing to the usefulness of the self-bounding technique [18, 49, 53), while the first [9] and earlier work [43, 44] on BOBW do not rely on the technique. Most of the recent algorithms beyond the MAB are also based on FTRL (to name a few, [24, 42, 49)).
Our BOBW algorithm with the sparsity-dependet bound can be seen as one of the studies that aim to achieve BOBW and data-dependent bound simuitaneously. There is not so much existing research, and we are only aware of [21, 23, 47, 49]. They consider first-, second-order, and path-length bound, and we the first to investigate the pparsit--dependee bound in this line of work.
Log-barriir regularizer and hybrid regularizer The log-barrier regularizer has been used in various studies (to name few, [14, 16, 35, 40, 491). The time-invariany log-barrier (a.k.a. constant amount of log-barrier [33]), whose properties are extensively exploited in this paper, was invented by Bubeck et al. [10] and has been used in several subsequent studies [33, 51].
Partial monitoring Starting from the work by Rustichini [41], PM has been investigated in many works in the literature [7, 12, 39J. It is known that all PM games can be classified into four classes based on their minimax regrets [7, 30.. particular, all PM games fall into trivial, easy, hard, and hopeless games, for which its minimax regrets ((VT), ((T2/3), and ( respectively. PM has also been investigated in both the adversarial and stochastic regimes as for MAB. In the stochastic regime, there are relatively small amount of works [8. 26, 45, 48), some of which are proven to achieve an instance-dependent O(log 7') regrets for locally or globally observable games. In the adversarial regime, since the development of the FeedExp3 algorithm [12, 39], many algorithms achieving the minimax optimal regret have been developed [6, 7, 15, 31].
D Proof of Theorem 1
Proof. We first prove (5) in Part (I).
Penalty term
First, we consider the penalty term Σí_
(1 11-
1) h441- By the definition of 3e
1et1
in (4),
T
C ciZphe+1
he+1
Σ
(Be+1 - Bb) het1
M1++1
T)c
tm1
mml
+ Ehh +
Ex=1 20ho41
T
aphrt1
مitn zeheas
T
< C1
Sa
V
dx
201
Σ 2ub411
(14)
1=1
Zzh1s41
where the first inequality follows from 5eh1 2 2eh1+1 and the second inequality follows by Lemma given in Appendix J.
Stability term Next, we consider the stability term Σt= 7-24 Using the definition of B, in (4)
and defining U² = V
02 + žgh1 + Σ1=1 2 for t E (0) U (T], we bound Be from below as
B. = B1 +
C 2u
31 +
Ci > 31 +
Σ Zu
(15)
U
UT
C2 + Endy + Σ411 2ghs41
u=1
u=1
18

---

where the inequality follows since (Ut) is non-decreasing. Using the last inequality, we can bound
Σ 11=1
2t
Σ t=1
T
2
Σ
2
2UT C
T
2t (3t + B1) + Σ ==
31
+
1t
B, + 31
Uz
5=
(16)
Since we have Ur (31 + 3+)
2
(31
+
B+) 2 8 21 by the assumption, part of the last
ea inequality is further bounded as
T
++2
Σ
2
dr S log
1 Σ zt
(B. + B1)
Σ.
Σ
(17)
where the second inequality follows by Lemma 8. Combining (16) and (17) yields
T
T
T
U I
2UT log
1
zt
log
1
2
C2 + brhn +
Σ
ah41
(18)
Combining (14) and (18) completes the proof of (5) in Part (I).
We next prove Part (II). For the penalty term, setting h = hi for all / E [T) in (14) gives
1) m
Σ t=1
h4+1 S 2011
hi
2
11++1
1=1
For the stability term, since there exists assumption,
0 such that 3r 2
oc1
V
Ex 2o
for any / E [T] by the
vh.
2
Σ
1h
h1
2t
3
aC1
ac
2==1
Am1
Summing up the above arguments completes the proof of Part (II).
E Basic facts to bound stability terms
Here, we introduce basic facts, which are useful to bound the stability term. We have
2 x
for x 2
E(x) = exp(eppppp x) + + 1
(19)
x
for 2 -1,
((x) = x - x)) s 2 for E
(20)
2 2
We also have the following inequalities for nn components of the negative Shannon entropy and log-barrier function:
log and (x) log(1/x), which
max [a(x -y) Dans (y. x²} = x((a)
for a E R,
(21)
vER
1 for a 2
max
(a(x 9) D (y, x²} ((ax)
(22)
VER
x
is easy to prove these facts by the standard calculus and you can find the proofs of (21) and (22) in Lemma 15 of Tsuchiya et al. [46] and Lemma 5 of Ito et al. [23], respectively.
19

---

F Proof of Corollary 2
Let Regr (a) E
Σ (leA - lta)l for [k]. Here provide the complete proof of Corollary 2.
Proof of Corollary 2. Fix 1" E [k].
Since Pt = (1 - 7) + 1, it holds that
T
Regr (i')
E
LeA=
E1s-
E
(le, Pt - -E4-)
1=1
T
1 L1 k
9.)
))
T (3c. q ex0) + tI
(le. 9i - c + E
7
S
where the last incquality follows by Ei [t] = l and the Schwarz inequality, Then, using the standard analysis of the FTRL described in Section 3, the first term in the last inequality is bounded as
T
T
1) 7tc
H(m) H(9+1)) +
T Σ
(T ai cx) S
(19e 21+1. Ut) - Do, (4++1,
7
7
1=
By (19) and (21) given in Appendix E, the stability term (qt inequality is bounded as
91+1 De) - Do, (9)+1, in the last
(g: - 10+1, Fe) Do, (1t+1, = (g: -e++1, Dt)
Duns (1c+1, 4t)
me
Dalau - (011,)
-
ans (onn((1t11, (1t+1,) 21s)
T/e
qct (ncBes)) S N
1
1
Σ
qualei S nowe
i=1
where the first inequality follows from (21), the second inequality follows by (19) with De 2 0, and
the last inequality holds since Σ qu. I Σ 2pc 2wh-
We will confirm that the assumptions for Part (II) of Theorem are indeed satisfied. definition of 3, in (6), We have
Using the
cWW
2c1
t-1
We
B, = 31=
81 +
1=
Wg
7
s=
Wy
W3
201
Wu
2 31 +
vh1
+
Σd We +
+
E+=1
1--
We
2c1
1-1
k
M
2-1
= B1 +
Wa
We
Vhi
a=1
#=1
==1
201
4: +
[-1
k
2c
B1 +
W
Ws
Vhi
7
h
1=1
wi Hence, stability condition (S2) in Theorem is satisfied with a = 2, and one can see that the other assumptions are trivially satisfied. Hence, by Part (II) of Theorem 1,
where the last inequality follows since 31
2e1
and
vhi
Σ
T
(Tt. gt - ex-) 5
T Σ
1 H(get)
+
Σ
T
maw
H(gn) m
22
6i
+
1 201
h1
Σ
T
we
+
log k
7--1
m
20

---

where in the last inequality we used h1 I log k. Now,
T
T
T
E
Σ
Wt
Blwr]
E
EAe
Σ
11
VL2
PLA.
Summing up the above arguments and setting C 11/22, we have
Regr S 2v2 lo log
+ +T' 1 2222 Le log k + (V2+ 1)( log log
which completes the proof of Corollary 2.
G Proof of Corollary
We first prove Lemma 3.
Proof of Lemma 3. Recall that Px(p) = 1 (5 (p) + (2)))B(()) Since Dz, LD D Dann + 26D jou and D ynn (x. v) = Σi=1 Dan (xz, yi) and Daue (x, y) = -E DaLe (2 vi), we can bound the stability term
(0: 11+1, Tea) Do, (1++1, S (ge 91+1 ke) - max {
- Depe (1++1, (t), 26 26Drar (ge+1, 0t)
1/2
Brllati (0+1,)) - max {LD
Dans
ans (90+1,5 1, gti), 26D aen (1c+ 1..b
1/
Usstti }
min qu & (n...) 28
(23)
7)
28
1=1
where in the last inequality used (21) and (22) with
Dt
1
28
2ôp
25(
y
where the first inequality follows by the definition of and the second inequality follows by Pu 2 /5. Next, we will prove that for any i E [k].
min {
qua (n.Ta)) 28
25 MunDis }}
1
8n Pei
CN min
Pti 2n:
1[4,
+).
(24)
17
Fix i [k). By ge S 8pt.
1
1
28 Ucelia
P S
Using this and ((x) s x² for E
[-2, 21 in (20), we have for any Pts [0, 1] that
1
28
28 QriTes
< 28
La I[A 2
= i),
(25)
25
where in the last inequality we used < ōpti. In particular, when Pts S i.e., the probability of selecting arm i small to some extent, the last inequality can be further bounded as
25 C
28 AtsDes
S
Tc 5
14: = < 8m
G
1 -A
(26)
Pti
On the other hand when Pis mes have neru 2 -1 Hence, by the inequality {(x) < x² for r 2 -1 in (19),
1
S - 5ps (veDue) Efp. Pti Hence, combining (25), (26), and (27) completes the proof of (24). Finally, by combining (23) and (24) we completes the proof of Lemma 3.
que (11T)s))
1[A = i].
(27)
T)
D
21

---

Remark. When le can be negative, the Shannon entropy regularizer alone cannot bound the stability term if the arm selection probability is small, i.e., Pt: S ?t. Introducing a time-invariant log-barrier regularizer enables us to bound the stability term even when the arm selection probability is small, This idea was proposed by Bubeck et al. [10], who analyzed the variation of arm selection probability for the change of cumulative losses. Unlike their analysis, our proof directly analyses the stability term, enabling us to obtain the tighter regret bound. More importantly, we will utilize the property It S O(1/n)) many times, which directly follows from Lemma 3, in the subsequent sections to prove the BOBW guarantee with the sparsity depeedett bound.
Now, we are ready to prove Corollary 3.
Proof of Corollary 3. Fix 1 E [k.. Define p" E PE by
p²
T
ex
+
7 1.
Then, using the definition of the algorithm,
T
T
Reg (i*) = I
le -
Σ
E
= E
(4e: Pt - ex,)
t=1
E
(Ee, Pt - -p")
+ +
Σ
'l.pp' - -cc.)
K E
(ūe. Pt - p²) +k,
where the inequality follows from the definition of p" and the standard analysis of the FTRL, described in Section 3,
inequality. By the
Po p²)
(p((p=1) & 8e41 (PEti) + Pe+i((") (p() -
(e pc- 1,) Da, (P)+).)))).
For the penalty term, since (p(p) = ni (p)) + (p),
4 (p(+1)) (141(Pe41) + (0+1(0") - (p1)
1) H((++1) +
H(1))
1
+
log
1/++1
T1e)
m1
D
t=1
T
1
H((L+1)+ + log k
+ 2k log
M1+1
Ttc
m
1=1
where in the last inequality we used the fact that p; 2 1/T for all i E [k]. For the stability term, by Lemma with 5- (since pt q:)
T
Σ((r - Pc+ 1, Tn) - Do, (p(41,P))
The
t=1
We will confirm that the assumptions for Part (II) of Theorem are indeed satisfied. By the definition of the learning rate in (7),
CiV
Va
= +
2 B1++ +
Σ s=1
1 Va
2==1
+
V
Eu-t
81 +
Σ v/
V8
31 +
C1
Σ 1/a
h1
u=l
#=1
#=1
#=1
22

---

Using this inequality, St is bounded from below as
t-1 l
i-
2/ = 3 3 20 + B1
+
C1 vhi
Σ
2, +
Us
a vhi
Us
G
Σ
Us
hr
where the first inequality follows by v S B./2 and the above inequality, the second inequality follows by the AM-GM inequality, and the last inequality follows from 2/23 2 vAr
dt and v + v 2
y + y for x, y 2 0. Dividing the both sides by 2, we can see stability condition (S2) Theorem is satisfied with 1/2. One can also see that the other assumptions are trivially satisfied. Hence, by Part (II of Theorem 1,
T Σ
T Σ nove 2
T
1 ne
2)
((p(11) +
a
h1
Σ
Vt.
M++1
Using the last inequality with E
V
VE
SE
V We
S V22 and setting 22, we
have
T
log k
Reg (i') S B
61 4
hn
Σ
ut
+
2 log T
171
1=1
1
I <4v2 La log k + 2k log T + k
+
which completes the proof of Corollary 3.
H Proof of results in Section 5.2
Appendix H.1 provides preliminary results, which will be used to quantify the difference between and q-+1 in Appendix H.2 and will be used to prove the continuity of F3 in Appendix H.3. Appendix H.2 proves Theorem 4 and Appendix H.3 discusses the bisection method to compute 8441-
H.1 Some stability results
Before proving Theorem 4, we prove several important lemmas. Consider the following three optimization problems:
p E arg min (L Ec1.p') + Bp((')) p'EP,
g E arg min (7, + Bib(g'), y'EP,
(28)
r E arg min (L, + ('26(r") (r') reP.
with L E R4, 0. S min.e(k) L, and B, 8 > satisfying G' 2 B.
4:
(1()) Σ (qs log 4:)
log q and v'(4) Σ (g: log q: - -::)
log q
B
3
for c O. Note that the outputs of FTRL with (²) and with - H)())) - (c/3) Ex_ log qi are
identical since adding constant to s does not change the output of the above optimization problems.
In the following lemma, we investigate the relation between & and in (28).
Lemma 4. Consider q and in (28). Then,
9/8'
Ti gi
(29)
23

---

Proof. From the KKT conditions there exist μ. p² E R such that
L B+ + p1 = and L+ L+ =0
which implies, by (Vi(());; log 9: Dq.
that
L Blog qi
p and
1/ L + Blog ri
+ p
(30)
ri
for all E [k]. This is equivalent
(-. 4i
(
1 L:
and = exp (-1)
1
(
c
n² )
q: exp
Li
Br
Removing L; from these equalities yields that
3/8' exp
c (1 Ti
qi ))) exp ( (u (p m1)
1
Ti
9i
(31)
We will prove du 3B 0. Taking derivative with respect to 3 of (30), we have
(=
dg.
du
log qi
0.
9
d3
d3
Multiplying
1 +
and summing over E [k] in the last equality, we have
-(1+
1
log log(1/g)) + dg 1 + d.
du d3
0,
Ci
d.
which with the fact Σ
dg dæ
implies
de > 0. Hence, since 3 s 3 we have S wl d3
1=
8/3"
When Ti gs it is obvious that we get < %i
When r2 qi using (31) with the inequalities 3 8r and μ S k²,
3/6
(1_ - )) exp
(1-1)
3 (u (up'))) p2)) S 9, 818
exp
B
which is the desired bound.
Lemma 5. Consider q, and r in (28). Then, under == 1/B < I5 we have
8/3'
ri 3p:
(32)
Proof. By Lemma 8 of Bubeck et al. [10] we have S 3p, for all i E [k]. Using this with Lemma 4,
we have
3/8"
3/8'
S 9: I 39
H.2 Proof Theorem
In this section, will provide the proof of Theorem 4. We first that the ratio Be/Bet1 is close to one to some extent.
Lemma 6. The learning rate Br in (8) satisfies
9
E 10,0/10)
8
24

---

Proof. Recall that =
31 + Eu=1 bu with by =
citu Un
and U, = Vo + 2 + E'=1
zohas1 for
t [0] u [T]. It suffices show
3
Be 2 9b:
3++1
33 + bt
10
This indeed follows since using V 5 3 we have
4142
C144
3
b
V 8lcf + E.-l zalio + 21te111
/8lef
9
9
Finally, we are ready to prove one of the key lemmas for proving the BOBW regret bound with the sparsit--dependen bound. Recall that we have pt = (1 +) qt + 7 and h2 = 1- (pt). Using the result in Appendix H.I, we will show that h441 is bounded in terms of ht- Lemma 7. Suppose that Br is defined as (8). Then,
20k
[s+1
T k
h
3h, + 9
log
hi+1-
3r
Proof. Let us recall that qe and q1+1 are defined as
Σ No. a / (c))
qt E arg min
Σ Ta. q (.(4) and 1641 E mig
gEPa
9EPx
which corresponds to optimization problems (28) with qr L = E. Do. 5 Tea, v = $1/Be. ? = 1/B,, r qt+1, v/ #1+1/3t+1 and r/ 1/Br+1-
Since H is concave, by pri = =(1- $ )qr and Jensen's inequality have
[ (1- tr = (pt)) 2 1
k T H H(a)
k T +
h (
H
1
T
8/19 which implies that
which implies h4 H(q)). By Lemma 5 we also have 9t+1; I
34t
PIL1 = (1 (1-T) ati1 + ] $ 1
k
Bc/9e+1
1
9.18
34
6p
T
T
The last inequality follows since when (1-
4) 34
Be/Bet1
< T
(1 1
(1-T)
k: T
3/h
8.18c11
S
2
Be/0441
22
((1
1
k:
qii + T
De/Bet1
22
8/8L-1
T
T
and otherwise
De/Bees
k (1-7)
Be/Bet1
1
k 1-
B./Brt1 < 6yd
3/Det2
T
30
T
<
6
T
4ri
Using these inequalities, we have
h++1 3/,
(H(p++1)- - -3H(p:))
<
(H((p: + (VH(p:)) Pt+1 - Pt) - -3H(p))
1
(pt-1.5 - 3pc) log
Pts
i=1
1
(g+41, - 3qt) log
(33)
Pti
25

---

where the first inequality follows by the concavity of H, the second inequality follows since P++1,;
3ps I (1 )) (q++1, qta)- Defining 9₂ {i E [k]] q1+1,1 3qs, 2 0}, (33) is further bounded
as
k
(9++,4 3q.)) log
Σ
(9++15- - 3qn) log
+
Σ
(qt+1,+ 3qus) log
Pei
iE
Be+1
1
(gt+1,1 3qts) log
0
Bt
P1+1,3
ic0;
<
(lt+1, -3ges) log
9
Pe+1,i
16
10
B412/11 log
1
qu+1, 9c+1,e
Pet1,1/
10
a+1, 11 1 9sti,
Pepi -1
1
log
(34)
9
PL+1,
iEQ.
9//Be+1 the second follows by Lemma 6, and the last where the first inequality follows by Pi+1, S. 6p,
8./8.11 Since for any & > 0, x E [0, 1]. and E [0, 1]. holds that
inequality follows by gt+1, S 3dts
ex log 1
x(1 11-x)) x5) S log
xx
log - 7 -1) 1) (or r) + 7 log |
e log ( ( (1 (1- (35)
S8
setting y k/T in (35) implies that the RHS of (34) is further bounded as
h++1 - 3ht
10
Σ
Be+1
-1)
log(T/h)
(
k
+
(1 1
A T
4++1,
log
Be
Pe+1,8
IEQ,
10k
3e+1
(1
k
1
3r
-1
log(T/k)
Σ
T
9e+1.
log
P1+1.
20k
Be+1
-1) 1)
log(T/k)/e44,
3r
where the second inequality follows by Lemma 6 and the last inequality follows by the definition of he+1.
Finally we are ready to prove Theorem
Proof of Theorem 4. Fix i" [k] and define pa E Ps by
p² = (1
+ T
1.
T
26

---

Then, using the definition of the algorithm,
T
T
Reg7 (1*)
= E
Σ
lii
E
(e, Pt cxr)
t=1
t1 1 41) )
1
E
(lt, 9t -ct-)
+ EE
k
1=1
S E
Σ (lt; 9t - -p")
+ R
Σ
(le, p" - -Bst)
< E
Σ (Te, Qt - -p")
+ 2k,
where the first inequality follows since p. = -1-7)q + ]1 and the last inequality follows by the definition of p" and 4. By the standard analysis of the FTRL described in Section 3,
(ec. q: p²) s _ Po(((41) (0+1()+1) + (p=) (1))
T
(90 94+1, Di) Do (9+1. Σ
+
1=1
We first consider the penalty term. Since D, = 1 gins + 420LB.
((((++))
2 (141(9941) + (c+1(p")
(q1)
T
1
H(11)
h
1
H (( +
+ +4)
log
17++1
7t
711
[=1
1=1
T
1
1
log k
H(g(+1)+
+ 4k log
M
7e
1
[=1
where in the last inequality we used the fact that p. 1/T for all E [k]. For the stability term, by Lemma with 2,
Σ (at (+11.0)) Do. Do.(9.11.91)
2 Σ mer.
We will confirm that the assumptions for Part (l) of Theorem 1 are indeed satisfied. By the definition of the learning rate in (8) and V4 I B,/2.
V (31 B.)+
2 9B1 m)) 2 B1 i..
C1
Hence stability condition (S1) of Theorem is satisfied and one can also see that the other assumptions trivially satisfied. Hence, by Part (I) of Theorem
T
1 Tt
2
Ue
+2
ney 2
Ci +
log
1+
C2
+
Mh+1
C1
3
2
1.2
T41
<
c1
+
log
1+
C2 +
vih+11
C1
31
I=1
1+ T2
T+1
-21 2oo
C2
veh441,
31
27

---

where in the last inequality we used in S and in the equality we set 01 = 2 (1+ (1))))
By summing the above arguments and Jensen's 's inequality, we have
T
T+1
+ 2k + 4k: log T log k
Reg7 (i*) $ E
2
2 log
+
vib++1
B1
7/1
T
T++
$ 2 2V
2 2og
+
C2
+
E
vehe+1
+ 2k 4k log + 15k logk
31
T
T
$ 2
2 2og
1
E
wh++1
+ OkklogT)
(36)
31
Adversarial regime
We first consider the adversarial regime. Recall that E v E us
V / I L2 was done in the proof of Corollary 3. Hence (36) with he log k (since
TT'
T 2 2k) yields that
T B1
Regr I < Lz log()) log
1
- O(k log 7)
Adversarial regime with self-bounding constraint
Next we consider the adversarial regime with
a self- ooff-bounding constraint. We will bound component of (36). By Lemma 7, / - velee1
is bounded as
E
vehu+1
20k
T
Be+1 1 hot1
3 E
+
log
E
k
-=1
10k
T
3 E
14
+
log
E
(Be+1 -Be het1
k
T
10k
T
3 E
+
log
E
9
To
C2 + Σt Vollotl
A=
T
20h
T
3 E
vg
log
E
Σ
vghet1
1:
20k
T X₂,
3 E
v
+
log
F
where the first incquality follows by Lemma 7, the second inequality follows by S 8,/2, the last inequality follows by Lemma 8. Since Va + bæ for immlies < 2 b.
T
T
20k +
T T
20k
T
X, < 2,
3E
Σ
h
log
2,
3
3
El |pe]/e
+
log
9
k
1=1
1=1
28

---

Algorithm 2: BOBW algorithm with a sparsity-dependen bound in Section 5.2
for 1, 1,2....,7o
Compute 4t using (1).
Sample A, Pt. observe LAA, E [-1, 1], and compute Tr- Update 3t using (8) based on the bisection method (Algorithm 3).
Algorithm 3: Bisection method for computing (+++
input: F;
2 left <- (r, right +- 3, + T
while true do
center + (left + right)/2 if (ceenter)) 0 then left + center else if (ecentr))) > 0 then
right +- center
else
10
break
11 return center
20k
T
s 2 6s E
(pr)
+
log
(37)
9
k
where we used E[ve ho] S E| Peo (CPp/P)) = EE 40 Pto Pr(lss/pssl S s.
We consider the case of P(a*) 2 e, since otherwise Lemma 2 implies Σ Hp:)) S elog(kT)) and thus the desired bound is trivially obtained. When P(a") 2 e, Lemma 2 implies that Σ H (p:) S P(a") log(kT). Then from the self-bounding technique, for any À (0, 1] it holds that
Regr (1 + R)gg XReg
< E (1 + OY/ (Vs log (og(T))(a)) AAmin + AC + O(klog
(1 +1+ 8) log(T))og((k)))) + XC
0
A
sTog(T) log(kT)
log(T) log( (T))
1 s log(T) log
(og(()) (kT)
=0
+ +C
+
Amin
Amin
Amin
where the first inequality follows by Lemma and the second inequality follows from a/2 - bx/2 S a² (2/(22) for a, b, 2 0. Setting E 10 to
s log(T) log(T))) / 8 (og(()) log(kT) Amin
(
=c)
Amia
gives the desired regret bound for the adversarial regime with a self-bounding constraint.
Stochastic regime Using Elv, hv] < E[ur Av] < P = = Q in the
second inequality of (37) and following the same arguments as analysis for the adversarial regime with self-bounding constraint, can obtain the regret bound for the stochastic regime.
D
29

---

H.3 Discussion on bisection method for computing B++1
This section describes the bisection method to compute 3441 described Section 5.2. Recall that Fe [8c, Be T) - R is defined by the difference of the both sides of the update rule of (8)) in (8):
C1V2
F((a) = Br
(38)
02 + v(hu+ila) + E.sl Voho-1
where h(+1(a) = 1-4 H(p++((a)), and pa+1(a) is the FTRL output with the regularizer + =
ay:s + 4.BLB Note that cu44/ Vez vnhe+ila) E Ugha+1 S c////22 S T/9 since Vs T.
Assume that F; is continuous. Then we can see that there exists a E [3,, +T] such that Ff(a) 0. In fact, if PtA. 0 then B++1 Be, and otherwise, have F((B,) I 0 and Fr + T) > 0. Using the intermediate value theorem with the assumption that F; is continuous, there indeed exists [8,, Be T] satisfying Fi (:(a)) O. We can compute such the bisection method. In particular, we first set the range a to [3,, 3g + 7], and then iteratively halve it by evaluating the value of F; at the middle point. Such bisection method (binary search) is also used in [50], although the computed target is different. The whole BOBW algorithm with the sparsity-dependent bound in Section 5.2 is given in Algorithm 2, and the concrete procedure of the bisection given in Algorithm 3.
Now, all that remains is to show that Fg is continuous. To prove this, it suffices to prove that h++1(a (a) T- - H (a)) is continuous with respect
Proposition F. (38) is continuous with respect to a.
Proof of Proposition 2. Take any a E [3c. 3r + 7] and then consider the following optimization problem:
(++1 (a) = arg min gEd.s
Σ D.. + +e+1
where 1,+1 antn + 4 Now using Corollary 8.1 of Hogan [20] with the fact that the solution of the above optimization problem unique, (a+)(a) is continuous with respect to a. This completes the proof since P++1 is continuous with respect to g++1, 1/T S Pt+1,s(o) I k/T, and H(p) is continuous neighborhood of = (a).
I Proof of Corollary 6
This section proves Corollary 6, which is the extended result of Corollary 5. Recall that B = 1/2 for FI, B k/2 for MAB, and B 2mk for PM-local, and r'M if M FI MAB, and 2k M PM-local, which are appeared in Appendix B. Let Regy (a) = ΣT (C - -aaz,) =
E E
(LA. Las ) for E [k].
Proof. Fix 8 E [k]. From Lemma 7 in Tsuchiya et al. [46], if n, > 0, we have
T
1) Th.
H(q+1) + H(g))
T
Regr (i*) <
E
Σ
m Σ
V.V!
(39)
M
We will confirm that the assumptions for Part (I) of Theorem are indeed satisfied. Since
V02 + 2,h,
2V log k log(1 + T")
log(1 + T) 2 V2 + +V,)
(8. +3) 2
2B
C1
log
30

---

stability condition (S1) is satisfied. One can also see that the other conditions are trivially satisfied. Hence, using Part of Theorem 1, we can bound the RHS of (39)
1
I
H(g))
Regr (i*) S IE
201 + log C1
1
VH(
Σ Vi
th
+0 +0 (V log(T) + B B (ogg(k))))))) log T
$
2c1 +
log (1 +
E
v(H(()+1))
2lg + TT),
E
(4H(4)))))
+0 B
BBylog log log(h))og(T)))
(40)
where the second inequality follows from V S 1 and in the equality we set v log(1+7)
and
used VV B.
Adversarial regime
For the adversarial regime, since (gt) I logk, (40) immediately implies
T
Vi (k) log(1 + +T) + O OBBlogg( log(T))
Regr S
E
which is the desired bound.
Adversarial regime with a self-bounding constraint Next, we consider the adversarial regime with a self-bounding constraint. We consider the case of Q(a") 2 e, since otherwise Lemma implies ΣT= (p:) S (kT)(kT) and thus the desired bound trivially obtained. When Q(a") 2 c, Lemma 2 implies that Et=1 ((g) S Q(a") log(k("). Then from the self-bounding technique, for any x (0, 1]
Regr = (1 + R)RegT - -ARegr
< E (1 + AYO (V
Ammia((a))
+ +CC
TM
V log (og( log()))(())
Aa minn Q(a*)
< (1 + OYY
AC
FM
(1 + RM
FM (T) lkg(
<0
AC
AAmin
TMV log(T) log(kT)
TMV log(T) log((T)))))) (KT) +c)
1 TM log(k))
=0
Amin
Amin
Amin
where the first inequality follows by (40) and Lemma with d' = and the second inequality follows from a/z bar/2 S a² (22b) for a, b, x 2 Setting X E (0, 1] to
FM V
/rmm (MMM log(T))og +C)
Amin
Amin
gives the desired bound for the adversarial regime with a self-bounding constraint.
J Basic lemma
Lemma 8 ([38, Lemma 4.131). Let 0g 2 0, (a.)T_ be non-negative reals and R4 - R2 be non-increasing function. Then,
T
Σr at
Σ
azf
ag
+
Σ
as
f(x)dx.
s=1
ag
31

---

We include the proof for the completeness.
Proof. Let A, = E.- Uz. Then summing the following inequality over completes the proof:
An A. [(Ae)dx s Sa A
ar a0 Σ
=aI((A))=
f(x)dx.
J
K Comparison of the sparsity-dependen bound and the first-order bound for negative losses
If 4 E [0, 1] the first-order bound by Wei and Luo [49] implies sparsity bounds. This, however, does not hold when & E [-1, 1]s. In fact, let consider the case where & is zero vector except that only
arm's 's loss is 1 for some t [T]. Then the dependent bound becomes O(VT). On the other hand, the first-order bound in [49] is not directly applicable, and we need to transform losses to range (0, 1]. This implies that the first-order bound becomes O(VKT), which worse than the sparsity-dependen bound.
32


Reviews:
[{"review_id": "oCZhGkSugC", "reviewer": "Reviewer_TasV", "summary": "This work considers the Follow-the-regularized-leader paradigm for multi-arm bandit and partial monitoring problems. It proposes a new framework for designing FTRL algorithms with a time-dependent learning rate to generate algorithms that is adaptive to the sparsity of the feedback, to the setting being stochastic/adversarial/adversarial with self-bounding constraints, and to the game difficulty of a PM problem.\nSpecifically, it proposes to choose the learning rate $\\eta_t$ based on the penalty term (changes in the objective function due to the change of the time-dependent regularizer) and the stability term (a measure of progress) observed in previous iterations.", "questions": "The algorithm analyzed in Section 5.2 achieves BOBW and adaptivity to sparsity in the adversarial setting. Is it possible to also have a notion of sparsity in the stochastic setting?", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The overall idea of this paper has many implications in different settings: for example, in Section 5.1, it generates algorithms with near-optimal guarantees in the setting of adversarial bandits with sparse feedback with/without restrictions on the signs of the feedback; in Section 5.2 it leads to an algorithm that is adaptive to the sparsity and to the adversarial-ness.", "weaknesses": "While all the notations used in this paper are defined before being used, it would be great if some context/discussion can be provided before diving into the statements and analyses. For example, what is the intuitive way to see that $opt\\prime_{q_t}(\\eta_t)$ captures the game difficulty? It would also be nice to explicitly describe how the learning rate is used in the FTRL updates.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and insightful suggestions.\n\n> While all the notations used in this paper are defined before being used, it would be great if some context/discussion can be provided before diving into the statements and analyses. For example, what is the intuitive way to see that $\\mathrm{opt}'_{q_t}(\\eta_t)$ captures the game difficulty?\n\nThank you for the suggestion.\nIn the revised version, we will include more intuitive explanations.\n\nThe intuitive interpretation of how $\\mathrm{opt}'_{q_t}(\\eta_t)$ captures game difficulty is as follows:\n\nIn partial monitoring (and many other sequential decision problems), it is necessary to exploit the information currently available, while at the same time constructing a loss estimator that appropriately balances its bias and variance.\nIf we can construct such an algorithm, then the algorithm can achieve a better regret.\n\nThe first, second, and third terms of $\\mathsf{ST}(p,G)$, the objective function that determines $\\mathrm{opt}'(\\eta_t)$,\ncorrespond to the degree of the exploitation, bias, and variance terms, respectively.\nTherefore, the smaller $\\mathsf{ST}(p,G)$ can become by optimizing $p$ and $G$, the smaller the regret can become, and thus $\\mathrm{opt}'_{q_t}(\\eta_t)$ captures the game difficulty.\n\nWe will include this discussion in the revised version.\n\n\n> It would also be nice to explicitly describe how the learning rate is used in the FTRL updates.\n\nThank you for the suggestion.\nAs defined in Eq. (4), $\\eta_t$ is defined as $\\eta_t = 1/\\beta_t$, and this $\\eta_t$ is used to define the regularizer $\\Phi_t$ for FTRL.\nIn the revised version, we recall these definitions again when defining $\\beta_t$ (in Eqs. (6), (7), (8)).\n\n> The algorithm analyzed in Section 5.2 achieves BOBW and adaptivity to sparsity in the adversarial setting. Is it possible to also have a notion of sparsity in the stochastic setting?\n\nThank you for the insightful suggestion.\nWe only considered exploiting sparsity in the adversarial setting and did not in the stochastic setting.\n\nExploiting the sparsity in the stochastic setting can be accomplished with a very minor modification of the analysis.\nIn the equation below Line 766, we use $\\mathbb{E}[\\nu_t | h_t] \\leq k$ without considering the sparsity of losses, but instead we can just use $\\mathbb{E}[\\nu_t | h_t] \\leq s$.\nThis indeed holds since \n$ \\mathbb{E}[\\nu_t | h_t] \\leq \\sum_{i \\in [k]} p_{ti} (\\ell_{ti}^2 / p_{ti}) = \\sum_{i \\in [k] \\colon \\ell_{ti} \\neq 0} p_{ti}  (\\ell_{ti}^2 / p_{ti}) \\leq s$.\nThis allows us to obtain a regret upper bound of $O( s \\log (T) \\log (kT) / \\Delta_{\\min})$ instead of $O( k \\log (T) \\log (kT) / \\Delta_{\\min})$ in the stochastic setting.\n\nThe authors found that Kwon et al. (2017) provides an example of how to utilize sparsity in the stochastic setting of MAB, but they define $s$ as the number of arms with rewards smaller than or equal to 0 (i.e., loss larger than 0), and hence the definition of sparsity is different from $s$ in our paper.\n\nThe revised version will include this result with appropriate citations to references such as Kwon et al. (2017).\n\n(Kwon et al. 2017) Sparse Stochastic Bandits, COLT2017\n"}, {"review_id": "x9DxPRTNZy", "reviewer": "Reviewer_x1zD", "summary": "This paper studies the Follow-the-Regularized-Leader (FTRL) framework for bandit problems. It proposes a learning rate dependent on both stability and penalty terms, which is inspired by the analysis. The proposal is helpful to achieve sparisty, game-dependent and Best of both worlds regret for bandit problems under stochastic and adversarial environments.\n", "questions": "- What would we lose if the learning rate only depends on stability **or** penalty, e.g. the sparsity or gama-denpendent property or BOBW property? It would be better to illustrate as remark for comparison.", "limitations": "No limitations are discussed in the paper.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed learning rate can be used to design algorithms that achieve sparsity-dependent and BOBW for Multi-arm bandit problem, and game-dependent and BOBW in partial monitoring problem.\n- The proposed learning rate might be of independent interest for other online learning problems.\n- The preliminaries are well-introduced to average readers.\n", "weaknesses": "- It would be better to provide comparison on regret bounds with $\\Delta_{\\min}$ and $L_2$ with previous results (some of them don't have these parameters) in Table 1.\n- There are too many in-line equations, which might hurt presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and helpful suggestions.\n\n> It would be better to provide comparison on regret bounds with $\\Delta_{\\min}$ and $L_2$ with previous results (some of them don't have these parameters) in Table 1.\n\nThank you for the suggestion for improving Table 1.\nWe 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 perspective you expect the comparison to take.\n\n> There are too many in-line equations, which might hurt presentation.\n\nDue to space limitations, in-line equations are present to some extent.\nHowever, in-line equations with equation transformations are presented only around Line 327, and the authors believe that the rest of them are considered acceptable.\nIn the revised version, we will reduce the number of in-line equations as much as possible.\n\n> What would we lose if the learning rate only depends on stability or penalty, e.g. the sparsity or gama-denpendent property or BOBW property? It would be better to illustrate as remark for comparison.\n\nThank you for the suggestion.\n\nSection 5 (multi-armed bandits, Theorem 2):  \nIf the learning rate depends only on stability, then the BOBW guarantee is not obtained, \nand if the learning rate depends only on penalty, then the sparsity-dependent bound is not obtained (i.e., the upper bound of the adversarial regime becomes $O(\\sqrt{kT \\log k})$ instead of $O(\\sqrt{sT \\log k})$).\n\nSection 6 (Partial monitoring, Corollary 4):  \nIf the learning rate depends only on stability, then the BOBW guarantee is not obtained, and if the learning rate depends only on penalty, then the game-dependent bound is not obtained.\n\nIn the revised version, we will include this discussion."}, {"review_id": "Qw39tozl2x", "reviewer": "Reviewer_WVsf", "summary": "This paper studies how to achieve BOBW regret bounds in sequential decision making problems such multi-armed bandits and partial monitoring games. To this end, this paper comes up with novel SPA learning rates for FTRL. For MAB, this paper shows FTRL with SPA could simultaneously be near-optimal for stochastic and adaptively adversarial sparse MAB, and is agnostic to the sparsity level. For PM, this paper shows it could achieve a regret bound that is both game-dependent and BOBW, and is better than previous results.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In addition to the contribution mentioned in summary: \n1. The SPA learning rate has an interesting form that may be of interest to the community and might have broader applications. ", "weaknesses": "1. The improvement upon the previous literature seems not big enough. The main improvement for sparse MAB seems to be removing the sparsity requirement. It is possible I underestimate the hardness of learning sparsity requirement, but since here we only need a multiplicative approximation of the sparsity, may I request the authors to explain why simple ideas such as using successive halving to guess the sparsity level wouldn't work here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your time and for providing a possible alternative procedure for exploiting sparsity in the adversarial regime.\n\n\n> The improvement upon the previous literature seems not big enough. The main improvement for sparse MAB seems to be removing the sparsity requirement. It is possible I underestimate the hardness of learning sparsity requirement, but since here we only need a multiplicative approximation of the sparsity, may I request the authors to explain why simple ideas such as using successive halving to guess the sparsity level wouldn't work here?\n\n\nFirst of all, the improvement for sparse MAB is not the main contribution of our paper, but only a preparation for Section 5.2, in which we tackle one of our goals to obtain the BOBW guarantee with a sparsity-dependent bound.\nWe will emphasize this more in the revised version.\n\nIn addition, while improvements in the sparse MAB setting are not a major contribution, we still believe that a successive halving approach would not yield favorable results.\n\nWe will assume that successive halving means either\n\n(Approach 1) A procedure that keeps a set containing the sparsity level $s$ and updates its range gradually based on past observations\n\nor \n\n(Approach 2) A procedure based on a method like a hyperparameter tuning that tries several sparsity level $s$ candidates simultaneously and keeps the one with the best result.\n\nWe would appreciate it if the reviewer could tell us if these approaches are not what the reviewer expects.\n\nIssues common to both approaches are as follows:\n\nFirst of all, it is not possible to get a reliable sparsity level $s$ at the halfway point in the adversarial setting, because parameters that are favorable up to the halfway round are not necessarily favorable for the whole round.\n\nSecondly, and importantly, the $L_2$-dependent regret upper bound is stronger than the sparsity level $s$-dependent upper bound.\nIn general, $L_2 \\leq s T $ holds. Hence, even if we can construct an algorithm that achieves an upper bound of $O(\\sqrt{sT \\log k} )$ by the above approaches, the regret upper bound of $O(\\sqrt{L_2 \\log k })$ in our paper is favorable.\nIntuitively, the $L_2$-dependent regret upper bound handles well not only the situation where the loss is sparse in all rounds but also the situation where the loss is sparse when averaged over the entire round.\nTo achieve an $L_2$-dependent regret upper bound, we need to cope with the situation where sparsity changes from round to round, which is difficult to do by successive halving.\n\nFinally, it is important to note that even if sparsity can be estimated using the above approaches, it would be significantly difficult to obtain a best-of-both-worlds guarantee simultaneously. \n\nThe following is an issue and why such successive halving approaches would be difficult to analyze, although they are not as important as the issues mentioned above.\n\nIssues with Approach 1:\nIn the literature, the basic strategy for constructing an algorithm that works adaptively to unknown parameters is to use an adaptive learning rate. On the other hand, doing exploration and exploitation in an adversarial setting while estimating sparsity level $s$ by Approach 1 is likely to make the algorithm and its analysis very complicated.\n\nIssues with Approach 2:\nIf based on Approach 2, several bandit algorithms must be run in parallel, but in general, bandit algorithms cannot run in parallel, so it is necessary to split the rounds into blocks, etc.\nHence the authors expect the design and analysis of such algorithms to become highly non-trivial.\n"}, {"review_id": "KyNvvXdUUe", "reviewer": "Reviewer_1eun", "summary": "This paper proposes a new scheme called SPA to configure adaptive learning rates for FTRL in MAB. Developed from a stability-&penalty-dependent generic regret bound for FTRL, SPA is designed to select learning rates to optimize the bound. SPA is then applied to three scenarios with different types of adaptivity, including sparsity, game-dependency, and BOBW. In particular, SPA eschews the need of knowing the sparsity level in advance as in previous methods, and is shown to achieve a near-optimal regret bound in both stochastic and adversarial settings. Finally, the proposed method is applied to partial monitoring, which achieves a game-dependent bound and BOBW property simultaneously.", "questions": "See the \"weaknesses\".", "limitations": "Limitations have been properly discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Adaptivity of FTRL is an interesting and important problem. The proposed adaptive methods may improve the applicability of FTRL in real-world scenarios.\n\n2. This paper is technically sound with solid theoretical results.\n\n3. This paper is well written in general and easy to follow.", "weaknesses": "1. The design of SPA is rather straightforward, which seems a direct consequence of existing generic regret bound for FTRL. This somehow limits the novelty of the proposed method (though the subsequent extensions to scenarios with various forms of adaptivity are interesting and non-trivial).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and for carefully reading our paper.\n\n> The design of SPA is rather straightforward, which seems a direct consequence of existing generic regret bound for FTRL. This somehow limits the novelty of the proposed method (though the subsequent extensions to scenarios with various forms of adaptivity are interesting and non-trivial).\n\nWe believe that the idea of a learning rate adaptive to both stability and penalty itself is novel, and its analysis (Theorem 1) involves non-triviality because we need to simultaneously bound the penalty term and stability term.\n\nFurthermore, Theorem 1 and its proof are presented in a simple manner by assuming the stability condition (S1) so that the theorem can be used for both multi-armed bandits and partial monitoring, and in order for the stability condition (S1), it is necessary to make use of time-invariant log-barrier (as described in Remark under Lemma 3), which is non-trivial.\n\nMoreover, Theorem 1 does not immediately lead to Theorem 2 due to the correlation between $\\nu_t$ and $h_{t+1}$ as mentioned in \"Key elements of the proof\" on page 9.\nTo address this, we need to analyze the behavior of arm selection probabilities when the regularizer changes (discussed on page 9 and proven in Appendix H), which is highly non-trivial. We will clarify this more in the revision."}, {"review_id": "QTJhUrqMRg", "reviewer": "Reviewer_Utqx", "summary": "The paper studies the problem of designing no-regret algorithm with three types of adaptivity to the setting: sparsity, game-dependency, and Best-of-Both-Worlds. To do so, the authors propose a new adaptive learning rate, called Stability-Penalty-Adaptive learning rate for Follow the regularized leader. They provide the first $s$-agnostic regret bound in the adversarial regime, where $s$ is the sparsity of the rewards. Moreover, they design the first Best-of-Both-Worlds algorithm with a sparsity-dependent regret bound. Finally, they extend the analysis to partial monitoring.\n", "questions": ".", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper provides new improved regret bounds for different settings. The paper provides a clear comparison with previous work. The proofs of the theoretical results are not straightforward.", "weaknesses": "The paper presents many different results and hence it is hard to follow the paper in some points.\n\nThe analysis of the partial monitoring setting is relegated to the last half page. This makes impossible to have an insight on the results from the main paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and for providing valuable suggestions. \n\n> The paper presents many different results and hence it is hard to follow the paper in some points.\n\nIndeed, multi-armed bandits and partial monitoring are very different, and the results obtained with each problem setting are largely different.\nHowever, we decided to combine them in one paper because both of their improvements are based on the stability-penalty-adaptive learning rate.\n\n> The analysis of the partial monitoring setting is relegated to the last half page. This makes impossible to have an insight on the results from the main paper.\n\nDue to the space constraint, only the main result (Corollary 3) could be included in the main text for the contribution in partial monitoring.\nNevertheless, we believe that the differences between the main result and existing results are sufficiently described in the main text through the Section 1, Table 1, and Section 6.\nFurthermore, Section 6 is described as an example to illustrate the wide applicability of the stability-penalty-adaptive learning rate, and the authors believe that the contributions up to Section 5 alone are considered to be sufficiently nontrivial."}]

Author rebuttal:

Meta-review: In this paper, the authors investigate Follow the-Regularized-Leader (FTRL) for bandits. The primary contribution is the introduction of a Stability-Penalty-Adaptive (SPA) learning rate for FTRL, leading to a regret bound that jointly depends on the stability and penalty of the algorithm. Following this, the authors develop several algorithms characterized by three types of adaptivity: sparsity, game-dependency, and Best-of-Both-Worlds (BOBW).

Specifically, they first establish a regret bound that is dependent on sparsity but without requiring prior knowledge of the sparsity level. Next, they introduce a BOBW algorithm, achieving a near-optimal regret bound in both stochastic and adversarial settings. Lastly, they demonstrate a BOBW guarantee paired with a game-dependent bound for partial monitoring. In summary, this paper offers substantive contributions to the ongoing research in the fields of FTRL and bandits, advancing our understanding in several aspects.
Decision: Accept (poster)