Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
Authors: Federico Di Gennaro
Khaled Eldowa
Nicolò Cesa-Bianchi
Venue: NeurIPS 2025 poster ()
Keywords: Partial monitoring
exploration-by-optimization
linear bandits
online learning
Primary area: theory

Abstract: In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing a linear structure on both the losses and the observations. This setting can be viewed as a generalization of linear bandits where loss and feedback are decoupled in a flexible manner. In this work, we address a nonstochastic (adversarial), finite-actions version of the problem through a simple instance of the exploration-by-optimization method that is amenable to efficient implementation. We derive regret bounds that depend on the game structure in a more transparent manner than previous theoretical guarantees for this paradigm. Our bounds feature instance-specific quantities that reflect the degree of alignment between observations and losses, and resemble known guarantees in the stochastic setting. Notably, they achieve the standard $\sqrt{T}$ rate in easy (locally observable) games and $T^{2/3}$ in hard (globally observable) games, where $T$ is the time horizon. We instantiate these bounds in a selection of old and new partial information settings subsumed by this model, and illustrate that the achieved dependence on the game structure can be tight in interesting cases.

Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
Federico Di Gennaro*1 EPFL, Lausanne, Switzerland digennarof..o 009gmail. com
Khaled Eldowa "
Università degli Studi di Milano. Milan, Italy & Politecnico di Milano, Milan, Italy khaled. el dowaa3@@m.... com
Nicolò Cesa-
Università degli Studi di Milano, Milan, Italy & Politecnico di Milano, Milan, Italy nicolo. cesa- bianchi @unimi. it
Abstract
In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing linear structure on both the losses and the observations. This setting can be viewed as generalization of linear bandits where loss and feedback are decoupled in a flexible manner. In this work, we address a nonstochastic (adversarial), finite-actions version of the problem through a simple instance of the is amenable to efficient implementation. We derive regret bounds that depend on the game structure in a more transparent manner than previous theoretical guarantees for this paradigm. Our bounds feature instance-specific quantities that reflect the degree of alignment between observations and losses, and resemble known guarantees in the stochastic setting. Notably, they achieve the standard VT rate in easy (locally observable) games and 72/33 in hard (globally observable) games, where is the time horizon. We instantiate these bounds a selection old and new partial information settings subsumed by this model, and illustrate that the achieved dependence on the game structure can be tight interesting cases.
method that
1 Introduction
Partial monitoring models sequential decision- makinn problems with general feedback structures. generic nonstochastic partial monitoring problem is characterized by action space A, an outcome space Z, an observation space Σ, a loss function A Z + IR, and an observation function Φ: A x 2 + Σ. All of these components are known to the learner, who interacts with an unknown environment in a series of T' rounds. In each round the learner picks an action A E A, observes (AA,, Zt), and incurs the (unobserved) loss (AA Zt). where Ze Z is latent outcome. The learner aims to minimize the regret, defined as the difference between the cumulative losses of played actions and the cumulative losses incurred by the best action in hindsight. This general decoupling between losses and observations results in an extraordinary modeling power. Not only does this framework encompass full-information scenarios [23, 13], where the latent outcome be inferred from the observation, and bandit scenarios [4, 11], where the loss and the observation coincide;
Equual contribution.
Now at ETH Zürich. Zürich, Switzerland. NNw at Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK; Grenoble, France.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

it can model problems that interpolate between these two extremes, like feedback graphs [2], and problems that go beyond bandit feedback, like dynamic pricing [14]. The primary object of study in this framework is how the structure of the game affects its difficuity, measured via the notion of minimax regret (the best achievable worst-case regret).
When A and Z are both finite, one recovers the well-studied finite partial monitoring problem. An extensive line of work over the last few decades [48, 14, 3. 20, 6, 38, 39] has shown that all finite games can be classified into one of four classes, each characterized by the achievable minimax rate in terms of T, which can only be ((()), ((T*/*), ((T) or O. These classes, respectively, consist of: hopeless games, hard-or (strictly) globally observable- games, and trivial games. What delineates these categories are precise 'observability" conditions on the loss and observation functions. An important work in our context is that of Lattimore and Szepesvári [40], who introduced the
easy-or locally observable-
(EXO) method (see Section 3 for a detailed description) and achieved-via an intuitive and efficient algorithm-the best known rates for the problem, free from arbitrary and redundant game-dependent constants that appear in prior results.
Nevertheless, the restriction to finite outcome spaces remains limitation of this model. On the other hand, the linear partial monitoring framework [42, 15, 31, 32] allows infinite outcomes, but restricts that, for given outcome, the loss and observation functions the actions. This framework still encompasses a broad spectrum of problems (see Section 2), and arguably, provides more intuitive observation structure, free from the combinatorial complications of the finite model (which can nonetheless be made to fit within the linear framework [32]). A simpler point of view sees this model as a generalization of the standard linear bandit problem [17, 10], which corresponds to the case when the loss and observation f'unctions coincide. Kirschner et al. [31, 32] studied an instance of this model in the stochastic setting (where the hidden outcome is fixed over the rounds and the learner receives noisy observations), adopting version of the information dirrrat sampling [49] algorithm. Remarkably, they showed that the classification theorem continues to hold in the linear setting with analogous observability criteria. Also of note is that their bounds feature certain alignment constants that reflect the difficulty of the game within its respective class in an arguably more interpretable manner compared to finite partial monitoring results.
linear in some representation of
In the nonstochastic (adversarial) setting, linear partial monitoring problem was studied by Lattimore and Gyorgy [37], who also adopted the EXO approach. In fact, their setup is more general than what we described above since their observation function is taken as arbitrary. Nevertheless, they established an elegant result bounding the regret of a general EXO policy in terms of a generalized version of the information ratio [49], which characterizes the Bayesian regret of information-directe sampling. As such, however, their bounds are still of largely opaque nature in terms of their dependence on problem- speciifi parameters. Moreover, in its general form, implementing their EXO algorithm involves solving a daunting optimization problem (over a possibly infinite dimensional space) at every step in order to compute a loss estimation function and a sampling distribution. Hence, though constructive, their approach serves more as a template than concrete implementable policy. An expanded discussion on related works is provided in Appendix A.
1.1 Contributions
We address a finite-actions version of adversarial linear partial monitoring through a simple instance of the EXO method. Outlined in Section 3, this policy builds upon an exponential weights update and imposes a simple structure on the adopted loss estimator, which is made possible thanks to the linearity of the observation function. As result, the aforementioned optimization problem is reduced to one of minimizing a convex objective over probability distributions over the actions, subject to a certain convex constraint. This problem is efficiently solvable against many loss (outcome) spaces of interest. Under the observability conditions identified by Kirschner et al. [31] in the stochastic setting, we prove new regret bounds for this policy in Sections 4 and 5 for locally and globally observable games respectively; the former of order vT and the latter of order 1 2/3 as one would expect.
The proofs rely on bounding the optimal value of the optimization program alluded to above via an application of the minimax theorem, following the analysis of EXO by Lattimore and Szepesvári [40] in the finite setting. However, to better exploit the linear structure of our setting, we employ new arguments, including more natural way of constructing exploration distributions in locally observable games. The resulting bounds feature interpretable instance-depender quantities, similar to the alignment constants of Kirschner et al. [31, 32], that gauge the difficulty of the game within its

---

observability class. We then illustrate the versatility of the bounds by instantiating them in selection of both locally and globally observable games, proving their near-optimality some cases.
2 Preliminaries
Notation. For a positive integer d, [d] denotes the set {1.....d} d]. We use the Iverson bracket notation [.I to denote the indicator function. For a set S _ R co( denotes its convex hull, and ext(S) the set of its extreme points. Moreover, its (absolute) polar set defined as 5 == far E TR. sup.es Kx, s) S 1}. For a real matrix X, tr(X), rk(X), col(X), X and |X denote, respectively, its trace, rank, column space, MoorePenrose inverse, and operator norm (induced by the Euclidean Ly-norm). For p E [0, 00], let (r)r) be the centered Lp ball of radius r > O. We use 1. and Ia to denote, respectively, the d-dimensional vector with all entries equal to 1 and the d x d identity matrix. The probability simplex in Rd is denoted by Aa- = {ar E [0, 1] ||ا|| = 1}. Given a finite index set Z and collection of matrices (X: E 7), all with the same number of rows, we denote by span (X: 2 E } the span of all their columns.
2.1 Problem setting
Let A= [k] denote the action set, where l is a positive integer. We associate every action a E AA with a feature vector tha E IRd and an observation matrix Ma E Rdxx((a) where ni.)) maps every action to a positive integer. We will use X' to denote the set (vaa a E A). Let c R be a convex and compact loss space, which, in our setting, is synonymous with the outcome space Z as used in the introduction. We assume here that contains a centered Ly ball (r(r) of some radius > 0. This simplifies the observation structure of the game and suffices subsume typical cases such as when L represents the absolute polar set of X' or a ball of bounded norm. We study the following game between learner and oblivious adversary over T rounds. Before the game starts, the adversary secretly chooses a sequence of loss vectors (fe) (fT)EE(), where le E L. Then, at every round E [T]. the learner: i) selects (possibly at random) an action A, E A: ii) observes the signal Φ == M,,6 & E Rm((A), which, in general, is distinet from the incurred (but unobserved) loss TT, le E R. The feature mapping and the observation matrices are known to the learner. For brevity, A. In the notation used in the introduction, E A and l E f. the loss map in the setting becomes (a,, E) = J e, while the observation map becomes ((a, f) = T.
==
let (a) = v._ l, for every
that for
For round / E [7]. let H4 = (A,, &5)==1 denote the interaction history up to the end of the round, and let F, = (HH) denote the o-algebra generated by H4. The learner's ' policy can be represented via sequence (T, )E(T) of probability kernels such that n. maps the history H4-1 to a distribution over the actions, from which A₁ is to be sampled. The learner's goal is to minimize the following standard notion of regret
T ye (A))
T
RT =
min Σ (a), acA
where the expectation is with respect to the internal randomness of the algorithm. The dependence of the regret on the learner's s strategy (T.); and the sequence of losses (fx); is suppressed from the notation for brevity. The minimax regret is defined as Ry == inf inf (xx), suP(e.). Rí- where the inf is over all (possibly randomized) learning algorithms and the sup over all sequences T loss vectors from L. Similarly to [31, 32], we impose standard boundedness assumption throughout this work:
Assumption 1. It holds that max,,bE.A.ee. ((v. - v/b) el < 2.
As a notational remark, we define E, [-] == E|- F,-1), with Fo being the trivial o-algebra. Moreover, throughout the paper, we treat functions over as vectors in RR. In particular, for b E A(= [K)), the indicator vector eb I corresponds the function a + Ia b] over A.
2.2 Observability conditions and lower bounds
Similarly to the finite partial monitoring setting, the observation structure of the game characterizes the achievable regret. Before we proceed, we introduce some relevant concepts. An action a A
3

---

is called Pareto optimal if V/a E eex((co(X')): ie., v. is an extreme point of the convex hull of X. ( a E } and contain no two actions with the same
Let S A satisfy that ex)(co(X)) features. Additionally, let k* == |A This set is well-defined since ext(co(X() S X: moreover, it is the smallest subset of A that satisfies min f) = min (Va-. {) for every & E IR The set of actions that are optimal against a loss vector f E Id is denoted by P(t) == a E A (We- wh, f) S 0 for all E A), which extends to sets C S Rd as P(C) = (()) We state below the observability conditions that determine the difficulty of the game (in terms of the scaling of the regret with 2') as identified by Kirschner et al. [31] in the stochastic setting.
Definition (Observability conditions [31]). game is called globally observable if
Va 1/b span Me I A} for all a, b E A.
(2)
Further, a game is called locally observable for every convex set C SCC. R
Vo lb E Me c P(C)) for all a, P(C).
(3)
Note that the second condition implies the first by taking C as Rd (or simply {0)). Intuitively, in a globally observable game, one can use the observations to estimate the difference between the losses of any pair of actions. In locally observable games, one can do so efficiently: only using observations from actions that perform at least as good as the pair of interest. (See also the equivalent formulation provided in Lemma below, or Lemma in Appendix B.) Kirschmer et al. [32] refined these conditions to account for cases when L is an arbitrary (and possibly low (ow-dimensiona) set. We do not pursue this direction here; as mentioned in the problem setting, we focus on the case when L has non-empty interior (in particular, we assumed it contains a centered L2 ball), rendering the conditions above sufficient to derive the following lower bounds.
Proposition 1. Assume that the game has least two non-duplicate Pareto optimal actions, and that (r) S C for some r > 0. Then, the minimax regret Rt is S(VTT) if the game is locally observable, ((T4)) if it is globally but not locally observable, and (T) otherwise.
These bounds are obtained in the same manner as similar results in the finite outcomes setting and the linear stochastic setting [31], see Appendix J. However, one must deal with some technical nuisances since in our case, the stochastic setting is not immediately subsumed by the adversarial one; besides boundedness issues, the manner in which noise is added to the observations can make the relationship a bit subtle, refer to [35, Chapter 29] for details. Over the coming section, we will derive regret upper bounds with matching rates and interpretable game-dependent constants for an EXO-based policy.
2.3 Examples
Owing to its flexibility, this setting can model many online learning problems, classic and contrived, as we now elaborate. In all these examples, L is typically taken as X"", which is equivalent to B (1) when the = e, for all E A.
Full information. d = k. v. ca. and M.- Is for all a E A. Hence, the learner observes the entire loss vector upon playing any action, and the game is clearly locally observable.
this game, also known as prediction with expert advice [13], we have that
Feedback graphs. An instance of this game [44, 1, 2] is characterized by a graph G = (A, E) over the actions (we focus on undirected graphs). As in the previous game, M. only has the vectors (Co)sE (a as columns, where Ng(a) is the neighborhood of a (which need not include itself). Globally observable games correspond to weakly observable graphs, where the loss of every action is observable; while locally observable games correspond to strongly observable graphs, where each action either has a self-loop, is connected to all other actions, or both.
and dha c.: however.
Linear bandits. Adversarial linear bandits [17, 10] (with a finite action set) is recovered by simply fixing M, tha for all E A. This is easily verifiable be locally observable game, which reduces to a standard bandit problem when v. ea.
Linear dueling bandits. This game is a quantitative variation of the dueling bandits problem. It was proposed in [31, 32] in the stochastic linear partial monitoring setting, extending the fitite-oucomms
formulation in [24]. Here, the action set has the form A [m] [m] for some positive integer m.
Given feature mapping + b. from [m] to Rdd we extend it to A via (a, b) + Da.D dh vo.

---

However, the observations are given by Ma.b = dha lbb hence, the learner receives relative feedback. This game can also be shown to be locally observable (31,32)
Bandits with ill-conditioned observers. Modifying a problem from [18], consider a game where d == k. th Ca. and Ma (1 (1-e) - for some E (0, 1J. such that & = 1 recovers standard bandits. Note that the observations become, in a sense, less informative as e decreases. Nevertheless, the game is always locally observable as Ex - Et M/e Mo).
Composite graph feedback. We describe now another variant of the graph feedback problem, still characterized by undirected graph G (A. E). which we now assume contain all self- self-loops. Here, again, d = It and vi = c.: however, upon playing an action, the learner observes the average of the losses of its neighbors (which includes the played action itself). That is, if A is the adjacency matrix of the graph and D is the degree matrix, then Ma is the a-th column of AD-1 This is less informative than standard graph feedback, and draws inspiration from problems studied in [57, 25]. Global observability here corresponds to AD- being invertible, whereas the only locally observable graph the one corresponding to standard bandits, see Appendix I for more details.
3 Exploration-by--piiiizttta
the Linear Case
We describe in this section a simple instantiation of the EXO approach [40, 37] suited to our setting, resulting in policy amenable to efficient implementation. We show in later sections that this policy suffices to obtain tight bounds, even if its specificity excludes it from enjoying the generic guarantees provided by Lattimore and Gyorgy [37] and Lattimore [36] for general EXO. The predictions made by this policy revolve around the predictions of an instance of the exponential weights algorithm, restricted over the set A of Pareto optimal actions (without duplicates). When executed against a sequence of loss functions (Ni)ee(r with Te: A I. the exponential weights algorithm outputs at round distribution qi E Aş given by
[a A (-n (.(a))
(:(a)
ENEE exp( (11) E.
where 17 >> 0 is a learning rate parameter. This would have been a sound approach on its own were we able access the loss functions (ye) directly. Instead, we are to estimate these loss functions, which, in general, requires carefully exploring the actions. Incurring minimal loss while doing so, to the extent allowed by the structure of the game, the essential goal of the EXO method. Towards making this tradeoff more explicit, the following lemma provides a generic regret bound for any policy by pivoting around the predictions (ge), produced against some sequence (Tt), of surrogate loss functions satisfying certain conditions. (Proofs of this section's 's results are in Appendix D.)
Fix a learning policy and define pt as the law of A, conditioned on Fi-1. Let qe be as given in for some learning rate 1) > and sequence of surrogate loss functions (ft)) such that Tt I2* is Ft- -e-easuurbble and satisfies max [n)) < 1. Further, let a* E arg min Ei=1 Va(a). Then, the regret of the policy satisfies
Lemma 1.
RT S log k
Σ
[(p E
qt, Ma) + n/gc, E.ii) + (gc Ca-, Me Egge)
While not particularly insightful, results of this form nonetheless motivate the EXO approach, where one picks the predictions and the surrogate loss functions by solving an optimization problem at every step, seeking to minimize an upper bound on the second term in the regret guarantee of Lemma 1. More precisely, at every round I, reliant on the observed history thus far, one decides on prediction p. A and a function g:: AA x IR + R so as to set Y1. ge( (Ar, Φt), assuming Ilge( (A. lo) S 1/n. To make the dependence on & more explicit, we denote by H the x matrix with (wa JaE.A as columns. In particular, this enables us to write ye H 4, Considering the t-th summand in the second term in the bound of Lemma 1, the term inside the expectation becomes
qr, .. 2x) + ( (aPr(a) M (,)2) (4: Ea- .H' E, - (a)gg)) M. (e)) (5) (p. (p.
where ga MT is the entry-wise square of gr (a, M. (x). The general strategy to optimize jointly in Pt and gr the expression above, maximized over the adversary's 's choice of &, Besides some
5

---

small deviations, this still aligns closely with the approach of Lattimore and Gyorgy [37].' Now, however, exploiting the structure of our setting. we sidestep the demanding task of optimizing over all possible loss estimators by committing to a simple structure commonly used in (adversarial) linear bandit algorithms [10, 35], modified slightly to suit our partial monitoring setup.
Before proceeding in that direction, we introduce some notation. Let M denote the d x (E. n((a) matrix obtained by stacking horizontally the observation matrices of all the actions; such that Span(M. E A} = col(M). For any π E Ak. we define Q(T) == LasA (T)) Ma Moreover, with 5 E (0, 1/2]. let Qs(T))= == Q(1 - 5) + (l))). This forces the argument of Q to be bounded away from zero, implying that (=)(
M,
col(M) for any л E A (see Lemma 8 in Appendix C), which is a convenient property for the analysis. Still, Qs(T) need not be invertible as we allow that rk(M) ) < d: hence, the ensuing presentation will feature quantities of the form (TT)) and Qs (T)).. Returning to our task, the following lemma specifies a certain form for the pair (pr. 9t) and provides the resulting regret bound under global observability.
Lemma 2. In the same setting as Lemma 1, let the predictions of the policy satisfy Pt = (1 5) 51k/k k for some 8 E (0. 1) and pa Ds. and let the surrogate loss functions satisfy T/ go (A,, @e) where ge(a, b) = (Tx- lage) H Q(pe)* Mas. Then, assuming global observability, it holds that
log k + 25T +
T
Rr S
Σ
E
(
qt 11 T (x) + +nw
Σ (()))((b)(V (6)) Tcsle) vb)
"
1=1
a.EEA
provided that maxa,beAltl - 4b) (o(p))) (16a - 1/6) + maxcc l Qo(p)) Mella S 2. where
mpo
S max || E||. REA,EE
= sup a, PEA2, DEA. LEC
MM Qu(p) - vo)l
Here, Q =: Eg is an estimator of le that is essentially unbiased." 2 Instead of taking the loss estimate of action E A as vh Ee as common in linear bandit algorithms, we use shifted version (va- Hg.)) T2 anchored about Hq: = A (b))))n. Shifting the loss estimators in this manner (via any anchor in co) does not alter the resulting qri however, its effect is that the last term in the bound of Lemma 2 (known as the variance term) is expressed in terms of feature differences. This is crucial if one is to take advantage of either observability condition, since they only relate the observation matrices (in terms of which (.).) is defined) to feature differences. Specifically using lgq, as the anchor is, in certain sense, an optimal choice, see Lemmas 13 and 14 in Appendix C.
With the structures imposed upon 9: and Pt in Lemma 2, we can now reduce our task of minimizing the regret bound to solving a (constrained) optimization problem at every step / (depending on the history only through q over the distribution 5. E IR* In the following, let L be a free parameter satisfying
L 2 w. Define the function& E: A x A x A - R as E(,, p) = (w.. - vb)) f Qo(p) (wa v6). and for every pair q E A& and 17 > 0, define the function Agga: : A L
H as
(p, E) = (p- 9. H.HTA El + 12
Σ a.EEA
Next, define As + R as x(p) = maxabeA b; + max.cA M.. Qs(p) Mella and its sub-level set E, {p A z(p) < 2/nt... Finally, let
A = min max (p, E) and
A = sup A g
p EEL
where Dj = (q A. g(a)= 0.a E A Algorithm summarizes the policy we have arrived at:
at round t, given gt. we choose a distribution p. satisfying =(p.) < 7/12 and maxtec An. (Pe, E) S
"The core algorithm here corresponds to the FTRL. algorithm run on the probability simplex over the actions, while they use FTRL with a general potential over the convex hull of the action set. The two approaches can be related, see [30. Section 5.2]. Moreover, term, which introduces the constraint over the norm of the loss estimators.
use second order bound the Bregman divergence (or stability)
FIts expectation is the projection of & onto col(M). As an alternative form, Lemma 13 in Appendix C implies that (p. = (1/1)(p - q. 9. (TH +
21 E.sA a(a)(v. "gg)" Qs(p)* (Va- Hg).

---

Algorithm Anchored citioration-y--Opimmzaae
1: input: learning rate 1) 0, stability parameter E (0, 1/2), sub-optimality tolerance 2 0,
scale parameter I. 2 w
2: initialize: 7o- = 0
3: for = 1,.... - do
4: Va E A, set ge(a) x Ia E d']exp(-n>Ei11 Da(a))
5: choose Pr. E A such that maxrec Ang (pt, E) I Ar + and =(m.)) s 2
6: set Pr = (1 8)p: + ōlv/k
7: execute A, ~ Pt and observe 6: = MA
8: Va E A, set (a) (th Hqq) (Q(p)) ((,)))Ma,' or simply, Te(a) 4. ((c)) MM
9:
end for
A e, for some tolerance ε > 0. In the following round, Q++1 is computed via the exponential weights update in (4) with De given in Lemma 2. As shown in Appendix D) (in the proof of Lemma 3 below), the functions z(-) and maxte (:, E) are both convex. Hence, the problem at hand is (inite-dimensional) convex program, the structure of which depends that of the loss space L, over which the max in the first (and more troublesome) term of Aq.o is taken. Typical examples of L. like balls of bounded norm or the polar set of X' can further simplify the form of the objective function, see Appendix G for details. Note that the parameter is introduced to maintain numerical stability. Turning back to the regret, the following bound readily follows from Lemma 2.
log k + A + (25 + TT)
Proposition 2. Under global observability, Algorithm I satisfies Rr S
What remains now is deriving an upper bound on A; depending on the structure of the game, and tuning the algorithm's parameters accordingly. Note that an adequate tuning of 1) would depend on A, (or satisfactory upper bound), which might be difficult to compute. Following Lattimore and Szepesvári [40], we can use learning rate sequence (πı).. which is updated at round f ++ using the attained value at the optimization problem of round t. This still allows recovering essentially the same regret rates, details are included in Appendix H for completeness. Now, for bounding Ai the properties of our An.q allow us to invoke Sion's minimax theorem, as Lattimore and Szepesvárí [40] did in the finite setting.
Lemma 3. For any > and E Ak, it holds that
Ang
max min Aq.o (p, e). EEC PÊEn
The next two sections will start from this result and derive bounds on A for locally and globally observable games, exploiting the linear structure of the problem.
4 Locally Observable Games
As alluded to before, what distinguishes locally observable games is that exploration, roughly speaking, is cheap. The following lemma provides alternative definition of local observability that appeals to this intuition.
Lemma 4. A game is locally observable if and only if it holds for all E A", E E Rd, and a' E arg min EA T that t. - - E span [M, v, l s vo f}.
Fixing q AC and 17 O, we show in this section how to exploit this property to bound AG. We sketch here the main arguments, deferring details to Appendix E. where proofs of this section's 's results can be found. Note that Lemma 3 reduces the task of bounding Ar to finding uniform upper bound on minpez. An.g (p, E) holding against any fixed loss vector f. With the clairvoyant- knowledge of l that this affords us, we start by constructing a specific distribution E E, that depends on and derive an upper bound on An,o when evaluated this pair. Using this result, we can then bound A and A, by passing to worst case over e E L and E A
Our choice of p will take the form p = yT + (1 >) with 7 E (0, 1/2) and π,P E Ag. For brevity, let = 1 7. The role of is to ensure that p E,, and that of is control the magnitude of
7

---

(p f). As a starting point, it is easy to show that
1n ( + +)p.))
27 + 7 ip- H.H +)+ L
Σ (())g(b) (4a- -b) Q0(7T + +D)) (14a - (bb) (6)
11 1
a.bEAA
27 + 1 ip- q, HTHH 6) + 222
_
Σ (())((b) (4%- - v/) Qo(1)) (va - (/6)))))
(7)
") 1)
a
We proceed first with the selection of f aiming to minimize the second and third terms, which exhibit a tradcoff' between minimizing our loss against (compared to q) and sufficiently exploring minimize the variance of the loss estimator. In finite partial monitoring [39, 40), the analogous predicament is resolved via a 'water transfer' operator. Leveraging properties of the same spirit Lemma this technique involves perturbing to ensure that each action receives comparable mass to actions whose estimators rely on the observations of the former, without incurring more loss in the process. While some adaptation of this approach can be utilized here (more details below), we will describe in what follows an alternative manner of redistributing the mass in q that is arguably more natural (especially considering the structure of (7)), and that, moreover, only relies on the simple characterization of local observability given by Lemma 4, without explicit reference to the neighborhood relation used in finite partial monitoring.
To control the third term, it is helpful first relate the feature differences (v), - 1bba.bbeA to the observations matrices (Ma)ae (or their collective form M) seeing that (P) is a linear combination of the latter. While this feat only requires global observability, the stronger assumption of local observability allows one to do so in a manner that facilitates controlling the second term simultaneously, will be shortly shown. Towards this goal, we define some relevant objects. Let n == ΣneA n(a) and k- = |A*). Note that any u E R" can, with a slight notation abuse, be decomposed (u(a))aεA with v(a) e Ia((a) such that Mv = Eae Ma)(a) In locally observable games, Lemma 4 gives that for any loss vector & E L. action a E AA", and optimal action a" arg min vb_ é, there exists vector IR" such that tha tha MM and that, the same time, having v(b) # 0 for some b A implies that vi e + f. Hence, the following set is not empty under local observability:
W = {x- -Aa)DEA" E RK xn Ea" E arg min &o v(a, b) E A,,
nEA
Ve - Va- MX2 and Aa (b) + - 1 1 wh e
Each member of this set is a sequence of weight-vectors in F", one for each action in AA', that allows recovering the difference between its feature vector and that of a fixed optimal action by linearly combining columns from the observation matrices of better- (or similarly) performing actions. Finally, for À E Whos and E A", let supp(A, a) == (b E A (b) + 0}. and define (A) = UsEA- supp(A, a); that is, the set of all actions whose observations are relied on.
Now, fixing some À E Whle and a" E arg min wh (such that vha -/aa- = MA, for all a E A).
one can show that
((a)g(b) (b.a 2/) (G(F)) (we -b) 2 Σ g(a) (+h -aa)) Qx( (va Vo-) A.PEAA
aEA
max (EcEalAA(()))) SEA-
Σ Σ
a(a)) ((a))AA(())] ((( (o(F)
cEAGEA-
An easily demonstrated fact is that for any r E Ac. M(
2rk(M) < 2d.
In view of the bound reported above, one can exploit this property by setting p = E.EA va)) where Va E A is such that (c) x (c)]l. That is, we choose P as mixture (weighted according to 2) of k- distributions, each associated with a Pareto optimal action a E A and supported on supp(X, a). In particular, action a transfers a fraction of its total mass g(a) to action e proportionally to [c][[]] representing the 'importance" of e to a. (For a", simply set v.- c) As an aside, though arrived at through a different manner, the exploration distribution used by Lattimore and Szepesvári [40] in the analysis of EXO in finite partial monitoring assumes a form similar to p. only
8

---

that, roughly speaking, Va is taken there as uniform over supp(X, a). We show in Appendix E. way incorporate this alternative choice (among others) into the analysis scheme showcased in this section, though resulting in a generally worse bound than what we report below for our choice of p.
Proceeding with the analysis, note that by the definition of Wolee, 1h. T Th for all b supp (A, a): c,),
hence, it holds that (v,- Ca: H f) I 0 for all A". And since q = Ene (V, see now that the second term in Equation (7) becomes non-positive. While for the third term, a refinement of the arguments laid above gives that
Σ (())((b) (+aa - b6) T Qo(P) (va bb) S 48% min {rk(M), |supp())] A.DEA
where BA == ma EBEA (b)] represents the 'difficulty' of recovering the features from the observations via A. The alternative bound featuring ssupp\A) brings an improvement in problems with abundant feedback per played action, like the full-information and graph feedback problems. We then proceed by taking the infimum of the bound above over À E Wiac before passing to the worst case over é L. What remains now is the less challenging task of bounding the first term in (7). This is done by choosing 7 7). provided v is small enough, with the leading constant chosen to ensure that ( S 2/nL; specifically, it is an upper bound on the value of an optimal-ded -eeigng like criterion that x is chosen to minimize. Ultimately, we arrive at the following result:
Theorem 1. In locally observable games, holds that
A/ S max inf LEC XEWlee
8T.2,3 132 min (rk(MM, suup(\)]] | + +2T(1 + (20) min (rk(M), w"}
provided 1
21 + (g) min (rk(M), w²}. where 8glo == max min abEEAVER":
[(((
1)
Va 2/ =M
CEA
and w" min
|S]
max] M, UU M.MJU) Ms Sk. DEA
SCA
Here, U E (d) denotes a matrix whose columns (μ))εειR(M)) form an orthonormal basis for (M) Let Broc = maxtez minxew 3x. which satisfies Broc 2 Bglo (see Lemma 17 in Appendix E). Assuming for simplicity that L., 3roc 2 1; the following simpler bound is obtained immediately:
A S 1
We see that under local observability, similarly to finite partial monitoring [40], there exist constants a, B such that A; S given that 17 S 1/B. Assuming 5 and are sufficiently small, setting 7 = min (1/B, v /log//o7) yields via Proposition that Rr is VoVTToo k). We refer again to Appendix H for a discussion on adaptive learning rates following [40]. We also note here that B can be chosen conservatively as it only affects the regret additively. We now use the bound of Theorem I to obtain regret bounds for the locally observable games discussed in Section 2. Omitted details and derivations are provided in Appendix I.
Full information. Here, playing any action is sufficiently informative; for any l E L, we can trivially pick À Wile supported only on an optimal action and satisfying Bx < /2. Moreover, w* < 1 taking S as singleton. Hence, we recover the order-optimal OVV ki) regret bound [13].
Strongly observable feedback graphs. Generalizing the example above, can, against any é C. find Wles supported on an independent set (a set of actions no two distinct members of which neighbors) and satisfying B^ < 2. This set can be iteratively constructed by first selecting an optimal action, removing its neighbors from the graph, and repeating this (proceeding with the best remaining action) until the graph is empty. This gives that 3 supp(A) is bounded up constant by (9)), the independence number of the graph (size of a maximal independent set). The same can be shown to hold for w", allowing us to recover the near-optimal O (G))T log k) regret bound for this problem [44, 2].
Linear bandits. Since the features and the observation vectors coincide, it is immediate that Bloc S 2. The regret bound is then of order / /dT log(k) (as achieved in [10] and [35, Chp. 27I), which reduces to the optimml / //:Tlog(13 rate for standard bandits.
'The inverse of U M,M, U exists when span( (oann(MM (Mr) col(M). see Lemma 9 in Appendix C.

---

Linear dueling bandits. It also holds in this example that Sloe S 2, implying again that the regret bound is of order v /dT log(k).
Bandits with ill-conditioned observers. Since Ca cb 1/e(Ma Mr), we have that Ptoc z/c. Thus, the regret bound is of order 1/s//Tllog k. We show in Appendix J that this bound is tight up to logarithmic factors.
5 Globally Observable Games
On the other hand, exploration is generally costly in globally observable games. Here, starting from the decomposition in (6), we simply pick ý = q and place the burden of controlling the variance term entirely on π. Consequently, y must be kept sufficiently large; precisely, of order v7. This causes the final bound to scale with 1/ /17. hence becoming 7-dependent, which aligns with the finite outcomes setting [40]. Building on this, the next theorem provides two bounds on A The first resembles the square root of the second term in the bound of Theorem 1, while the second bound features a refined alignment constant but has a generally worse dependence on the structure of the observation matrices. Theorem 2. In globally observable games, it holds that
Ar < 4v 1/1L min (1 + (glo) v min(rr(MM), w" (1 + $2.glo) Vu²
provided that
2 (1 + L2) min (1 + S
w') (1 + 82 32 u² J. where
32.gio max a.bEA
M (w%- +/))l and u² min |
M T U (ErEsU) U M,M, u M S k.
Note that w² S u², and that S2. = Maaaa,bbA min dh Moollll hence, Ba,elo S Bgto S v VkB32.gto This theorem shows that in the present regime, there exist constants a, B such that A; S a/ V/ given that 17 S I/B. Assuming again that 8 and are sufficiently small, setting = min (1/n, (log k/ar)//3)) 3/33 yields via Proposition 2 that Ry is ((TT)) (log k))/3). The adaptive tuning of 7) discussed in Appendix H. We now revisit the globally observable examples from Section 2.
Weakly observable feedback graphs. Here, it is immediate to verify that Bgto 2. A subset of vertices (actions) is said to be a total dominating set if the union of their neighborhoods covers all vertices. Moreover, the total domination number of the graph, 8(G), is defined as the size of minimal total dominating set. It can be easily shown (see Appendix I) that w S 6()), leading to a ((((g) log 1)/333333 regret bound, Further refining this bound to scale with the weak domination number (which only considers weakly observable nodes) used in [1] requires a careful combination of the analyses of this section and the previous one to eliminate unnecessary forced exploration over the strongly observable portion of the graph.
Composite graph feedback. It holds here that =² rkk= k; hence, the second bound generally better. The regret bound then O( log (1)1/3(82,.)))) T)2/3), the tightness of which remains to be studied. In Appendix I, we provide more detailed discussion about the interpretation of 82 in this problem, as well as two instantiations of which in simple families of graphs.
Limitations and Future Work
Besides enjoying the same rates in T as the bounds derived in this work, the regret bounds derived by Kirschner et al. [31. 32] in the stochastic setting feature analogous alignment constants to Booc and Bglo, see [31, Lemma 13] or [32, Lemma 5]. Comparatively, our bounds enjoy some extra versatility as they easily yield nearly tight guarantees for feedback-rich problems like full-information and feedback graphs, which were not addressed in [31, 32]. However, our exposition is limited to dile-dimesiionl loss spaces (like [31] but unlike [32]) and finite actions. The former aspect precludes us from recovering tight guarantees for finite partial monitoring as the observation conditions do not match in general, see [32, Example 8J. Addressing this aspect in the adversarial setting is left for future work. Likewise for studying generic compact action sets, for which full classification theorem is lacking also in the stochastic setting. Lastly, characterizing how the minimax regret depends on based constants remains general challenging direction.
10

---

Acknowledgments and Disclosure of Funding
KE and NCB acknowledge the financial support from the FAIR project, funded by the NextGen- erationEU program within the PNRR- -E-A scheme (M4C2, investment 1.3, line on Artificial Intelligence), the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the NexIGenerationEU program within the PNRR scheme (M4C2, investment 1.1), the EU Horizon BL4-202-HUUMAN-U research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of AI for Sustainability), and the One Health Action Hub, University Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR
6).
References
[1] 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 of Proceedings of Machine Learning Research, pages 23-35, PMLR, 2015.
[2] Noga Alon, Nicolò Assa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785-1886, 2017.
[3] András Antos, Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Toward a classification of finite montial-mniioriing games. Theoretical Computer Science, 473:77-99, 2013. ISSN 0304-3975.
[4] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[5] Michel Balinski. On the graph structure of convex polyhedra in n-space. Pacific Journal of Mathematics, 11, 06 1961. doi: (0.2140/pjj..19 19t.....9..........
[6] Gábor Bartók, Dean P Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitooinggllsssficttionn, regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967-997, 2014.
[7] Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Minimax regret of finite partial-monitrring games stochastic environments. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 133-154. PMLR, 2011.
(8] Gábor Bartók, Navid Zolghadr, and Csaba Szepesvári. An adaptive algorithm for finite stochastic partial monitoring. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), ICML 12, pages 1727-1734. Omnipress, 2012.
[9] Aharon Ben-Tal and Arkadi Nemirovski. Lectures Modern Convex Optimization. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA, 2001. ISBN 11-00-98871-491-21
[10] Sébastien Bubeck, Nicolò Desa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Proceedings of the 25th Annual Confer- ence on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 41.1-41.14. PMLR, 2012.
[11] Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and TrendsS in Machine Learning, 5(1):1-122, 2012.
[12] David Carlson, Emile Haynsworth, and Thomas Markham. A generalization of the Schur complement by means of the Moore-Penrose inverse. SIAM Journal on Applied Mathematics, 26(1):169-175, 1974.
[13] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schappre, and Manfred Warmuth. How use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
11

---

[14] Nicolo Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Regret minimization under partial monitoring, Mathematics of Operations Research, 31(3):622-58., 580. 2006.
[15] Sougata Chaudhuri and Ambuj Tewari. Phased exploration with greedy exploitation in stochastic combinatorial partial monitoring games. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[16] Alon Cohen, Tamir Hazan, and Tomer Koren. Tight bounds for bandit combinatorial optimiza- tion. In Conference on Learning Theory, pages 629-649--692 642. PMLR, 2017.
[17] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[18] Khaled Eldowa, Nicolò Cesa-Bianchi, Alberto Maria Metelli, and Marcello Restelli. Information capacity regret bounds for bandits with mediator feedback. Journal of Machine Learning Research, 25(353):1 1-36, 2024.
[19] Erhan Baki Ermis and Venkatesh Saligrama. Distributed detection in sensor networks with limited range multimodal sensors. IEEE Transactions on Signal Processing, 58(2):8438858 2010. doi: 10. 109/TSPP
[20] 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 of Proceedings of Machine Learning Research, pages 382-390. PMLR, 2012.
[21] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv: 13487, 2021.
[22] Dylan Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. In Advances in Neural Information Processing Systems, volume 35, pages 35404-35417. Curran Associates, Inc., 2022.
[23] 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):119 1399, 1997.
[24] Pratik Gajane and Tanguy Urvoy. Hillity-based dueling bandits as a partial monitoring game. arXiv preprint
2015.
[25] Manjesh Hanawal, Venkatesh Saligrama, Michal Valko, and Rémi Munos. Cheap bandits. In International Conference on Machine Learning, pages 2133-2142. PMLR, 2015.
[26] Elad Hazan. Introduction Online Convex Optimization. MIT Press, 2022.
[27] Maxime Heuillet, Ola Ahmad, and Audrey Durand. Randomized confidence bounds for stochastic partial monitoring. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages
PMLR, 2024.
[28] Maxime Heuillet, Ola Ahmad, and Audrey Durand. Neural active learning meets the partial monitoring framework. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 1621-1639. PMLR, 2024.
[29] Andrew Holbrook. Differentiating the pseudo determinant. Linear Algebra and its Applications, 548:293-304, 2018 ISSN 0024-3795.
[30] Shinji Ito and Kei Takemura. An paplorationbb--ooiiiizze approach best of both worlds in linear bandits. In Advances in Neural Information Processing Systems, volume 36, pages 71582-71602. Curran Associates, Inc., 2023.
[31] Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Conference Learning Theory, pages PMLR, 2020.
12

---

[32] Johannes Kirschner, Tor Lattimore, and Andreas Krause. Linear partial monitoring for sequential decision making: Algorithms, regret bounds and applications. The Journal of Machine Learning Research, 2401):6660-116333 2023.
[33] 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. Curran Associates, Inc., 2015.
[34] Joon Kwon and Vianney Perchet. Online learning and Blackwell approachability with partial monitoring:
Optimal convergence rates. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 604-613, PMLR, 2017.
[35] T. Lattimore and Cs. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[36] Tor Lattimore. Minimax regret for partial monitoring: Infinite outcomes and Rustichinis regret. In Conference on Learning Theory, pages 1547-1575, PMLR, 2022.
[37] Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages 2965-2992 PMLR, 2021.
[38] Tor Lattimore and Csaba Szepesvári. Cleaning up the neighborhood: full classification for adversarial partial monitoring. In Algorithmic Learning Theory, pages 529-556 PMLR, 2019.
[39] Tor Lattimore and Csaba Szepesvári. An information-theerrtiic approach to minimax regret in partial monitoring. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages
PMLR, 2019.
[40] Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Conference Learning Theory, pages 2488-2515, PMLR, 2020.
[41] B. Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statisties, 28, 10 2000.
[42] Tian Lin, Bruno Abrahao, Robert Kleinberg, John Lui, and Wei Chen. Combinatorial partial monitoring game with linear feedback and its applications. Proceedings of the 31st Inter- national Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 901-909 PMLR, 2014.
[43] Gábor Lugosi, Shic Mannor, and Gilles Stoltz. Strategies for prediction under imperfect monitoring. Mathematics of Operations Research, 52885-513-528, 2008
[44] Shie Mannor and Ohad Shamir. From bandits to experts: On the value side-observations, In Advances in neural information processing systems, volume 24, 2011.
[45] Shie Mannor and Nahum Shimkin. On-line learning with imperfect monitoring. In Learn- ing Theory and Kernel Machines, pages 552-566, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45167--.
[46] Shie Mannor, Vianney Perchet, and Gilles Stoltz. Set-valued approachability and online learning with partial monitoring. Journal of Machine Learning Research, 1 15(94):3247-3255 2014.
[47] Kenneth Nordström. Convexity of the inverse and MoorePenrose inverse. Linear Algebra and its Applications, 434(6):1489 1512, 2011.
[48] Fabio Piccolboni and Christian Schindelhauer. Discrete prediction games with arbitrary feedback and loss. COLT, 2001.
[49] Daniel Russo and Benjamin Van Roy. Learning optimize via information--irecter sampling. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[50] Aldo Rustichini. Minimizing regret: The general case. Games and Economic Behavior, 29 (1-2):224-243, 1999.
13

---

[51] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 176, 1958.
[52] G. W. Stewart. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Review, 19(4)6334662, 1977.
[53] Taira Tsuchiya, Junya Honda, and Masashi Sugiyama. Analysis and design of Thompson sampling for stochastic partial monitoring. Advances in Neural Information Processing Systems, volume 33, pages 8861-8871. Curran Associates, Inc., 2020.
[54] Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-both-worlds algorithms for partial monitoring. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 1484-1515, PMLR, 2023.
[55] Taira Tsuchiya, Shinji Ito, and Junya Honda. Stability-penalty--a leader: Sparsity, game-dependency, and sott-offboth-workkde In Advances in Neural Information Processing Systems, volume 36, pages 47406-47437, Curran Associates, Inc., 2023.
follow-the-regularizee
[56] Taira Tsuchiya, Shinji Ito, and Junya Honda. Exploration by optimization with hybrid regulariz- ers: Logarithmic regret with adversarial robustness in partial monitoring. Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 48768-48790. PMLR, 21-27 Jul 2024.
[57] Michal Valko, Remi Munos, Branislav K Kveton, and Tomá Kocák. Spectral bandits for smooth graph functions. Eric Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 54, Bejing, China, 22-24 Jun 2014. PMLR.
[58] Hastagiri Vanchinathan, Gábor Bartók, and Andreas Krause. Efficient partial monitoring with prior information. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[59] Fuzhen Zhang. The Schur complement and its applications, volume 4. Springer Science & Business Media, 2006.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the claims made in the abstract and introduction are formalized via theorems stated in the main body and formally proven the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We explicitly added section where limitations are discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

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

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
olicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. wttp:cccccppppccccccceooocccccce hua.biii/guddde//deeubbiiiii wwt.SSubmmiiiioooooooooooooooooe
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted this paper fully conforms to the NeurIPS Code of Ethics. There are no ethical concerns related to data collection, experiments, or other aspects of the work, as it focuses purely on theoretical analysis.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical advancements in partial monitoring and does not have direct societal applications. As such, it does not explicitly discuss potential positive or negative societal impacts. The work is foundational in nature and does not involve technologies that could be misused present ethical concerns its current form.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: httpps://neuriss.... http://aaarrs..ceeeeeeeeeeeeeeie cc////mffeeeencc//22////11 for what should or should be described.
21

---

A Additional Related Works
The work of Rustichini [50] is generally recognized as the first work partial monitoring. Notably, he studied a modified notion of regret under which non-trivial guarantees can be derived for hopeless games, see also [45, 43, 46, 34, 36]. Finite partial monitoring has also been extensively studied in the stochastic setting [7, 8, 58, 33, 53, 27, 28]. Among the works cited earlier in the adversarial (finite) setting, of most relevance here are those by Lattimore and Szepesvári [39, 40]. The first proved a minimax theorem for all games with finite actions, linking the minimax (adversarial) regret and the worst-case Bayesian regret. For finite partial monitoring, they bounded the latter by presenting an algorithm (Mario sampling) enjoying a bounded information ratio in the Bayesian setting, which in turn, implies a non-constructive guarantee on the former. The second work, as mentioned already, proposed the EXO method, and showed that its regret matches the non-constructive bounds of the first work. The subsequent work of Lattimore and Gyorgy [37] does, in some sense, link these two results in general linear partial monitoring setup by showing that the regret of EXO can be bounded in terms of general notion of information ratio. We note here that the results by Kirschner et al. [31, 32] in the stationary stochastic linear setting cannot be combined with these findings to yield bounds on the adversarial minimax regret or the regret of EXO, as that requires bounding (some form of) the information ratio for arbitrary (finitely supported) priors over sequences of latent outcomes.
In the same line of work, Lattimore [36] expanded on the results of Lattimore and Gyorgy [37] considering all games with infinite outcomes and finite actions. He showed that the optimal rate in T indeed determined by the behavior of the information ratio, and that for every p E [1/2, 1]. there exist games where the minimax regret is T up to subpolynomial factors. Further, Foster et al. [22] showed that the regret of EXO can also be bounded terms of the general complexity measure for interactive decision making [21], which too is rather opaque in terms of its dependence on game-specific parameters.
Coefficient,
The first work on linear partial monitoring is by Lin et al. [42], followed by the closely related work of Chaudhuri and Tewari [15]. Both study the stochastic setting and only prove 7 bounds under global observability condition. On the other hand, they focus on designing efficient algorithms in the face of combinatorial action spaces that can be exponentially large. On a different thread, Ito and Takemura [30] employ a version of EXO in the standard linear bandit setting (hence our algorithm and theirs naturally follow a similar general template) and obtain best-of-both-worlde (BOBW) bounds (near optimal bounds in both the adversarial and the stochastic settings). Their techniques and contributions remain distinct from ours as they do not address partial monitoring. In related line of work [54, 55, 56]. EXO is used to obtain BOBW bounds partial monitoring, but only for finite outcomes.
B The Geometry of a Linear Partial Monitoring Game
This section provides brief overview of some partial monitoring concepts and terminology, see [3, 6, 31, 35), which will be used in the proofs, particularly those of the lower bounds in Appendix J. We remark that the definitions used here mostly concern the case when (r(r) S L for some r > 0, which is our focus in this work. Recall that X' = [wa E A), and define V = co(X'), which is convex polytope. An action a E A called Pareto optimal v/a E (x';(X);; that is, vaa is vertex of V. The convex cone
== (f E Rd 1 E A, (e. =0= (EE Ve E V, (b. x, e) 20}
is called the cell of a. A Pareto optimal action a satisfies that (wa} n co (v,)) 2 since v is a vertex of V. Hence, by the separating hyperplane thcorem, there exists a vector u E gd such that wi! u < x= Tuu for all x X \ [Wa), yiclding that vo < v/, u for all b AA with the # vaa follows that dim(C.) = d, where dim(S) is the dimension of the affine hull of S, since we can construct small enough Euclidean ball around where the same condition holds (recall that A is finite). Conversely, dim(Ca) = d implies that a is Pareto optimal. This is because th can be written as convex combination of points in X' \ feaa. then for every such point 4/s (with positive weight), (V.- 4/,, E) = 0 for all é E C.: hence, C, cannot be mull-dimessionl..
The polytope V induces graph (the 1 1-skeleton of V) whose vertices are the vertices of V, two of which are adjacent in this graph if they are the endpoints of an edge of V. Two non-duplicate (i.e., having different features) Pareto optimal actions and b are said to be neighbors if th and th are
22

---

adjacent in the 1-skeleton of V. is known that this graph is connected [5]. For any two neighbors
and b, it holds that tim(C, n Cb) = d 1. This is true since
Co
{e R (+0 1h. C) = 0 and Ve E (v. Se. E) =0]
A is finite, and the fact that there exists (by virtue of th and the being endpoints of an edge of V) a vector u E R such that v. u < x for all x E V (b, 46] (which also excludes duplicates of a and b) and th u = big u. Conversely, if dim nC2) = d - for two Pareto optimal actions a and b, then they must be neighbors. To see this, note that each E C, n., can be mapped to face of V containing both Vaa and th,, in addition to points x E V satisfying (x, f) = (Wa, f). Since the intersection of two faces is also face, the intersection of all faces containing th, and th, is still face of V. If a and b are not neighbors, this face must contain some vertex the different from tha and t/b- Therefore, for any / C. n Co. (Wer () = (va, E) (viz, f). implying that dim dim(C, n Cb) I d since Va. Vo, and the are affinely independent being all distinct vertices of V. Lastly, for neighboring actions a and b, define their neighborhood as
Na.6 == {o E A 1/c E [Wa vall = fc E A the = ove + (1 - a)vb a E 1]] which includes the duplicates of a and b. (Note that the neighborhood relation is defined only for non-duplicate Pareto optimal actions.)
Recall the definition P())= == {a E (b. vh, l) S 0 for all b E A) for E E Rd, extending to sets D C Idd via PD) == UtED Lemma 26 in [31] shows that local observability as defined via Definition 1 is equivalent to the more usual local observability condition used in finite partial monitoring. The following lemma expands on that adding two more equivalent conditions, one of which was featured in Lemma 4.
Lemma 5. The following conditions are equivalent.
i) For every convex set D C IR
t/a whb E span MM | c P(D)) for all a, E P(D).
ii) For any pair of neighhoring actions and b,
V/- th E span{Me c No,bt.
iii) For any Pareto optimal action a, E IRd, and a" E arg min W.T.e,
Va - va- E span {Mo WT S v5
iv) For any pair of Pareto optimal actions a and b, and any l Rdd, Va 1/b E span { MM w. / & max v. e, 2/ f}}
Proof. i) ti) This is given by [31, Lemma 26). (Note that, unlike [31], our setting allows duplicate actions; however, their proof extends immediately to the case when duplicates are present.)
i) = ii) Since is Pareto optimal, vaa E exx((V), implying that (Wa) O co \ (waa) = 23. Hence, by the separating hyperplane theorem, there exists a vector u E Rd such that ei_ v < x u for all x E X {wa }. yielding that wt u < between and f, i.e.,
vh u for all b E A with the # vaa Define E as the line segment
(C' E Rd l' A)e+ + Au, A 1J.
Now, considering that a, a E P(E), Condition i) implies that
Va via spanç b P(E)).
We now show that for every b E P(E). vo S v.T from which the lemma follows directly. If dhb Vo. the inequality holds trivially. Suppose
that v/ * vha By the definition of Th Tu u < Vo v. Hence, since E P(E), we have that for some X E 10, 1).
(1 A) T S Aup v Auh T S. Dividing by x (note that À < 1) gives that v/T f v.T l as required.
(1 - A)4
iii + iv) This can be seen immediately upon writing vha v/b = va va- (wbb - Va-).
iv) + ii) For neighbors a and b. [&, vol is face (in particular, an edge) of the polytope V; hence,
there exists E R and E Rd such that x TE = r for x E [va: the and y r for E V \ [Ma th). This gives, via the definition of Na.b, b. that for any e E A. vo l S max (1b e, wo l) = c E No. which established the sought implication.
23

---

C
Auxiliary Results
We will use S in the following denote the of (symmetric) positive semi-definite matrices R=x" while = will refer to the Loewner order: for any F,G St F G is equivalent to
F G
Lemma 6. Let and m be two positive integers, and let V be a subspace of Re Then, the mapping (X, G) > X G is convex on I x {G E S col(G) V} with respect to the Loewner order.
Proof. This a direct consequence Theorem 8 in [47].
Lemma 7. Let n and m be two positive integers. For F,G E St and X E Ru such that
(X) C col(G), it holds that
Proof. This direct consequence Theorem 5 in [12].
Recall that for Dg and 6 (0,
Q(=) = Σ aaaM
and Qs(z) = Q((1 6) + 01x/k).
REA
Recall also that U [d)rk(M) matrix whose columns (4)) form an orthonormal basis for cM)(M), with M being the d x (E. n(a)) matrix obtained by horizontally stacking all the observations matrices (Ma)eEA. Now, for E As and d E (0, define
B(T) = Σ
= U QTT(U and B^(r) = B((1 - 5) + 51z/k). (8)
AEA
Finally, recall that given finite index set Z and collection of matrices (X, 2 Z). all with the same number of rows, we denote by span ( Xx, E }} the span of all their columns.
Lemma 8. For any As. (=l(((=)) = span Ma x(a) > 0}.
Proof. Letn = EOEA Dai Ur be the n-dimensional vector constructed by concatenating the vectors VT(a)In(a) in order, and Dx be the n x n diagonal matrix with u on the diagonal. Note then that Q(T)) can be written M MD²M" Hence,
col(((=)) col MM) col(MD,)) = span Ma TTa)= > 0}
Lemma 9, For any π E Ag. the following conditions are equivalent.
span Ma (a) > 0} col(M):
ii) col(Q(=)) = cM)
iii) B(T) is positive definite;
iv) span UT Ma ((a)= 00 RR:(MM)
Proof.
i) + ii) Follows directly from Lemma 8.
i) + iii) For any nonzero E (Rrk(M)
T. B( TU
- T(a) UM
24

---

Note that Uc # O since U has full rank, and Uc E col(M) by the definition of U. Hence, thanks to Condition i), M,Ue # for some a A with x(a) 0, yielding that ΣaEA ((a) M| Uvl
iii) + iv) Applying an analogous argument to the one used in the proof of Lemma 8, one can show that
(Ol( = span (U T Mo (<(aa)) > 0}
The required property then follows since col( RR by the assumption that (TT) is positive definite.
iv) i) For any E Rd Condition iv) implies that U x E ( can be written U EaEA U Ma for some collection of vectors (Va)aed such that va E R²(a) and 2 O whenever T(a) = O. Now, take to be in col(M). Since col(Ma) E col(M) and UUT is the projection matrix onto col(M), we obtain that
== --UU x= EOU
Ma = Σ Ma
aEA
acA
This shows that (ol S span Ma T(a) > 0}. The required property then readily follows as the converse statement trivial.
= Lemma 10. Fix some As such that ((x) is positive definite. Then, U =
Proof. For brevity, let Q Q(T). B = B()), and X = UB- Also, recall that B = U QU. Since U has orthonormal columns, U I M) and UU is the orthogonal projection matrix onto (U), which coincides with col (M). Additionally, note that the row and column spaces of Q the same thanks to symmetry, both of which also coincide with col(M) via Lemma 9. Hence,
QUQ.
UBUT T UUT QUU =Q
We now prove the sought identity, that X = by verifying the MoorePenrose conditions:
QXQ = UBU = U = =Q, = UB UB- X:
xQX = UB 1UT-UUBBUUUBBBB
(QX)T (UUT)"=UU) =UUT QX,
(XQ) = -0TT)T=UUT TU = =XQ.
Lemma 11. For any A₁ and 8 10, it holds that col(Qu(z)) = col(M), Bs(T) is positive definite, and U BB(x)-LUT (s(
Proof. As (1 8) + 81g/k /k has full support, the requirements follow from Lemma 9, Lemma 10, and the definitions of QT(T)) and Bs(T).
Lemma 12 (Extension of Theorem 21.1 in [35]). Define the functions f,9: Ae 1-00, too| as
((T) = loog det B(T) and
g(T) = max ir
-10 Ma).
aEA
Then, for any nt E As. the following are equivalent:
i) x" is a minimizer of g:
ii) π² is maximizer of f;
iii) g(T") rk(M).
25

---

Proof. For brevity, l == rk(M) and ga := ( Ma) for a E A. When Bx))
iol--condiiioned, f and 9 map to -00 and +00 respectively. can be verified via standard arguments that f and y indeed attain their maximum and minimum respectively on As-
Via the definition of B (see (8)) and the fact that d(log det X) txXX- we have that
(VS(T)) = tr (B( U" M. tr Using the linearity of the trace, we get that
M.) (T)
Σ T(a) (Vf
Σ x(a)ga(T) =tr (B(()) Σ T(a)U' M.M = tr( = rr
aEA
aEA
aEA
ii) i) By the concavity of f. the first-order optimality condition gives that for any π E A..
0 z (Vf(T") x n²) = Σ x (())
Taking π as Dirac over some E A gives that (a( ) S r: hence, g(TT)) < r. However, for any и Ar. g(T) 2 EnEA T(a)ga (T) = r, so x² minimizes g and minre ((T) = r.
fii) ii) If g then go (TT) f for every A: hence.
(Vf(="),
Σ - -
AEA
for all ι E Ap. The concavity of therefore implies that x² maximizes f.
=> iii From the first part we know that minged. g(T) r; hence, n², being minimizer of g- satisfies g( = T.
Lemma 13. For any p. q E As. holds that
a(a)g(b)(V - vt)) Qo(p) 21) = Σ " aEA
Hq).
a.bEA
Proof. Note that via the definition of H, we have that Hq = ((b)//. For brevity, let X = Qi (p))t. t. It is also noteworthy that the only relevant property of Qp(p)t here is its symmetry. Starting with the offthhand-side, we have that
Σ a(a)g(b)((. w'n) X(va - :b)= Σ a(a)v X -2 Σ ((a) X a.bEA
aEA
a.bEA
= Σ a(a) X - 2((H)) XXq..
.EAA
where the equivalence of the two cross terms the initial expansion follows from the symmetry of X. Next, expanding the sigt--had-side of the sought equality yields that
2 Σ (v.. Hq) X(#a Hq) = Σ g(a)o
X -4 4 Σ
a(a)o. XHq T X
a
aEA
aEA
2 Σ
q(a)v. Xtha - 2(Hq) XHq.
aeAA
which concludes the proof.
Lemma 14. For any p. E AE. holds that
Σ q(a)(va - T Qo(p)) (va Hq) min AEA
Σ - Qa(p) - rEAi aEA
Hr).
Proof. Define F: A+ + R such that F(r) = Enea ((a)(t. - Hr) Qo(p)t - Hr), which is easily seen be convex (Qo(p) is positive semi-definite). Its gradient is given by
F((r = 2H Qs(p) Hr - 2H Qs(p)* Hq.
This clearly vanishes when g: hence, via the convexity of F, it is minimized at g.
26

---

D Proofs of Section 3
As a starting point for the analysis, the following lemma states a standard result for exponential weights. A proof can be easily extracted, for example, from the proof of Theorem 1.5 in [26].
Lemma 15. Assuming that at every round i, ni: (a) 2 holds for every action a, then, for any a" E A", the sequence of predictions (ge): defined by (4) satisfies
T 6ar 1=1
Di) log k
T
Σ (9.
+
Lemma 1. a learning policy and define pt as the law of A, conditioned on Fi-1. Let qt be given for some learning rate 1l > and sequence of surrogate loss functions (Wi)) such that i/. IR
is Femeauurabe and satisfies max.cA (n)) S 1. Further, let a* E arg min Et= Ve(a). Then, the regret of the policy satisfies
log k
RT S
Σ 1=1
E ((Pe qc: Mel + 7/e. E,Di) + (gc Co- Ut E,De)]
Proof. Firstly, we have that
Pr
E
ye (Ae) ve(a")
E
(pt Car yi)
T
T
E
Σ (p- 4t we) + Σ
lat
Ca- Ut) +
Σ (q:
Car Ye - Te)
where the second equality follows from the definition of pt. the linearity of expectation, and the tower rule. Next, we apply Lemma 15 to the middle term (nee(a) 2 -1 holds by assumption) to get that
log k
T
T
Rr S
E
Σ
(p gt, w1) 1 Σ let D2 +
Σ
1/ ear W/ Tr)
log l
(p: gt Wt) + T/ges E.Wi) + (ge Ear, yt Ee0i))
where the equality is another application of the linearity of expectation and the tower rule, using the fact that qt is F.-1 measurable as it only depends on (-.)
Lemma 2. In the same setting as Lemma 1, let the predictions of the policy satisfy pt (1 8)p: 0l./k / for some E (0, 1) and ps DEs and let the surrogate loss functions satisfy D. ge ( Ae, Φ+) where ge(a, Φ) = (I+ 1x
(( M. Then, assuming global observability, it holds that
log k + 28T +
T
RT <
E
2. H (,) + +m= Σ (a))) - To(l))) (vb, vo) Pt
1
a.EE
provided that bax (W 4b) (T((())) ( - 4/6 max.e IlMe Qs(pe) Mella S qp where
1w0b (..p))) {
< max MM. E|l.
W =
sup a.b.cEA PE LEC
(TTxst) vc)l
.EA.EC
Proof. Fix some a" A'. If [lac(A,, Dell s -1 holds in all rounds, Lemma gives that RT S n - -log k + Σt= ET, where
T = (p- - qt H T (,) + ( E.pr())9:a,, MT (TT) + + - - ea- Ho, HT AT4-- (a MT
27

---

Concerning the third term in (9), we have that
Eadi(a)ge(a, Ma 4))
(Ix 1s9, H Q(:i) (an))aa((MMMM))
= (Ix 1x9,) H Q(M))
(Ix 1.g.
(Ix 1.9. ) UUT
(Ix - 119.))
where U and Bs(-) are defined in Appendix C (see (8)), and the last equality holds since each row in (Ix Leg ) H is convex combination of vectors of the form v. thb with a, b E A. which, via global observability, belong col(M) onto which UUT projects. Hence, get that
(qt e , la ExPr(o)gr(a, ()) = (at Ee. T (Ix - 114 ) Tn)
(q: Ca. 1: H He))
0
using in the last equality that gt, ca- E As and all coordinates of lage H & are identical. In what follows, will refer the individual coordinates of ge(:;)) as di gb(b; :.) for b A. Shifting the second term, fix E A and observe that
E.Pi(a)g((;; a, M ExPe(a) - Hq) 16lh 2,)²
[V -
w (. wwll
w² (.(0(0)).000(>>>)>>> (,) M, -h0
w ". - (00
(v' 4c)
(c)((()) - v.)) (Q. we)
where the first inequality is an application of Jensen's inequality, while the second incquality follows from the definition of w.
As for the first term in (9), it is immediate that
(p. - 4z H TT {2) = 8(1x/k /k: 9e, H HT4) + (1 61-6 - q: HT4) S 26 (7r - qt: H (e) where we used the definition of p. and the assumptions that ma 114. v)b) Te s 2 and E 10.
Finally, we examine the boundedness condition. Fixing a, 6 E A, we have that
ge a, M, te)
1(1r Hq)) M.. &el
= la. (Vol, - H) Qo(m)) M.M, &
< Ea eel
s ~ E.a(C)lM[]((( (2 (Q>(7)))) 1/2 (2(b/b w501
< w E.alellMM. ("("I))"""(((("""""""""(""""""""
(11(((((())))) 1/2 (vo - -b-ill
"
2 Ee((c) (1IM. (Ca()))))))))) 1112 (QQ(())) 1/2 1/2 - -coi
(INM Qo(T.) Mall + max (vb- Tos vbo) IA WIE
cEA
where the first and second inequalities again follow from Jensen's 's inequality and the definition of respectively. The required result now follows from Lemma 1.
Lemma 3. For any nj > and g E Ag, it holds that
A
max min An, (p, e)
LEC PES,
28

---

Proof. Recall that
(p, () = (p q, H E) 1,2 o,BEA
1
Σ
{(a,)())((a.bb.))
7)
for DR. and & E L; and that for any a, b. A,
E(a,b:p) (ta - vb)² Qo(p) (Vo vb))
Also, recall that Egy = {p E 4:: z(p) - 2/nL). where
(p) max E(a, b;p) + max MM Qs(p)t Melp22 a,PEA
cEA
and that A = minpe=, maxsec (p, t).
We start by showing that for fixed pair (a, b) E A2, E(a, b) is convex in p. Via Lemma 11 in Appendix C, co)(Qs(p)) = col(M) for any E A Hence, the convexity of & in follows from Lemma in Appendix and the fact that (s(p) is affine in p. Moreover, for a fixed c E A, the function p + || (p(p) Mellz can also be easily shown be convex by invoking once again Lemma 6 and using that (p) is affine in and that the spectral norm is convex and non-decreasing in the Loewner order. Also note that both functions are continuous as the rank of (s(p) constant for any A& (see Corollary 3.5 in [52]), simply via the continuity of matrix inversion since (x))) BB(p) T and (p) (defined in (8)) is positive definite for any p E AІ as asserts Lemma 11 in Appendix C. Hence, the function is continuous and convex in E Ak. and its sub-level set E {p E Ax: x(p) S 9/12) is convex and compact.
The arguments above imply that for fixed & L. p An
(p. () is continuous and convex over the compact set E,- Moreover, for a fixed p E Ag, E Ap E) is trivially continuous and concave the compact set f. Therefore, Sion's minimax theorem [51] asserts that
min max Ag (p, C) = max min Am.app e). PEE, REC
EEC PεE,
The theorem then follows from the definition of An.9'
E Proofs of Section 4
Lemma game is locally observable if and only if holds for a E A', E Rd, and a" E arg mi & that vho -/a E span { {M, v/ l S vo f).
Proof. This follows from Lemma in Appendix B.
Before moving on to the proof of Theorem we define an analogous set to Wolcc that does not take the losses into account. Recall that global observability implies that for any pair of actions (a, b), there exists a (not necessarily unique) weight vector E R" such that &. - Mv. The following is the set of all possible action- oetion-ppir-voe pair- wise assignments of such weight vectors:
MuRlo = {E = (Ea,bla.bE E R k
Va, E A. vo sb = ME
Recall that
Agla == max
min Ce Bo-v,=Mu Mu
E1r(e))l-
a.EEA vER":
CEA
The following lemma provides slightly different characterization of Aglo featuring Wyso, Lemma 16. It holds that
Aglo
min &EWid a.bE
max
Σ (a, cEAA
Proof. For a, b A, let oh refer to an arbitrary member of arg min whe wo- My Eeecllo(c)] Via the definition of Walo, (aabee E Walo; moreover, it holds that (o ( e arg argmingewat Exsallea.s())) for all a, E A simultaneously. This implies that (w arg millgwwd max.,bEA EceallEa,(e)) concluding the proof.
29

---

The following lemma relates Pglo and Bloc. Lemma 17. holds that Bglo S Broc-
Proof. Recall that
Bloc = max min max
REL XeW acA
cEA
where
W = {a- (Aa)aEA- E R Ea* aargin Te V(a, A" xA,
CEA
va - Va = MA2 and (a + + vs v.l.v
Additionally, define
W = { = (Aa)aEA- E R² xn 3a" E arg min wh e Va E AA" ,/4 v.- =Mra
cEA
for l E and, with some notation abuse,
W = =AaaeEA E =k*" xn Va E ,", - -W0 MA
for d' E A" Then,
Blor max min max
EEL XEW aE
min
EEL XeWele dE
cEA
max min max
(c)l
bE Xewele aEA
max max min
Σ
Ax(e)l
DE aEd AEWElo
max
min
[[(c)]
a.BE.A' w to vo My
where the first inequality holds since Wole C Wit Concerning the second inequality, argued in the proof of Lemma 5, holds for any Pareto optimal action b that { coo(X (1a)) } = ø (since v/b E ext(V)); hence, by the separating hyperplane theorem, there exists a loss vector l E R such that v/ l, < x &, for all X \ {1b)). yielding that only and its duplicates can minimize e T5 la over A. The inequality then follows by restricting the maximization to any selection of loss vectors of the form (fs)bE and using the fact that Myslo Weglo
On the other hand, we have that
Aglo=
max
min
Σ |e(c]]:
A.bEAA wER": W. dyy M
hence, showing that the maximum on the right-hand side of the equation above is attained by a pair b E A" suffices to conclude the proof. Let a, b E A be two arbitrary actions. By the definition of A" there exist two probability distributions p1, P2 E AE- such that th ΣneA Pi th and R/ ΣneAr P2(h)uhn Then.
Va 1/6 Σ (h)uh
Σ JEA
Σ RJEA
pi(h)p2(i)(1> 45),
hEA-
30

---

and Vo Hence,
v/ = M EAjEA P1(h)p2())0 with wiis eag t4 pa-V5 a--v==aa Eccallo(c)]
min
Elbe(e)1
Σ
vERt: do Vh MD
CEA
cEA
1 Σ p1(h)p2()
Σ
A.jEA'
cEA
< max R.JAA"
|
cEA
= max h.jEA' vERn: th,
min
|o(c)ll,
M CE.A
where the second inequality is an application of Jensen's inequality. We have thus shown that
Rglo max a.bEAA wERn:: Pa th
min
Σ [|((e)] S Bloc-
The proof of Theorem relies on the following Proposition. (The definition of B()) is given in (8).) Proposition 3. Suppose that the game locally observable. Then, for any L A W/o. and & W it holds that
M, )( Moll min (p, 8L233 Σ (b) PEE,
DEA
2T ( min max M. UB(())"U Mell
mED:
provided that 1/n 22 (2) min max #EAr CEA
M, UB( UT Me where
S* = max aEA*
8 = max a.EEA
Eee Sea,All and
Au (b)ll
(b) q(b)) 1 0]
Σ
g(a)
Ereall da (c)l
rEAt: 7.
92 (b)
Proof. We show this by constructing a certain distribution E E. and bounding An (p, E). Our choice of p will take the form p = 7 (1 DD. with 7 E (0, 1/2] and π, E As. For brevity, let 7=1 - 7. The role of π is to ensure that 7 + 70 E E, and that of p is to control the magnitude of An. + Tp.() f). Let
arg min (vaa,, E). Now,
(TT + +, = 1 ( - q, 1 2) +
] i q. 11
T
L
Σ
((a))(b)((a, b; +
a.AEA
< 27 + (p q, H
2) + I?
Σ
1 "
a.bEA
< 27 7 (p q, H E) 2L
Σ
a(a) 7p)
(10)
n
where the first inequality uses the assumption that max,, (4/a - 1/) S 2, and the second incquality follows from the definition of E, Lemma 13, and Lemma 14 (noting that E(a, ap;p) (vh He ) "s(()) (s/a He.-) )). We now proceed with the selection of f with the purpose of minimizing the second and third terms. A convenient choice select p so as to perform better than q against the loss vector f. For that, it suffices to consider P of the form
P Σ a(a)va such that Va E A" (Va ca, H TT,, S0,
(11)
31

---

where E As. That is, i a mixture (with weights proportional to q) of | distributions, each associated with Pareto optimal action and is chosen to outperform this action against L. This choice allows us to simultaneously eliminate the second term in (10) and bound the third term independently of tunable parameters. The former fact is easily demonstrated:
1 2 20-2HH H. =2==2 2 Σ
(a))(a - ca, -G, (T 5.
(12)
"EA"
Moving over to the third term, fix X Whe such that Vo Va. M for all E A", which exists via local observability. Then, for any a E A" and any p E Ac. we have that
E(a, a:p) = -Wa--va. Qo(p)* (wa- - voa)
= -I((6(p))) ( (w%
ECEEd (Qo(p))) 1/2 (c)l
E Eccal((s((p)) (
< Ee (.
Ela Σ [IA.Celll((sse1]] y Moll"
(13)
where the first inequality is an application of the triangle inequality, the second consequence of the definition of the spectral norm, and the third an application of the
inequality. Hence,
Σ g(a)Ela,a': :p) = Σ a(a)E(a,a') aa))
aEA
"EA
Σ a
(14)
cEA
S max NEA"
(E (A.))I))(())I)
Σ ((a)
Σ
[c(ee)ll 1/2 "M,]'
DEA
cEA
= max (ECEalA,(()))
Σ Σ
1/3 Mall
=EA-
CEAREA"
max "EA"
(cE))IA
Σ
a(a)
max EseAl>x.0 (Qo(v)t) v/ Mall
[aa())l
cEAGEA"
< max ( (cEAllA,(()))) =E
Σ Σ
((a)
EbeAll (b) || (Qx(z)t) V M..l" (15)
[aa())l
CEAREA": Aoyo
where the first equality holds since q is only supported on A Note that the right-hand-side of (15) now offers natural way to choose P as to respect the constraint in (11) I) and simultaneously simplify the bound. Simply, let U2 A (as referred
in (11)) be such that (b) x [b>a(b)]] for b A if A * O; otherwise, if X = 0 (which is the case for a and its duplicates). simply set Va = ea- This choice satisfies the condition in (11) since the fact that support of Pa has loss smaller than or equal to that of a. To emphasize its dependence on À and g, we denote this choice of p by q². For clarity, we state its definition explicitly below: for E A, let
Wolce implies that any action in the
[ba(()I
(b))= = Σ ((a)
[A_ = 0, = b] +1 + 0]
Σ EoEAl [aa
ac
(b)ll
= =0 +]+ Σ
g(a)
EoEA [ca())]
nEAA: : Ao 0
(b)
32

---

For convenience, we have also defined above an abridged mixture q², which excludes actions E AA
for which A O. Now, with _x m EcEAl (c (15) implies that
Σ q(a)E(a,a 1YT + = - 8
(b))l + )T) V Mbll
EEA
PEA
2 (b)llMM Q6(TT + /
DEA
B
M. (((A))
8)(1
DEA
- 433
Σ 2 (6)
M2 )
MEA
where the penultimate step is an application of Lemma 7 using the definition of Qa and the fact that (Mb( S )()( whenever (b) > 0 (see Lemma 8), and the last step uses that d, 7 S 1/2.
Hence, combined with (10) and (12), this entails that
27 A 79 1) =
+ 8L
Σ BEA
((
(16)
7
The smallest admissible value for y depends on the choice of n, which should be chosen so as to ensure that (лT + ) E Enj that is, z(γπ + = S 2/nL. Now, fix & E Wulo and define Se == be Eceull (()())))) Analogously (13), we have that for any a, b E A.
b + 77)) <
1/2 (( + +7 )t) M.Il
max (Qo(1T + )10")) "M CEA + + Moll?
2 max
(17)
CEA
Then, enforcing that col(Q(=)) = col(M) we get that
2(7ग + --0))= = max 8(a, Yπ + ) + max (exx)((Qan) (Q6(7T + + Va Mc]l²
a.EEA
CEa
- (1 + 32)
max cEA
(Q6(7T + وgン))) 1/2 Moll
$ (1 8)7
(1 + [
max c
(Q(+)))) V/2 Mcll
s (1 + (
2
max CEA
(Q(+))) //2 Mal
(1+ + B
max CEA
(UB(()) 1/2 Moll"
(18)
where the second inequality follows from Lemma 7 as (MM S col(Q(=)) by the assumption on t, the third inequality holds since 5 < 1/2, and the last equality also follows from the assumption on (see Lemmas 9 and 10). At this junction, we pick
π E arg min max || (UB( 12 Moll" n'EA, cEA
which satisfies that (Q)()) = col(M) as this is equivalent to B(T) being non-singular, see Lemma 9. With this choice of ग, equating the right-hand side of (18) to 2/4z dictates setting
7 n 3
min (UB(=")-UUT) MM.. r'EAr asA
To ensure that this choice of is valid (i.e., 7 - 1/2), we enforce that
1/n 2 21(1 + (2) min max max[(UB(+))-oTT) Ma
''E d
33

---

Plugging this value of y back in (16) finally yields that
min (p, 8L233 (,,)),,
M Q(a
BEA
+ 2L 22 (1+11 (2)
min max m (UB(7)- "2 Me 1|? r'E CEA
Theorem 1. In locally observable games, it holds that
A I max inf FEC XeW
8L2 min (rk(MM, supp(A)]) + 21 (210) min (rk(M), w*}
provided
1 2 2 (1 + ( min {rk(M), w²) where 8glo = max
min
Σ
[e())
1
0.6EA WER": 19
cEAA
and w"
min SEA
[S]
max DEA
M3 U( U) UT U sk.
Proof. Fix l L, 9 E Ag and Who Concerning the first term in the bound of Proposition we have that
Edead (G S EsENq (OIIMMTTOGA)MM
EBEAT (U)
+r((Q(a)) " (b)MM(() =((() rk(Q(rA)) S rk(M),
where the last inequality follows from Lemma At the same time, whenever (^ > 0, an application of Lemma gives that
M (M,T) Mbll (^(b)
||ar Mo (²(b) <>
MM of < M (((M) Mall
where the last inequality uses that Mt Mo is an orthogonal projector. Then,
(b) (b)
Σ (b) Q(1)) M( BEA
Σ
< A: o (b) 0} = |supp(A)]
BEA: 9- (8)20
For the second term, setting æ as the uniform distribution over some S C A (assuming EeeSUT M,MMUU is invertible) gives that
max MT MMJUB(T)-LD) M bEA
|S| max PEA
IM,U (TM M.M.U)--UTM.
Hence,
min max (UB())))00 TUT Mb min
IS max M, U'ErESU M.M.U) "MM Myll = n
mED: BEA
SCA
Note that for any E A. the norm on the right-hand side of the inequality is bounded by whenever b S (again via application of Lemma above). Hence, choosing S as A yields ie as upper bound on w". At the same time.
min max M, UB(m) M,| #EAL BEA
min maxtr (M, UB())-U(T-- M,).
SE BEA
The right-hand side is form of the G-optimal design criterion (with matrices as elements of the design space), for which one can show that the minimizer coincides with the maximizer of log (Et(E T(a)UT M.M, U) and attains value of rk(M). see Lemma 12.
34

---

Let Bglo == gewao Pg. Combining the four bounds derived above with Proposition 3 (which holds for any A W and & E Weloo and Lemma 16 gives that
min (n.(D,() S inf ST,283 min {rk(M): (upp())]] + 2T.11 + .glo) min((r(MM) ww) swW
PEE,
as long as 1/1 2 21 + 5 (rinrr(MM) w* Taking the maximum over E C in this bound yields an upper bound for A via Lemma 3, which is also an upper bound for A,, as it does not depend q. Finally, note that the image of the map l + W/ec is finite as Wher depends on l only via the ordering induced by the latter over the actions; hence, the maximum value over E C of the bound above is attainable.
E.1 Alternative exploration distributions
We revisit here the key argument in the proof of Proposition 3; that of choosing p to control EaEA ((a)E(a, pD) while keeping (p q, H non-positive, having fixed L and a" arg min 4. f. As argued in that proof, for any choice of X E wiie (such that v/. -.. MX, for all E A), choosing p -acA-- {(a)v, with Va supported on supp(X, a) suffices to ensure that (p (p-q, HT&H f) I O. On the other hand, establishing an upper bound E(a,a";)) that is proportional to ) (a))) (c] Qs(ā) Mell allows using the fact that EeeA r( Qx(r)* Mall is most 2rk(MM (M) for any E A& (also, at most twice the size of the support of r) bound EnEA ((a)E(a, a"; p)) as such (see the proof of Theorem above). A slight generalization of an argument in the proof of Proposition 3 gives that for any a E IR and E A (with A, + 0)
Ea, a" ; = (tha - )a-)) T !o(2) (Va -Wa))
(I(2c(0))) V2 (vo - )1
(1()(()))) 1/2 MX 1
1 [Ecesupp(A, (Qx()))) 1/2 M, M.A. (c)l
(cesmpp(A (1 (=(P))))* McAa
E (cEsupp(A.
( (x( 1/2 Me (c)l1
EceRuppiA a)
A 2c)]1 2n)
(CEESup(AAaa A (a]c)) (F()
E EcEsupp(A.a) Au (c)ll--20) (Ecssup(AAa)) Da (c)
|| (c) 2a
M.. Q6 (o( (cgsupp(A.a) Exesupn(X.o) > (b)
where the last inequality is an application of the Cauchy- (c) x [c)())]2a where a = 1/2 corresponds the choice of v, used the proof of Proposition and a 0 yields (c(c) x [[c E supp A, a)]. which is essentially the analogous choice of p to that used in the analysis of Lattimore and Szepesvári [40] finite partial monitoring. In any case, the resulting bound is
incquality. One can then set
Σ (a))((aa'i))) s Σ Ecla)(EnsuppAA.no (c ( (Eoesupp(A,o) (Aa(c))122) aEAA
aEA
(celll( (.(0)
max asA-
Eneampp(hi 2-) (Ecesupr(A.)) [c) (() (x(P) Moll
Since for any a the Cauchy-Schward inequality gives that
Ec (a 2-220)
(0) (Eeesupp(A.e) AAa(c)) (c | (e))))
35

---

choosing = 1/2 minimizes the leading factor in the bound above. To be clear, it is not claimed here that this choice of & minimizes EaeA q(a)E a"; :)), neither under the structural constraint that P EusA- q(a)va with Va supported on supp(>, ( a) nor the general constraint that (p-q. 9. H E) & O, neither for a fixed q nor after passing to the sup over q E A. It is not generally clear if such an optimal distribution can be expressed in closed form. The aim, rather, was to show that our choice of is fairly natural and justified in pursuit of a simple and interpretable bound (one that isolates in standalone leading factor the 'cost' of using the weights (Aa)a) through our thnear-bandit-inspired analysis.
To expand on this discussion, we consider now a special case where a tighter analysis leads to a different value of a being the most convenient. Assume that col(M and col(M)) are orthogonal for any b o c. In such a case, it holds that
E(a, a :)) = (Va- The) T Qo(P)* (Va- - that) (Ma Qb(7) (MA.)
(COESUDDAA Meda(c)) (c)) (Ed MeDale))
EcEmupp(A,a) (M.A( (2((0) (M))(())
Eeesupp(A || Qs())
[|a(()]]
(Ee Esmp((AA))) Au (c))) Σ bbssupp(A.a)
(b)12 M (a(P) Mell
where the fourth equality follows from the assumed structure of the observation matrices. This immediately suggests setting (c) x [|Ax(c)] (or picking a = 1), obtaining as result that
Σ q(a)E(a, a"; p S max (Eneeupp(A.a) || Aa (c) aEA
Σ p(b]|lM Qs(P)) Mbll,
.EAA.
be
which features a better leading factor than what we obtained with a = 1/2 in the general case. Again, this choice is not necessarily optimal in any precise sense, but it allows exploiting the structure of this special case in a simple and natural manner. Devising a general choice of p that can recover improved bounds in special cases such is a worthy direction for refining the bound of Theorem 1.
F Proofs of Section 5
The proof of Theorem relies on the following proposition. (The definition of B(-) is given in (8).) Proposition 4. In globally observable games, it holds that
+ (2))) minTeA, max M, M,
Ar < 1V L min
(1 + 32 millreay M MTUB(T)--UTM M
provided that
(1 + /go) minges max M, M,U(())-IUU Moll
1/12 2 (1 1.3) min
(1 + 32 glg minres, UB M
where
32 = min max
||
max DER": ca V.=Ma |||||
min
max a.edA
M (va. - v/))ll
gewalo ab
Proof. Fix E L and E Aj. As in the proof of Proposition 3, we choose a certain distribution
p E E, and bound An, (p, f). Here, we simply set p = 7 + (1 - -7)g with 7 E (0, 1] and т E A
such that col(Q(=T) col(M). For brevity, let 7 1 7.7. With these choices we obtain that
An + 79, f)
? (T q, H.H. E)
7 2/g q, H L? Σ ((a)g())((a) km + +99)
17
a.eEA
s
2y
I Σ ((a)((b)((a) u, +5)),
(19)
7 a.AaA
36

---

where the inequality uses the assumption that maX,, DE. 11 - [ 2. Fix some & E Wyeto which exists via global observability. Then, similarly to (17) the proof of Proposition 3, for any b E A.
ba by y + 74) - 3
max cEA
(Qo(1T =g))))²
(0)))2MM)) Moll*
1
$
max CEA
Mc Me. (T))TTm
8)7
$
22 CEA
max
M.. ((=)
where the second step follows from Lemma using the assumption that col(Q(m)) co) and the last step uses that 5 < 1/2. Then, choosing & E arg mingrewete 3gr we get via Lemma 16 that
Σ a.bEAA
g(a)a(6)((a.::47 + +70) - Bg. max My Q(T) tEA
2
7
2
(1 B
maxl| My Q(T)
7
BEA
Alternatively, for any & E Walo, we also have that
E(a, 7 7tt + 54)= (Va vhb) Q5(TT + 54)² (ta vb)
11(Qs(77 + 59)") 1/2 (d/a (b)-"
|1(Qs(TT+ + +5)) 1/2 ME,,.11
S ([ + + M|
2 11 Q(T)
again using the assumption that (Q(()( co)( With & E arg mingeeeee ma we obtain that
Σ ba)) 0
+ S b
B M M(T) & (1 31, [
where
32 = max M - -/)il a.PE
max a.
min -
|||||
min max |6,,b]]. SEWe a.EEA
vER
The first equality follows via the minimum norm property of the Moore-Penrose inverse, and the second is due to the structure of Vyelo (see also the proof of Lemma 16 in Appendix E). Let
(T) (1 (g
max BEA
M, UB(()
UMoll
and
U2( = (1 m2 UB( M
Returning back to (19), we have shown that
27 + r min min (T)( (2(m) ( + E) s
"
This expression is minimized at = vTl. ( (v((m), / 02 (T(TT) yielding that
Ayg + + E) < 4 L miiiii/(ul [2(
For 7 hold, it must hold that
1/n 2 minfei (T), v2(m))
37

---

Consider also that
= 74) max E(a, D; 7 + 79) max M Q8(TT + 59) Mell abEA
$ + (g10)
max bEA
M3 MM]ll
And that at the same time,
2 74)
max Ca, /: + 79) + mmxx| M, Qs(yT + 59) Mell abeAA
2
2 7 max| My Q(T)² Moll
82
glol M TNQQQe [(x=) MI|
2
$ [1 + 2 (22 M ((T) M||
7
where the second inequality holds since the columns of every Ms also columns of M via its definition; hence, we can construct a matrix C, with ||Cb|l s such that M McC. have then shown that,
2 =(yx + 74) S min (i (2), (2(2))
7
min (T) (=))
VTL
Therefore, for yor +77 E E, to hold, it suffices that the last expression is no larger than 2/yz; meaning that y must also satisfy that
1/1 2 min 01 (T), (2(m))
Thus, if we pick E arg reA. m (5²), (2()))) " then enforcing that
1/n 2 (1 + I2)) min minfer (2())) (1 I22 min min uz (I()), min (2(TT) nede
rEdx
suffices have
min An. (p.()) VV pE
min min (1 [2((T) xeAx
7
= AV
min min ( min v /2(TT)
17
TE
xEAr
Av L min min Un (T),
(1(
min 12 12(
7
TEAr
TEA:
Since this bound does not depend on or it is also an upper bound for A (via Lemma 3) and A
Theorem 2. In globally observable games, it holds that
A s 4 I/ min (1 + Bgto) (rk((r((M)))))) J. (1 + (2.glo) Vus
provided that
2 (1 + I22) min (1 S Mm)) w } + (2 u²) where
82.gio = max a
M (va- +b)) and un = min
M U (EEssU" MaM UJ - MMM sk. |S|||]
SCA
Proof. It follows from the proof of Theorem that
min max M, UU( M. S mmin(rk(MM), w=)
xE DEA
Similarly, restricting π to be uniform over a subset of actions gives that
min ( M|| < min reAr
|||||M (ZESSU M,M, U) - M = u"
SCA
This is again bounded by k. which is attained with S A. The theorem then follows from Proposition 4.
"Note that the functions (T) and (2( do attain their minimum in n over A.. A minimizer n² of either function must satisfy our requirement that col(Q(xr*) = col( [M) this is equivalent to B(x) being positive detinite, Lemma 9, which is necessary for (TT) be non-singular.
38

---

G
Implementation
Define
(.,g(()) = max An An,9(P FEC
= max
H
H
Σ a.bEA
a(a)g(b)
(v. (b) Qs(p)) (#o - 4%).
REC
"cc(H(p-o)
where og is the support function of L, which we assumed to be compact. In Algorithm 1, we are asked to solve an optimization problem of the following form every round:
min Pn (P), EE
E = {p E DR: =()) S 2/nL},
where 7) 0 and E As given and =(p) max,, E p) + max.c. l| Qx(p) Mall This was shown to be a convex problem in the proof of Lemma 3. Going further, we point out here that it can in many interesting cases be represented
semidefinite program, a well-structured and widely-studied class of convex programs that can be solved in polynomial time via interiorpoint methods [9]. In terms of semidefinite representability, the crucial components to study here are the functions {o, -). M| (+(-))
(- Mcll, and cz(-); that the program is semidefinite representable (SDR) would then follow the combination rules outlined [9, Chapters 3 and 4], which include taking the intersection of SDR sets, taking the maximum of finitely many SDR functions, and summing (with non-negative weights) SDR functions.
Fix some positive integer and a d x matrix C' that satisfies col(C) C col (M), and consider the mapping - ||C (p) for p E As. This mapping. assuming global observability, subsumes the first two functions specified above; namely, p - E(a, b: p) and + ||M. Qs(p) Mell for any a. b. c E A. We show now that the mapping in question is SDR by showing that the set
{(p, G,t E x S R C. Qs(P)'C= = G and ||G|| st)
coincides with the solution set of a number of linear matrix inequalities, where S is the set of symmetric matrices. This is sufficient since the epigraph of the mapping in question coincides with the projection of onto the (p. t) space. We firstly note that the semidefinite representability Ag is immediate; it can be characterized by set of simple linear inequalities. Consider the following symmetric matrix:
J(p G) = (p(()) q
By the properties of the (generalized) Schur complement (see, e.g., [59, Theorem 1.20]), we have that
J(p G) 2 = Qs(p) ł 0,, col(C) S col(Qu(p)), and C CT)s(p)) 3 G.
For any p Ag. the first two conditions are always satisfied thanks to the structure of Qs(p) (convex combination of positive semidefinite matrices), the assumption that col(C) S col(M). and the fact that col(Qs(p)) col(M) asserts Lemma 11. Moreover, it holds that
||G|| St =
G tI and G -t,,
Hence, for p A and G E S",
= J(p.G)z G sI,, and > -tI;
that is, membership in I' can be characterized by linear matrix incqualities (recalling that Qs(p) is affine in p), implying is SDR.
As for ag, consider now the common scenario when L = By(c) = {ee Rd |||]| S c) for some p 2 and e 0; that is, a centered Lp ball. The support function then becomes a (c(x)) c||a||| with 1 1/p + 1/g 1. For rational the L, norm is cone quadratic representable [9, Chapter 3]. hence SDR (note that the input to a is H(p - q). which is affine in our variable and thus preserves semidefinite representabilityy. This also holds when p 1 (g oo) and (q 1).
39

---

Another common case is when L is X², the absolute polar set of X. Here, oc(H(p q)) is the optimal value of the following program:
-(p(e)- s.t. 1 S Va E A.
max
FER
REA
Via strong duality, it is straightforward to show that (c(H(p 4))
min
w
min
(ul + u2) 1s
wERR; H(p Fan
21. H(p 9) M(u ((u--u)
This is the minimum value of linear function under linear constraints, which can be easily incorpo- rated into the full program adding un and U2 as auxiliary variables.
H Adaptive Learning Rate
Algorithm 2 Adaptive Anchored httprratioo-yy-OOimmiiiiiii
1: input: stability parameter E 1/21, sub-optimality tolerance 2 0, scale parameter L 2 w,
2: initialize: 7h = min ( vlog k) (a(a) = 0 Va EA
3: for 1...., , do
4: Va E A, set (a) ix [a E A-) exp((=1x E.=1 (a))
5: choose pa E As such that maxtec Am.g. (pr, E) I Aip. - and =(p() S nz
6: set Pt = (1 - d)p: + 51,/k
7:
execute A, ~ and observe 6: = =,, &
8: Va E A, set Te(a) = (va Hqq) Q(p:)* HQ(p)((p)) ((lp))(Maa) MA.
9: set V max 00, maxeet Am.g. (Fr. )) and M1t1 min B V
log & ++ V,
10: end for
Following Lattimore and Szepesvári [40], we briefly deseribe here 'adaptive' variant of Algorithm that tunes the learning rate in an online fashion, sidestepping (for the most part) the need to have prior knowledge concerning the value of A This variant described Algorithm 2, with the main difference being the of learning rate schedule (me).. k. where Y) is set based the attained values at the optimization problems of past rounds. Note that the algorithm is not completely parameter-free besides the stability (6) and tolerance (e) parameters (which in principle be reduced at will), requires a sufficiently large constant B > O as imput to guarantee that the learning rates are sufficiently small meet the requirements of Theorems and 2. However, can be picked conservatively only affects the regret through an additive term as shown below.
Adapting our analysis along the same lines as the proof of Theorem 6 in [40], one show (analogously to Proposition 2) that Algorithm 2 satisfies (assuming global observability)
Rr S 28T + log K
T
+
E
Σ
m
1=1
11
< 28T + 5E
Σ
V4
log k
+ + max Vi Vlog k + B Blogk. k. LeE(T]
Locally observable games. Via Theorem 1, there exist constants a, B' such that A s a given that 17 < 1/B'. Hence, as long as B 2 B', we have that V22 < A + a $ a + E. Thus.
Ry S 28T +5 (a e)T) log (a + E) log le + Blogk,
where, assuming and e are picked sufficiently small (e.g., o(T-1/2)), the dominant term of order V/Tllog K.
'Nte that for x to be compact, X must span dd.
40

---

Globally observable games. Theorem 2 asserts that there exist constants a, B' such that A - a/ vn given that I 1/B.. Hence, assuming that B z m, we get that
V < Ar, + S af Th + S a/ v + +//ve Th.
Then, from the proof of Proposition 7 in [40] we obtain that
3/3 Vlog
Rr S 28T +5
a+
max(1, B² log k)
(log k)
(
aat max(1, B² log logk3 633%4) (log (log k)
4/5 (log k) + Blogk,
+ a
where, assuming 5 and E are picked sufficiently small (e.g., o(7 the dominant term is of order (aTT)) V/.
As final remark, that is our error tolerance when minimizing maxtec Ags.r (p, in p E where the optimal value is A n.... The properties of this optimization program are discussed in Appendix G. On the other hand, neither algorithm undertakes the (generally) more challenging task of computing A* up to some tolerance. Still, when tuning a fixed learning rate, this task is somewhat unavoidable tight regret guarantees are sought, and therein lies the utility of the online learning rate schedule described here.
I Examples Continued
L1 Linear bandits
Since th Ma for all A and L = X", maxosArec M. fl s 1. Hence, w <= 1 (see its definition in Lemma 2) and can be chosen as 1. Morcover, trivially, tha - 1/b Ma M, = M(c,- eb), which shows that the game is locally observable. Finally, is immediate that for any & C and a" arg min vi l, (ea ex- Jag Wooc and consequently, 8inc == maxrec mewoe max |alll 1
S We then obtain via Theorem I (and Lemma 17) that N S d (i.e., A is no larger than up to a universal constant).
1.2 Linear dueling bandits
Recall that here, the action set has the form A [m] [m]] for some positive integer m. With fixed feature mapping and Ma,s = V. th. If = ((Va)aex)) then w I 2 and can be taken as 2. As pointed out in [32], the Pareto optimal actions those of the form (a, a) for E [m]. Fix l L, and let (War,, E). (Here, a and are not necessarily distinct and, in any case, (a, b) E arg (a (War satisfy tha th = mince(m] (W)e, ().) Now, for any (c, c) E A. we can write
th from [m] to Rd. we have that for (a, E A, dha. == th + v
Vee Va,b the + the Via th Ma.o + Mo.b.
At the same time, (Ve,a v..., (V/a - Ve, E) < and (Ve, veeer C) = (1bs - the L) < 0. This shows that the game is locally observable (see Lemma 4) and that Bloe S. in the linear bandit case. Hence, it also holds here that A,, I d.
L.3 Learning with graph feedback
The game here, recall, is characterized by an undirected graph (A, E)) and we have that d= ki tha ca, and M, [Nx(N)(()) has the vectors (es)beNe(a) as columns, where Nç(a) the neighborhood of in G (which need not include a). In the terminology of [1], graph is said to be weakly observable if Va A, 3b e A: E (b),), while in a strongly observable graph, holds that Va A. either E (a). E (b) Ab A. or both. Here, and in all the examples to follow in this section, all actions are Pareto optimal. We consider
this example be (1o which
coincides with ((ea (ee)) Note that m.x. Ell = max.eA / V[Ng(a), which can be as
large as Vk, derive in the following tighter bound on w.
41

---

Recall from Lemma 2 that
( v.) (.oo
sup a.b, p tEc
M Qo(w)((6> +0)l
Now fix a,b, A. E k. and l E L. Firstly, the Cauchy-Schwan inequality gives that
1(0b 4c) Qs(p) Ma M, / e z ||M] (a()) (e's w Il 0
Notice now that [| I || I 1. By the structure of the observation matrices, Qs(p) is diagonal matrix with (P(a)) as the diagonal entries, where
P(a) = + (1 6)
Σ p(b) BE BENo(a)
Hence, (a(p) (tbs [b) P(b) leb - P(c)-tees and consequently, M Qa()) 4h) has most two possibly non-zero entries:
a = P(b) Tb e Ng(a))
and
== -P((() -Ic e Ng(a)].
Then, using that |a| + |8| = v(aa+ 13) & 02 02 + f2, we get that
MM (a())* +e)l, - v My Qs(p) - vb)e
which implies via the arguments above that
1(vb - v.) (esT((())))))))))) M. 4 v2 Qs(p) (vb-)))l
and consequently, w < 2. Alternatively, if L [0, 1]a, the non-negativity of the losses and the structure of M, Qs(p) (vb whe) described above yield that
(80s vc) -.)T((((()) M. El s max(la),
|M Qo(p) well ||M (olp)) - -b))l
Hence, it simply holds in this variant that w S 1.
Next, we study the problem-depended terms appearing in the bounds of Theorem 1 and Theorem in weakly and strongly observable observable graphs respectively, leading to bound of order (g on A in the former and a bound of order / /0(G)/nj in the latter.
Strongly observable graphs. Fix E L, as mentioned in Section 4, we aim to find À E Wolee that (essentially) supported
independent set and satisfying 8x < 2. Let a" arg min.e (Wa f) Notice here that AA" = A and (Wa: f) = f(a). We construct such a À by iteratively constructing two functions 91, 92: A \ {a }
A such that for all a e A {a"}.
i) a E (a)
ii) e Ng(gz(a))
i)) (()( ((a)
iv) ((2((a)) < L(a)
v) img(gi) U Uiig(ga)) < a())+ +1.
Fix E A {a*}. Note that for À E Wlee and b E A, Aa(b) E (R(N(()) with each coordinate corresponding neighbor of b. Since, by assumption, E (a)) we X (g) (a)) = e where abuse notation and ea in this expression as the indicator vector in (o)) for the coordinate corresponding to a. Similarly, set >a -e,- using that a" E (g)) While for b & (g1 (a), (a),.a(())) (a)).
Aa(b)
0. Finally, we naturally set Aa. (b) 0 for all A.
Using the assumed properties above, we get that indeed vha tha MA. A E W/oe (since E(gi (a)), (()2(a)) < {(a)), 3x s 2, and supp(A) & a()) + 1, as desired.
The two functions can be constructed using the iterative node elimination procedure detailed in Algorithm 3. This construction satisfies required properties for 9I and g2 as listed above. In particular, img(gi) ) is independent set, and limg(g2) iimg(9))l 1. The arguments laid so far
42

---

illustrate that the game is locally observable (see Lemma 4), and, moreover, that the first addend in the bound of Theorem is of order a()). What remains now bounding w* (note that Bglo I using Lemma 17 and the fact that Btoe S 2). Let S = img(g) U img(g2), which is total dominating set (that is, every node in the graph, including the ones S", connected node in 5*). Then,
w" = min |S] max
BEA Mg (M))) -Moll
I |S
max BEA
M, (E M,M,) M, = 1S
max BEA
M, Moll $ |S S (g)) + +1,
where we have used that Exes. M,M." is diagonal matrix where every entry on the diagonal is lower bounded by 1 (thanks to 5 being total dominating set).
Algorithm 3 Constructing 91 and 92
LR,,C input: undirected graph G = (A, le RR,a" a" aig E(a) output: 91. 92:92:4 : A {a
A
initialize: G 4
while g' contains at least one vertex do
if Vg. = then b a* else select E arg min Vor {(a)
D Vi denotes the set of all vertices in g'
set 91 (a) = b for all a E (b) {a*}
note that b E (b) i o otherwise b b Ng(aa) implying it has already been eliminated
g' < VV
Ub)
D for S C Vor, G'[S] denotes the sub-graph induced by S
end while if a" Nç(a") then
set (2(2) = a" for all a E A a
else
in this case, Ng(a*) A fa*} and (1(4) = a" for all A) {a*}
select E arg min a' f(a) set 92 (a) = e for all a E A 1
end
return and 92
Weakly observable graphs. It immediate to verify that weakly observable graphs are globally observable with Aglo 2. Moreover, w" is easily to be bounded by the total domination number 6(G) (size of minimal total dominating set) by following the same argument laid above in the strongly observable case.
1.4 Full information
This is special case of strongly observable graphs, with the graph being clique (fully connected graph) with self loops. For this graph, a(G) = 1; hence, the arguments laid out in the previous example yield that A is simply upper bounded by universal constant (independent of the number of actions). In fact, since M, is the identity matrix for all a, it easily seen that w² = 1. Moreover, the construction
described for strongly observable graphs (Algorithm 3) trivially yields, for every E L, weights X E Waoe that satisfy sApp(A) = {a*) (with a" E arg min 1/ E) and 0x = max.e AA (I max A car = V2.
1.5 Bandits with ill-conditioned observers
In this game: = k, tha ca. and M. = (1 - s)1k + e for some e E (0, 1]. Moreover, take L Bxx (1). Since M, As for all a, we have that [|a Schwarz inequality gives that max el < 1, implying that 1. As noted in Section Ca G 1/e(Ma M.) for any a E A. Hence, it holds for any E L and a" arg min viT that (ca/s ea- Ea-/E)aEA E Wloe, and consequently. that Broe bele. ct/Ella = 2/2. Theorem then gives that A,, < d/e?.
Hence, the Cauchy-
43

---

166 Learning with composite graph feedback
This game is a variant of the graph feedback problem (on an undirected graph G (A, with all self-loops) where, again, d = k and th = Co: however, the feedback vector Ma is the a-th row of the k X k matrix D-1 A: hence M = (D-IA) AA) AD- Here, D is the degree matrix and A is the adjacency matrix. Hence, after playing A, the learner observes the average of the losses (i) E Ng(),)) which include & (Ae). As mentioned in Section 2, this feedback less informative than standard graph feedback, and draws inspiration from problems studied in [57, 25] motivated by applications in signal processing (SNETs [19]). Once again we take L = (1). Note that || 1 1: hence, A. clM, S 1, implying again that w I 1. Depending on the structure of the graph, the game could be hopeless, globally or locally observable (or even trivial if there is just one action).
If the graph is empty of edges except self-loops (i.e., M = It), we recover the standard bandit game, which is locally observable. In fact, this is a necessary condition for locally observability. To see this, fix E L such that f(a) < E(b) < min (a.0) E(c). Then, c ca & span Ma M,} a and b are connected in the graph, which rules local observability via Lemma (note that all actions are Pareto optimal). As for global observability, one needs that eb Ea E span Mc: c E A} for all a, E A. If we define S span c. eb: for all a, A), global observability then translates to S S col Now, suppose that det(M) M) = O. This would imply that dim(col( (M)) is at most Then, since (S)
global observability would require that dim dim (col(M)) =
and S = col(M), This can never hold, however, because the vector 1 is orthogonal to S, while any column of M has non-zero component along k; implying hence that col & S. Therefore, in order to be globally observable, the game must satisfy that det F O, which is also clearly sufficient condition.
Assume in what follows that the game is globally observable, meaning that M has full rank. As mentioned in Section 5, it holds here that u² = k. To see this, note that Lemma implies in this case that for any orthonormal basis U, E.ESU" UT M,M,, U is invertible only when S = A. Hence,
u = k| JIMMUU( MM MMTU)-'U M| k
As for w", know from Theorem that w² kt Moreover, recalling that (Ma)ae are vectors in this example, we have that
w min max M, ( T Mo = k
EEA PEA
where the equality follows from Lemma 12 using that rk (M( = k by assumption. Hence, it holds too that wt = k. Theorem 2 then yields a bound of order B2.glo / /k/n on AG--
We now examine the two quantities Agto and $2 in this problem. The assumed Invertibility of M implies that
Bglo max a.eEA
| (ea -e>)l1 and
B2.glo
mmxx M M (ea - -e6)lla- a.E
It holds here, it does in general, that $2.glo S Bglo S Vk32glo- Recall that M AD-1 and let S == AD-1// Note that S is symmetric and M could be rewritten in terms of as M = D1/2 Further, M and S are similar, thus they have the same eigenvalues. For square matrix V, let o(V) denote its smallest singular value, and let (w:(V))=....., denote its eigenvalues. Lastly, let deg(a) denote the degree of action a, and let deg and deg denote, respectively, the smallest and the largest degree of any action in the graph. Now,
B2 = max M -- (ea - - = max A
I 1/22 D 1/2 - eb)ll2
a.DEA
degmax deg(a) (bg
degmax
v /2eegaxx/ deg degmin
|| ||5-1||2
OSS)
2deg degmin
2degmax/ /dgmin
min;=1,.... [s) min; 100;;11.... I....k (w;(M))
where the penultimate step follows from the symmetry of S, and the last step uses that M and similar. Note also that wy) 1 - (L where y It S is the symmetrically
44

---

normalized Laplacian of the graph G. Hence, it also holds that
v 2deg deg Suui
g S
minl,
We 1
1.6.1 Cycle graphs
As an example, take G to be k-nodes cycle graph (with self-loops), where For convenience, we index actions starting from 0 instead of in the following discussion; that is we take A = {0..... 1}. We also extend this notation vectors and matrices indexed by the actions. For this family of graphs, we have that
Aa.b 1b E {(a 1) mod k, (a + 1) mod k]] and M -AA 3
& mod 3 = O, then M is singular, which is synonymous with a hopeless (i.e., not globally observable) game in this problem argued before. A simple non-zero vector that belongs to ker(M) in this case is given by
2, if a mod = -1,
(aa)
otherwise
for a E A. see Graph (i) in Figure 1 for a schematic representation on a 9-node cycle. When k mod 3 (1, M is invertible and the game is globally observable. In particular, for a, b A, one can verify that
2 v3
2
(2Th(a,b) 3
(2Th(a,b)
M a.b
sin
cos
3
3
where h(a,)) b) (a b) mod k. We now characterize Bglo and $2.glo up small constants, focusing on the case when & mod 1. (The remaining case, when & mod 2, can treated in similar manner.) Firstly, via the triangle's imequality,
Be
M AMM'eea a.E
max
(ea -evill S aEA
max M M
And similarly, Aglo I ma M As the entries of M determined by h(a, b), all its columns are identical up to cyclical shifts. Hence, the bound above is attained by any action. From the formula stated above for M one can check that each of its columns contains 1 2(k: 1)/3 entries with value and (k: 1)/3 entries with value 2, Graph (ii) Figure provides a schematic representation of one column of M-1 10-node cycle. Evaluating the Ia and L2 norms obtain
glo S 2V 2k
and Bglo 2 -
On the other hand, we can obtain a lower bound by taking and b as neighbors. In which case, M 1 (e, eb) contains (k: 1)/3 entries with value 3. (k: - 1)/3 entries with value -3, and 1 + (k- 1)/3 entries with value 0, visual representation is provided by Graph (iii) in Figure 1.
Then, again evaluating the L, and L2 norms gives that
B2 2 16(k-1)
and
Aeto 2 2(k - 1).
This shows that Bglo is (kk), while $2.glo θ(Vk), providing thus an appreciable improvement relative to the former in the bound of Theorem 2 (recalling that here, w" u² k).
L6.2 Complete bipartite graphs
As second example, we consider a complete balanced bipartite graph G2/2.4/2 (with self loops). assuming & is even. The vertices of this graph are partitioned into two subsets of of size k; L (1...., k/2} and = {k/2 + 1,..., k} such that for a, E A with a < b,
Aab Ab,a [a E T. and b E R].
while Aqe for all A. Hence, all nodes in this graph have degree k/2 + and
1
Ik/2
JE/2
M
A
k/2 +
k/2 +
Ju/2
In/2
45

---

a
2
2
-
3
3
1
-3
(i)
(ii)
(iii)
Figure I: The first figure represents a (non-zero) assignment weights on a 9-node cycle such that the sum any three consecutive nodes is O. illustrating that M is singular. On 10-node cycle, the second figure provides a representation of M - i.c., the a-th column of M M- where a is an arbitrary action in A. The last figure is representation of M (e. es) on the same graph, where b is a neighbor a.
where Is/2 the (k/2) x (k/2) identity matrix and Je/2 is the (k/2) (k/2) matrix with all entries equal to 1. In a similar manner, we can write any vector I E IR* the block form
I
TR
with F2, on E h/2 kf 2, then M is singular and the game is hopeless. Otherwise, when i 2 M is full rank and its inverse is given by
1
(4///4
- 1 [k/2)
Jk/2
M
k/2
J2/2
(12/4-1)fr/ 1) (k/2)J
If two actions and are the same side; i... a, b E L or a, b then
M M eb) (k/2 1)(c. et).
Otherwise, if a E L and b R, then
1
- 1k/2
M- -ea) = (k:22 - k/22
1x/2
In either case, both M - -b)ll2 and (e, - e0)l are (kk). Hence, both 82.gio and Agto are (k:). Compared to the previous example, $2. grows faster with the number of actions, while Bglo remains of the same order.
J Lower Bounds
In this section, we provide proof for Proposition 1. This is an extension of the lower bounds in [31, Appendix G], with a construction that compatible with the adversarial setting. The proof still relies on designing hard instances in stochastic linear partial monitoring framework. However, the noise added the loss vector itself. This noisy loss vector, moreover, designed respect boundedness condition. The latter is achieved via truncation, following [16], at the cost of factor logarithmic in the time horizon. We also provide a tailored lower bound for the bandit game with ill-conditioned observers that matches the upper bound we achieved.
J.1 Stochastic Linear Partial Monitoring with Parameter Noise
We will assume henceforth that, for some positive integer m, n(a) m for a E A: this can be taken max, na(a) while padding with zeros the matrices with fewer columns. Moreover, as
46

---

mentioned in Section 2, we assume that B2(r) S C parameterize stochastic linear partial monitoring problem as follows. At round t, the player select (possibly random) action A, E A and observes the signal Φz M l I where & E IR4 is given by
for some > 0. Let E R We will use @ to
4 = 0 X,,
with X, drawn i.i.d. across rounds from a Gaussian distribution (O, Σ), where Raxdd is some covariance matrix. Extending [16] (see also [18, Theorem 9I), we describe in the following a truncation scheme that allows adapting to the adversarial setring lower bound constructions that employ unbounded noise. Let clip: Rd > L denote some clipping operation. Consider the following two notions of (random) regret:
RT(0)= = (WA La
t=1
(0) max acA
Σ (WA. va)T clip((e).
where (44), are drawn as described above and the actions (Aş)e are chosen via some policy (#t)e- Moreover, define the stochastic regret (0) as:
T
( max E. aEA
E ve) max Eg acA
AA. T.)
where the expectation is taken over the aforementioned sequences (fe), and (Ae).. (The dependence on (Ne)c is not explicit in the notation since it will be fixed throughout.) The equality in the above display follows from the fact that X₃ is centered and independent from A..
Lemma 18. Let ④ be a finite subset of Rd with |e|
N, and let = max - v/ll. Then,
R
2
1
(0)
T312 N
E
V E E 12) (o(clip(E)) # #G))
N
AEB
While if there exists some R > such that maxace (T) S R uniformly, then
RG
N
1
Σ
(0)
RT
Σ
(o(cipp((1) + f1)
N
N
AEO
8c8
Proof. Firstly, note that
RG 2 supo Eg (0)
2 Eg and ERy (0) 2 Rr(0),
N
AEE
the latter holding via Jensen's 's inequality. Define the event {vt [2], clip(()) le). Clearly, (0) = (f) whenever B occurs. Hence,
Eg (0) Eg [1B] (0)] + Eg ([B)) < (. (0) + E. [T
Rather crudely, we have that
(0) max AEA
(WiA T +0)
max aEA
Ilyh d/ Mall|x,, + #ll1
T
< max || - w//ll Σ a.eEA
X + 01
t=1
< max ||,b - vall
[10|IT + Σ x,,||
a.beA
47

---

And,
2
(2) - max 1140 26612 |101 + > |1xi|] a.PEA
t=1
< 2 max 1/40 450119 [101222 + > (xxxll) )) a.
T
S 2 max 10 woll? [101|222 T > | a,
Now, via the Cauchy-Schwarz inequality.
Es (r)
- v E. [[ E. R (0)]
Eo [[B]] Eo R3 (0)
Po (B)) Eg (0)
2 max |14/ - - PP abEA
[ + VT
Σ
11
S 2 max 11 - 1 (100 + / | /Po
a.eEA
Where we have used the fact that (Xt), is an i.i.d. sequence. Moreover, a union bound gives that
Po (B S
Pa (c((pi(())) &.) TPP (clip((() + e.).
Let a² = max, be 1/ Voll. We have shown that
S 22 (110) + /EIXx (clip(() + 3/2 In the simpler case when max e Ry (0) < R uniformly, we can similarly show that
Es [B] (0)
Eg [ (.) < (clcip((E)) + RT
The theorem then follows using that
(0) 2 (T) Eg [[B] 2 RT(0) E. [[B]
In the following, we will generally use Pa to denote the probability measure over the history of interaction Hr == (Aa, ) induced by our fixed policy (Te); and the environment parameterized by 0. Moreover, Pe.. will denote the distribution over observations when action a is played. This stationary (does not depend on t) since (fx) is an i.i.d. sequence. Let DKL (P Q) denote the KL-divergence between two measure P and Q. The following is a standard result based on the chain rule for the KL-divergence; see, e.g., [35, Exercise 15.8].
Lemma 19. For any 0, 0' Rdd, it holds that
(P [Pr) Σ Eo DKL P.P...))
E To(a) (Po.A. ...)).
acA
where (a(a) = Eg [A. = al.
As an extra piece of helpful notation, for S C let = Eg ET E S].
48

---

J.2 Regime-based lower bounds
Besides the use of truncation and parameter noise, the constructions used in the following three lower bounds are adapted from [31, Appendix G] and [35, Chapter 37]. Analogous constructions appear also earlier works on finite partial monitoring like [3, 6].
Theorem 3. Assume that (r) S L for some r > 0. If the game is globally but not locally observable then Ri is ()
Proof. By Definition I and Lemma 5, there exist at least three non-duplicate Pareto optimal actions, two of which, say a and b, are neighbors and satisfy
Ve 1h & span c
Hence, we can write vha - 4/ a + o with u belonging to spant Mc : E Na,1) and v + belonging to its orthogonal complement. Let 0 E relint(Ca, n C.). Then P(0) coincides with N No, in particular, there exists game dependent > such that any & Na.6 satisfies (ve t'a 0) 2 E. Moreover, can assume that ||0]] = r/4 (C, n C2 is cone). Let 0 A S 1 be constant to be chosen to later, and let q == T|lll V. Now, define
O₂ = 0 Aq and
O. + Aq,
and notice that
Ar
Ar||ul12 4||0||
Ar||ol
(waa Vb. 0 Aq)
4/l0l| (v/a vo. 1)
4 < 0.
Similarly, (why vo + Ag) = Ar|[ol
< 0. For brevity, let 7 = Arijull, Note that any c E Na.b
satisfies that P(0). Hence,
( va. f- - Aq) + (ee - -0h
0 + Ag) = (We 1/5 th + va. Aa) = A.
Therefore, max ( Vaa 0a), (w)- -v8. 06) A/2. In particular, define
S. E Na,b (e'e - via, 0a) 2 Í/2]. S {c No. (tee via 0a) < k/2) Na,b S.a
Also note that min ( (yh: - than 0a), (t/-- - 1/b, 0b) > 0 for any E Na,6 since the [1/a, 1/6.. Moving over to actions e & No,,, we have that
rda"
(We (v. 0- Ao) 2 (e that Ag) 28 Allva &all 2 8 v.a
4
where a² = da 1l vall > O. Assume that A < 26; thus, (1b - 1. Oa) 2 e/2, and similarly, (th w/b 0o) 2 E/2. Moreover, since ||||| < a", we have that A - नार implying that
2x
A < e/2. For brevity, let Na. A Na.b- Overall, we have that 0₂ C. and 0, E Cs- In particular,
A T To. (Sa),
(0.) = Ea, (vA, T 0. 2 2 (Wab))
2
and,
T Σ (1)A - 26) T0 2
A
(8b) = Eo,
5 (N a.)) + To, (Sp)
2
2
2
To. (N a,b U.)))
2
A
(T
To, (Sa))
2
A
(T To. (Sa))
(To, (Sa) - To, (Sa))
2
2
A
2
(T To. (S.))
-
T (1/22 (Po PP.)
2
2
49

---

where the last inequality follows from [35, Exercise 14.4] and Pinsker's ' inequality. Hence,
A - T(1 ((1 (Po DKl PPoo))
Rr((0)) + - 2 2 To (N a.))
Now, let X, ~ No o² Ig)- Recall that, 4 = 0g + X, under environment for and e 0g X, under environment lg. For any action c, then holds that Fo.,c is (M, 8a, MM Mc). and that
(KI.PPoass Ooo... Pa..c) = DRL. (M 0n, o² M Mo) || |MM 0g o² M Ma))
MMMMa)
Note that the first distribution is supported on M. 0o + col( MM. M.) col(M,] which coincides with the support of the second. Hence, the KL-divergence finite and can be written as (using, e.g., Equation 3.1 by Holbrook [29]):
DKL. (Po..e Po..c)
20 (M. 0n - -M (M. M.) (M. 0n Mº
20 (0, 0n) MM. M.) M2 (0. -n) 0n)
(0. 06) .MMM. (0a 06)
202
(-2Aq) T M.M! (-2Aq)
20
2
24
d2 9 MaM
π² |MMMall
where we have used that M.M is the orthogonal projection onto (M2( This also means that if e Na then M,M by the construction of q. Otherwise, we simply have that |MMMall s l1 r/4 Hence, via Lemma 19, we have that
A²A² To, (Nab))
2 To, (Na.)).
(Po, [Poo) S 802
0B||us|2
Which gives that
A 2
A T
A
(o)(2a) + (0.) 2 To (N e,6)
o||l|| V Toa (Nas)
Now, set A = 2010-1///// 1/3////// /r, assuming T is large enough so that A < min 1, 26 } Precisely, assuming that 1 2 o max(2/rr a² /t}. We then have that Ä I|li|| 1/3 12. Now, if To. (No.)) s TT23, then,
A T 2
A
A T -- 0 T%
(T((w)) + (0,)
1//
2
8
Otherwise, we directly get that (0.) + Rrr (0%) 2 ς 2 Hence, in total, we have that
(Rr) + Ror().)) 2 min { ال|اا||
T//s
16
We now prepare for an application of Lemma 18. First, notice that X1| odd. Second, pick the clipping operator
clip((.) = |||&|| < r14 + 1||4|1 > r] rl,
[Telll
Then, for 0' E ((a,000)
Per (clip(()) # +&) = Po (llell > r) < Per (110'1 + ||x||| > r)
S Po X1 > r/2)
= Por (1)x1 2 >>r" r2/4).
50

---

which uses that ||0a]| - |||| + A 1g1ll r/2, with the same holding for 6g. Lemma by Laurent and Massart [41] gives that for x >
P > d²d 20 Vv + 20²x) S se
Assuming 0² < setting r² /800²2 gives that
|| > /2/4) S ~~/
Then, Lemma 18 yields that
V20-70/2
R7
RT((')
(16'11 v / 13) Por (clip((1) + e1)
2
2
8'E ('e
o [oleel
8
" (r/2 to ovd /(1600² T
min
16
/2a" 122"r1' 2/ /11000") T
min
16
where the last step uses that a S rr Now, we can pick a = /240log(T) which is a valid choice
when T is large enough that 0² S y² (8d), meaning that T 2 e/300 With this choice of obtain that
8 $1 T /2a'r, 32 60 log((T
r||l|l
Rr min
4
which concludes the proof.
Theorem 4. Assume that (2(r) S for some O. the game is locally observable and there is least one pair of non-duplicate Pareto optimal actions, then Ry is (((TT).
Proof. By the connectedness of the neighborhood graph, there must be at least two pair of neighboring actions, which we again denote by a and Most of the proof proceeds almost identically that of Theorem 3. The main difference is that tha 1/5 E span Mr c E Na,bb by local observability. Moreover, Na.b could be empty. Nevertheless, we can directly take
== V/ 1/b,
which is strictly positive, and again define q = ||l v. Then, for some relint(C,, n Cb), we again choose
0₂ 0 Ag and O, - 0 Ag. Following the proof of Theorem verbatim, we reach that
A T(1 v(1/2) DKI(Po, (o.))
Rr((.)) Rtr())) 2 To, (Va.))
+ 2
> 2 T(1 (01--(1/20 ((/2) DKL PP..))
We choose, again, that X, ~ NN0, 25.
02 I4). Now, however, we use the bound
Poy S
o² i|lla for all actions c, even the ones in Na.. This yields via Lemma 19 that
A T
Ä
(r(( + (O) 2
VT
2
|||||
Taking 1// 1//T.///rr. /r, (assuming again that large enough to satisfy the condition set on in
the proof of Theorem 3),7 we have that Ā = = 1/2/2, which implies that
a | VT.
(0.) (0.)
"I Wa.b is empty (also meaning that TN(N..)) 0), one can satisfy the conditions on A in the proof of
Theorem 3 taking arbitrarily large number.
51

---

The rest of the proof again follows that of Theorem 3, with an identical use of Lemma 18 and tuning of a. finally yielding that
RG 2 r||l| VT 220"r
32 B2V66llgg/ (og
for sufficiently large T.
Theorem 5. Assume that (2(r) C L for some r > 0. If the game is not globally observable, then R. is (?()).
Proof. The game not being globally observable means that there exists a, E A such that Vo th & span c A}.
This implies that they have distinct features, which in turn implies that there are at least two non- duplicate Pareto optimal actions (vertices). Now, if the property above holds for some pair of actions (a, b), then it must hold for at least one pair of non-duplicate Pareto optimal actions. This is because the features of any action can be written convex combination (with positive weights) of the feature of one or more Pareto optimal actions. Hence, tha 1 1hy can be written as a linear combination of feature be (non-duplicate)
differences for Pareto optimal actions. This implies that Pareto optimal actions. fact, we can take them to be neighhors too; since the neighborhood graph is connected, we can find path (a:);=1 where di a, ag b, and (at, a1+1) are neighbors (endpoint of an edge the polytope of neighbors must satisfy the non-observability condition above. Thus, without loss of generality, and are assumed to neighbors.
take and
co(x)). And since v/a - t/b = 2--1 (Way - Vay 1): at least one pair
Now, define v as the component of v.a th in the orthogonal complement of (pan(MM, c E A}, _ v. Neither of which zero by assumption. With this altered choice of (and the and set q 4|ja|| corresponding one for q). we can follow the proof of Theorem 3 verbatim till we reach that
A T (11/2) DKL (Po. PP.))
RT((.) (0,(,) To. (N a.))
DKL
2
A T(1 ((122 DKL (Po. Po.)).
2
Observe now that q belongs to the orthogonal complement of MM,) for all E A, meaning that, via the derivation in the proof of Theorem 3 (again with X, (N, Ia)), DKI [P, ) 0. 2z
Hence, (Po,Po, Po..) 0 via Lemma 19. Then, choosing A = min ra yields that
|r||e|| e||e|1
(6.) (6,) 2 min {
4a" ]
Next, a similar application of Lemma 18 to that in the proof of Thcorem 3 gives (with sufficiently small σ) that
T|lu||
e|le|l - + (16600)))
R4 2 min
16 8&"
Since does not appear in the first term (in fact, adding noise here is redundant), it can be chosen sufficiently small so that
rlllll e|le||
} T,
RG 2 min
32 16a
proving the theorem.
J.3 lower bound for bandits with ill-conditioned observers
As defined in Section 2, we have in this game that d d= k, t. = ca. and M. -1 (1 =))1sk) sea for some ε (0, 1]. Here, we take L Bxx (1) (see Appendix I). fact, we clip the losses this
lower bound construction belong [0, 1 This example is adapted from [18. Section 6), where they consider the case when th too is (1 c)lkkk + se., and prove a Ω ((VkT)) lower bound in their Theorem 9. The game consider here harder asserts the following theorem.
As remarked in the proof of Theorem 4, take be arbitrarily large number if N... empty.
52

---

Theorem 6. In the bandit game with ill-condiiooed observers, it holds that Ri is (1/eeV/))
Proof. Besides the altered definition of tha the proof is essentially identical that of [18. Propo- sition 8J. Nonetheless, we report here the full proof in our notation for completeness. Consider l environments {4a Jae such that
0a = 2 + 11 1x Aea: 2 k
besides an auxiliary environment 0g = (1/2) where
S 1/4. Notice then that for any
be E A {a).
(wb Vo: 0.) = (e, ca 0a) =A.
Hence, 0a E Ca, and in similar fashion to the proof of Theorem 3, we have that
T
(T(( = Eag, Σ (W. - -aa, Oa) = A(T - To,(a))
A(T - Te, (To, (a) - -Too (a))
> A(T - (a) AT AT DKL oPoo Pl.
In this game, will take X₂ to be distributed according to 1/(00 (111))) for some 0. This means that in environment la. le = 0a + Z,1,, where (Zi); is an i.d. sequence of random variables, each sampled from (V(,, 2²). Notice that, for all E A, Mc. E Aus hence, M. M 0a + Zz. So we get that
(Po.c [P.o..)) = DKL (N(M. 80. 02) N 0c.
1
(Oo 0a)* McMo (0o 0o)
20
Notice, moreover that
(Oo 0a) Me A A(c.
T (H-)))=))))) 1x (1-11111 1 1 1x
se.) =AIaa c.
k
k
Thus, (P || Po
22² 20
[a-
c] Lemma 19 then implies that
E²A 402 (a) = A(T To,
EQ2
(r((s) 2 A(T - To, (a)) - AT
To, (a).
20
Hence, via Jensen's inequality,
1
Σ (o,) 2 -
EAS
T
TT/h
h:
20
A
T
/T/k)
2
KT
8z
where in the last step we have picked A ayE 25v7 assuming that T 2 4/²k/e² so that A S 1/4. To
apply Lemma 18, we choose the clipping operator as follows (where l((c) = =T)()):: 4)):
[clip(()][cc) max (c()),
Note that under any environment 0.. 1/4 S (c(c) < 3/4 for all E AA by the definition of 0, and the fact that 0 A 1/4. Hence, since (a(a)) (c(c) 7,, if clip(&.) * l,, then it must be that /Z,l > 1/4. And since Z, ~ (N10 o2), we have that P([Z, > 1/4) S 2exp(-11
Moreover, under environment 0g, it holds for any pair of actions and that
(wh - Via, f2) = (ee ed, 02 + 7, 1) = (ee Cd 0,) < A, which implies that (0.) < AT uniformly. Therefore, can apply the second part of Lemma 18 to obtain that
RG Z 0 KT
2AT2 -1320"
Te (/so0))))) -
σ -VTT
KT
VTT 64 64
85
where the first equality uses our choice of A, and obtain the second set (o2log(16T)
53


Reviews:
[{"review_id": "uU04bK2Tar", "reviewer": "Reviewer_5qSe", "summary": "The paper considers the adversarial linear partial monitoring setting. The authors provide an efficient algorithm for this setting, based on the principle of exploration-by-optimization (EXO). The authors show that the regret bounds of the proposed algorithm are near-optimal in the globally and locally observable games. \n\nPrior works, e.g. Lattimore and Szepesvari [2020], only provided efficient and optimal algorithms for the finite partial monitoring setting (the current paper extends this to the linear setting). Existing results on linear partial monitoring by Lattimore and Gyorgy [2021] involved an inefficient version of EXO.", "questions": "See questions in the strengths and weaknesses.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strenghts:\n- The paper provides a unified algorithm for the linear partial monitoring setting, and shows that this generalizes many existing setting actively researched.\n- The paper is written in a mathematically rigorous way. \n\nWeaknesses: \n- The main concern I have with paper is with the writting. The paper is rather dense with definitions, and authors do not always provide sufficient intuition. If I were to rewrite the paper, I would perhaps include less results in the main body, but then provide more intuition and proof sketch in the main. \n- The authors also do not spend enough time highighting the deltas to prior work. Sure, the paper provides the first efficient algorithm with near-optimal regret for the linear partial monitoring setting, and this setting encopasses previous settings such as full information, linear bandit, graph feedback, etc. But are there existing efficient algorithm for these setting not based on EXO? Also, the authors should also highlight any novelties in the analysis of the algorithm, and where they were able to overcome prior hurdles. \n\nSome other comments:\n- The notation in the first paragraph is not consistent with the notation in the rest of the paper. \n- Line 20 says: \"All of these components are known to the learner,\", which suggestes L is know, but then L is unobserved. \n- Line 136 claims that (3) implies (2) for $C = \\mathbb{R}^d$. Is this true? From its definition, the set $\\mathcal{P}(\\mathbb{R}^d)$ should only contain points in $\\mathrm{ext}(\\mathrm{co}(\\mathcal{X}))$, whereas (2) invloves points for all $a,b\\in \\mathcal{A}$.\n- Does the set of neighboors $N_{\\mathcal{G}}(a)$ include the set itself?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We address below the raised concerns.\n\n> The main concern I have with paper is with the writting. The paper is rather dense with definitions, and authors do not always provide sufficient intuition. If I were to rewrite the paper, I would perhaps include less results in the main body, but then provide more intuition and proof sketch in the main\n\nWe recognize that the presentation is dense; however, we do devote a significant portion of the main body to developing intuition regarding our adopted approach and its analysis. In particular, the progression in Section 3 is meant to motivate and explain the EXO approach, justify our specific choice of (anchored) loss estimator (compared to the more general machinery of [30]), and illustrate how it ultimately gives rise to the optimization problem featured in Algorithm 1 and analyzed in the rest of the paper. Further, the bulk of Sections 4 and 5 is devoted to outlining the key steps and hurdles in the analysis, highlighting how the linear structure of the problem can be exploited subject to the observability conditions. Finally, the example problems that we discuss motivate the general setting and help interpret the results. Nonetheless, with more space available, we would be able to expand the explanations further in the revised version.\n\n> The authors also do not spend enough time highighting the deltas to prior work. Sure, the paper provides the first efficient algorithm with near-optimal regret for the linear partial monitoring setting, and this setting encopasses previous settings such as full information, linear bandit, graph feedback, etc. But are there existing efficient algorithm for these setting not based on EXO? Also, the authors should also highlight any novelties in the analysis of the algorithm, and where they were able to overcome prior hurdles.\n\nEfficient, specialized algorithms do indeed exist for the examples we discuss; however, our aim in this work is not improving upon these algorithms in their respective problems. Our aim, rather, is to present a unified and efficient algorithm and to show that it enjoys interpretable (in terms of the dependence on the problem structure) regret guarantees in our general setting. As a testament to the significance of these guarantees, we show that they recover tight bounds across a wide spectrum of well-known special cases; in particular, we show that our generic game-dependent factors reduce to the `correct' complexity measures in these problems.\n\nRegarding novelties in the analysis, a primary novelty is how we exploit local observability under the adversarial linear partial monitoring framework. This is elaborated on in Section 4, where we highlight the point of departure with the standard analysis of EXO in finite partial monitoring. In particular, the choice of exploration distribution in our analysis does not follow the water transfer method of [32, 33]; it constitutes a simpler and more natural manner of redistributing the weights between the actions in this setting, and importantly, it enabled achieving the game-dependent constants featured in our results.\n\n> The notation in the first paragraph is not consistent with the notation in the rest of the paper...Line 20 says: \"All of these components are known to the learner,\", which suggestes L is know, but then L is unobserved.\n\nThe notation used in the beginning describes the partial monitoring framework in full generality, subsuming our setting and that of finite partial monitoring. Indeed, $L$, as defined there, is known to the learner. It describes how the loss is determined by the learner's action and the environment's (unobserved) outcome. In our setting, the outcome space corresponds to $\\mathcal{L} \\in \\mathbb{R}^d$ (as mentioned in Lines 97 and 98), such that for $a \\in \\mathcal{A}$ and $\\ell \\in \\mathcal{L}$, $L(a,\\ell) = \\psi_a^\\top \\ell$. This can be clarified further in the revised version of the manuscript.\n\n> Line 136 claims that (3) implies (2) for $C = \\mathbb{R}^d$. Is this true? From its definition, the set $\\mathcal{P}(\\mathbb{R}^d)$ should only contain points in $\\mathrm{ext}(\\mathrm{co}(\\mathcal{A}))$, whereas (2) invloves points for all $a,b \\in \\mathcal{A}$.\n\n$\\mathcal{P}(\\mathbb{R}^d)$ contains all actions since $\\boldsymbol{0} \\in \\mathbb{R}^d$ and $\\mathcal{P}(\\boldsymbol{0}) = \\mathcal{A}$. We also note (as mentioned in the paper) that this formulation of the observability conditions is due to [24].\n\n> Does the set of neighboors $N_{\\mathcal{G}}(a)$ include the [action] itself?\n\nNot necessarily, if the reviewer is referring to the graph feedback problem. In the composite graph feedback problem, however, we do assume that every action has a self-loop as mentioned in Line 180."}, {"review_id": "utPsga3K7x", "reviewer": "Reviewer_bC8o", "summary": "This paper studies the setting of adversarial linear partial monitoring. They provide an implementable algorithm based on the “Exploration-by-optimization” method that obtains optimal regret bounds for locally and globally observable games respectively. Moreover, their regret bounds scale with instance-dependent quantities comparable to the one obtained in the stochastic version of this problem.", "questions": "- It is stated that the setting studied in [30] is more general than the one of the paper because the observation is taken as arbitrary. In particular, the setting of the paper does not subsume the setting of finite partial monitoring. Could you explain why the restriction is necessary for the methods of this paper to work ?\n- The concurrent work of IDS for Linear Partial Monitoring doesn’t require a finite action space for the regret bounds to hold. Is it possible to extend the methods of this paper beyond the finite action space case ?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written and easy to follow. The main ideas behind the algorithm are clearly explained and the mathematical derivations are well presented and shed some more lights on the results. The dependencies in the regret bounds are clear and the instantiation of the regret bound on different setting of interest shows that this method recovers optimal or almost optimal rates in a variety of settings.\n\nAs I’m not as familiar as the authors with the litterature on that topic, I found the comparison with existing work a bit hard to follow, in particular, what are the known upper and lower bounds for the regret in the stochastic and adversarial setting, are the proposed algorithms implementable.\nOne of the main properties of the proposed algorithm is that it is implementable, it would have been good to either have some experiments to illustrate that or at least a clear analysis of the computational complexity of the algorithm in one of the settings of interest.", "was_revised": true, "final_justification": "My questions have been properly adressed by the authors. I remain confident in my good evaluation of the paper.", "rebuttal": "We thank the reviewer for their feedback and positive comments. We provide below the requested clarifications.\n\n> As I’m not as familiar as the authors with the litterature on that topic, I found the comparison with existing work a bit hard to follow, in particular, what are the known upper and lower bounds for the regret in the stochastic and adversarial setting, are the proposed algorithms implementable. One of the main properties of the proposed algorithm is that it is implementable, it would have been good to either have some experiments to illustrate that or at least a clear analysis of the computational complexity of the algorithm in one of the settings of interest.\n\nTo expand upon the discussion in the introduction, the state of the art results in the stochastic setting are those provided in [24,25], which adapt the classification theorem from the finite partial monitoring setting. This provides the optimal rates in $T$ (at least for finite actions) in locally and globally observable games; moreover, their upper bounds also feature constants that depend on the finer structure of the game, though their optimality is not studied. In general, their bounds are not comparable with ours (in the adversarial setting) since neither problem directly subsumes the other (see Paragraphs 147-153 and 343-347). Nevertheless, our bounds exhibit a degree of similarity with theirs; for instance, roughly speaking, Theorem 8 in [25] reports a rate of order $r \\sqrt{\\alpha T}$, where $r$ is analogous to $\\mathrm{rank}(\\mathbf{M})$ in our setting (but also takes into account the structure of the loss space) and $\\alpha$ is a game-dependent constant that can be expressed in a similar form to our $\\beta^2_{\\mathrm{loc}}$ via their Lemma 5 as we mention at the end of Section 4. An analogous comparison can also be made in globally observable games.\n\nIn the adversarial setting, the problem studied in [30] subsumes ours, but their bounds are very generic; they are stated either in terms of $\\Lambda^*$ (analogously to Proposition 6) or in terms of the information ratio, both of which remain opaque as to their dependence on the structure of the game. Moreover, thanks to our more structured setting, our EXO algorithm is amenable to efficient implementation, as discussed in Appendix F, where it is illustrated how the optimization problem that we need to solve simplifies in many common scenarios. \n\n> It is stated that the setting studied in [30] is more general than the one of the paper because the observation is taken as arbitrary. In particular, the setting of the paper does not subsume the setting of finite partial monitoring. Could you explain why the restriction is necessary for the methods of this paper to work ?\n\nDespite our linear observation structure, finite partial monitoring can still be modeled as a special case following Example 7 in [25], where $d$ is taken as the number of outcomes. However, this requires enforcing a certain structure on the loss space; namely, it would no longer be full-dimensional, and hence the observability conditions we consider in this work (also used in [24]) are no longer adequate, see Example 8 in [25] for a simple instance illustrating this. Properly addressing finite partial monitoring within the linear framework requires exploiting the possible low dimensionality of the loss space (as done by [25] in the stochastic setting), which we did not focus on in this work.\n\n> The concurrent work of IDS for Linear Partial Monitoring doesn’t require a finite action space for the regret bounds to hold. Is it possible to extend the methods of this paper beyond the finite action space case ?\n\nA direct extension of our tools (through discretization, or through a direct generalization of our EXO algorithm and its analysis) would likely be inadequate for continuous actions spaces in general; it is shown in [24] (in the stochastic setting) that the observability conditions alone are no longer enough to characterize the optimal rates as the shape of the action set matters as well. In fact, aside from special cases, the general case of compact action sets is not well understood even in the stochastic setting (i.e., a full classification theorem is lacking), and remains thus an interesting problem."}, {"review_id": "4fg6NkyU9F", "reviewer": "Reviewer_Tk4m", "summary": "This paper proves an instance-dependent upper bound for the regret for non-stochastic adversarial linear partial monitoring which covers possibly infinite outcome spaces. The problem-independent lower regret bound and upper regret bound is characterized by the global or local observability.", "questions": "1. Could authors explain the definition of $\\Lambda, H$ and $B$?\n\n2. Could authors provide an overview of the analysis on locally observable and globally observable cases, before going into the proof, respectively?\n\n3. What is the novel technique developed in this paper? What are the main challenges to derive the results in locally and globally observable cases?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The proposed non-stochastic linear partial monitoring model covers a wide range of settings including linear bandits, graph bandits and ill-conditioned bandits, which contributes in many ways to the literature. The provided examples are helpful to understand the coverage of the partial monitoring model.\n\n2. The proposed algorithm is simple yet principled to obtain the proven instance-dependent regret bound. Explanations on the terms that appear in the regret bound provides understanding of the procedure.\n\n**Weaknesses**\n\n1. The paper is quite focused on technical description and the novelty or significance of the results are not highlighted well. I suggest including comparison with other works especially for Lemma 4,5 and Theorem 11. Including the literal meaning of definitions of $\\Lambda, H$ and $B$.", "was_revised": true, "final_justification": "I appreciate the author's detailed responses.\nThe responses helped me understand the work better with clear novelty.\nI will keep my score as is with higher confidence.", "rebuttal": "We thank the reviewer for their comments and questions. We address below the raised concerns.\n\n> The paper is quite focused on technical description...Could authors provide an overview of the analysis on locally observable and globally observable cases, before going into the proof, respectively?...What are the main challenges to derive the results in locally and globally observable cases?\n\nWe kindly refer the reviewer to our first response to Reviewer 5qSe as it touches a similar comment. In short, we remark that most of the main body is devoted to providing an overview of the key aspects in designing the algorithm and analyzing it. In particular, Sections 4 and 5 are indeed mostly dedicated to laying down the main ideas of the analysis for globally and locally observable games, highlighting the challenges posed in each of the two observation regimes and pointing out the new techniques we employed in compared to finite partial monitoring works, all without detailing full formal proofs.\n\n> [T]he novelty or significance of the results are not highlighted well. I suggest including comparison with other works especially for Lemma 4,5 and Theorem 11...What is the novel technique developed in this paper?\n\nRegarding novelty and significance, we kindly refer the reviewer to our second response to Reviewer 5qSe. There, we point to a main novel technique discussed in Section 4 (regarding the choice of exploration distributions in the analysis of locally observable games), and discuss further the significance of our bounds in references to known results in the literature. This latter aspect is expanded upon further still in our first response to Reviewer bC8o, to which we kindly refer the reviewer for more details.\n\nRegarding the subset of the results cited by the reviewer, the results in Section 3 (which include Lemmas 4 and 5) motivate and explain the EXO approach in our particular setting. The general exposition in that section is naturally inspired by previous works on EXO like [30] and [33], as highlighted in the text, with the distinguishing aspect being our choice of estimator and how it affects the structure of the optimization problem characterizing the algorithm. In particular, Lemma 4 is a generic regret decomposition and, Lemma 5 further instantiates this result in light of our choice of estimator; both results motivate the definition of $\\Lambda$ and the design of Algorithm 1. Theorem 11 is the analogue of Theorem 10 in the globally observable case. It provides a general bound on $\\Lambda^*$, which leads to a $T^{2/3}$ bound that depends on a game-dependent constant. This provides a clear dependence on the game structure compared to [30] and rivals the bounds obtained in [24,25] in the stochastic setting.\n\n> Could authors explain the definition of $\\Lambda$, $H$ and $B$?\n\nThe function $\\Lambda_{\\eta, q}$ is defined in Line 242. This is the function to be minimized at every round by the learner in our EXO approach; its definition is directly dictated by the bound in Lemma 5, as mentioned in the preceding paragraph. $H$ is defined in Line 215; it is the $d \\times k$ matrix with the feature vectors of the actions as columns. $B$ is defined in Line 224; this is a different representation of the design matrix $Q$ that can be made invertible and is used to simplify some expressions."}, {"review_id": "0Df5rva8ak", "reviewer": "Reviewer_aKH4", "summary": "This paper studies the problem of adversarial linear partial monitoring with finitely many actions. This setting differs from both stochastic linear partial monitoring and finite partial monitoring, which have been studied previously. The authors show that the minimax regret rates are $O(\\sqrt{T})$ and $O(T^{2/3})$ (up to logarithmic factors) for locally observable and globally observable games, respectively. The upper bounds are achieved by combining the \"exploration by optimization\" framework of Lattimore and Szepesvári with the linear structure of the problem, resulting in a computationally efficient algorithm. The regret bounds are also specialized to various settings, such as the full-information setting and the linear bandit, recovering existing optimal results.", "questions": "No further questions.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\nI have read the main paper and skimmed through Appendices A, C, and D. The paper is clearly written, and the related works are adequately addressed. The theoretical results I checked are rigorously supported.\n\n---\n### Novelty and Significance\n\nThe adversarial linear partial monitoring is a fundamental problem in online learning, yet it has not been studied thoroughly in the literature. This paper provides a comprehensive characterization of the minimax regret rate when the action set is finite, which is a valuable contribution.\n\nAs far as I understand, the main technical contribution of the work is a computationally efficient algorithm (Algorithm 1), that cleverly leverages the linear structure within the exploration by optimization (ExO) framework. In contrast, the general ExO framework requires solving an infinite-dimensional optimization problem, which may be intractable.\n\n---\n\n# Weaknesses\n\n### The finite-action assumption\n\nThe paper assumes that there are only finitely many actions (Line 67 and 94). However, as far as I understand, the linear structure is typically used to address large or even continuous action spaces. Therefore, I am confused about the motivation and advantages of studying the finite-action linear setting. In particular,\n\n1. What is the motivation for studying the linear partial monitoring problem with *finite* actions? Are there any important applications that can be modeled by this problem?\n2. Besides computational efficiency, are there other key differences between the finite partial monitoring problem and the finite linear partial monitoring problem?\n3. What are the main challenges in extending the current results to the infinite-action case?\n\nI will raise my score if the above concerns are resolved.\n\n---\n\nThe following comments are minor.\n\n### Clarity\n\nGenerally speaking, this paper is clearly written. However, due to the complexity of the notation, it took me some time to understand the results. Below are some comments that could help improve clarity.\n\n1. In Lemma 5, the loss estimate is defined as $\\hat{y}_t = (H^\\top-\\mathbf{1}_dx_t^\\top)Q(p_t)^\\dagger M\\_{A\\_t}\\phi_t$. From my understanding, this is an unbiased estimate of the true loss $y_t$, i.e., $\\mathbb{E}_t[\\hat{y}_t]=y_t$. The definition can be derived by using least squares similar to [1, Chapter 27]. To improve clarity, an explanation of how this estimate is constructed would be helpful.\n2. Due to the complex notation, it may be difficult for readers to specialize the results (Theorem 10 and Theorem 11) to different settings. I would suggest including derivations of some of the special cases, such as full information and linear bandits, in the appendix.\n3. It is stated in Line 343-347 that \"Overall, our bounds seem more versatile [...].\" I couldn't see the reason for this claim. Could you elaborate more on the advantages of your bounds?\n\n---\n### Typos\n1. In Line 299, under the summation in the definition of $\\hat{p}$, should it be $a\\in\\mathcal{A}^\\ast$?\n2. In Line 354, I believe it should refer to Theorem 10 rather than Theorem 11.\n3. In Line 349-351, it is mentioned that in Section 4, we choose $\\hat{p}=q$. However, this does not seem to be the case (see Line 299). I assume there are some typos here.\n\n---\n\nReferences\n1. Lattimore and Szepesvári. Bandit Algorithms. 2020.", "was_revised": true, "final_justification": "My concern regarding the finite-action assumption is resolved. Please see my response to the authors below. Since this is a technically solid paper, I will recommend acceptance.", "rebuttal": "We thank the reviewer for their comments and suggestions. We address the raised questions below.\n\n> What is the motivation for studying the linear partial monitoring problem with finite actions? Are there any important applications that can be modeled by this problem? What are the main challenges in extending the current results to the infinite-action case?  Besides computational efficiency, are there other key differences between the finite partial monitoring problem and the finite linear partial monitoring problem?\n\nFirstly, considering finite actions in problems with linear structure is commonplace in the literature, especially in the adversarial setting; see, e.g., Audibert et al. (2011), Neu and Olkhovskaya (2020), and Lee et al. (2021). In such settings, one strives to achieve regret bounds that depend on the dimension $d$ of the space where the actions live, as opposed to the number of actions $k$ (or at least only logarithmically so) so that one can handle very large actions sets while incurring small regret. This mild dependence on the number of actions also allows obtaining  guarantees for compact action sets via discretization arguments, see Dani et al. (2007) and Bubeck et al. (2012).\n\nIn our case, considering a finite actions setting in partial monitoring (as is the usual case in prior works on adversarial partial monitoring, e.g., [29,33]) still allows modeling interesting problems like the composite graph feedback problem and the linear dueling bandits problem that we discuss in the manuscript. Moreover, as we mention in our third response to Reviewer bC8o, it is important to note that passing to the continuous action set case is challenging and requires new ideas in the analysis. In fact, already in the stochastic setting, obtaining a full classification theorem for the regret in this case is still an open problem [24,25]; the example provided in [24, Section 2.4] shows that in determining the achievable rate in $T$, the geometry of the action set also matters, besides the observability conditions.\n\nCompared to finite partial monitoring (i.e., finite actions \\emph{and} outcomes), the linear setting allows the outcome set to be infinite, which lends more modeling power to the framework. Moreover, the linear setting provides a more intuitive observation structure, free from the combinatorial complications of the finite model. Thanks to this structure, we are able to obtain bounds that do not depend on the number of outcomes and depend only logarithmically on the number of actions. Instead, the problem complexity is captured in the bounds by the features' dimension $d$ (or more refined quantities) and interpretable game-dependent constants like $\\beta_\\mathrm{loc}$ and $\\beta_\\mathrm{glo}$ that provide a measure of the alignment between observations and losses.\n\nReferences:\n\nAudibert, J. Y., Bubeck, S., \\& Lugosi, G. Minimax policies for combinatorial prediction games. COLT 2011.\n\nNeu, G., \\& Olkhovskaya, J. Efficient and robust algorithms for adversarial linear contextual bandits. COLT 2020.\n\nLee, C. W., Luo, H., Wei, C. Y., Zhang, M., \\& Zhang, X. Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. ICML 2021.\n\nDani, V., Kakade, S. M., \\& Hayes, T. The price of bandit information for online optimization. NeurIPS 2007.\n\nBubeck, S., Cesa-Bianchi, N., \\& Kakade, S. M. Towards minimax policies for online linear optimization with bandit feedback. COLT 2012.\n\n> It is stated in Line 343-347 that \"Overall, our bounds seem more versatile [...].\" I couldn't see the reason for this claim. Could you elaborate more on the advantages of your bounds?\n\nThis is in reference to the bounds of [24] and [25] in the stochastic setting. (We also discuss their results further in our first response to Reviewer bC8o.) Our remark about versatility was meant to highlight that our bounds can recover near-optimal results in feedback-rich problems like full information and feedback graphs. In contrast, the bounds in [24] and [25] always depend polynomially on the dimensionality of the loss space or the space spanned by the columns of the observation matrices, which results in a polynomial (and sub-optimal) dependence on the number of actions in the aforementioned problems. Nonetheless, a more refined analysis of their information directed sampling approach can likely recover the optimal bounds for these problems in the stochastic setting.\n\n> Typo 1: In Line 299, under the summation in the definition of $\\hat{p}$, should it be $a\\in\\mathcal{A}^*$?\n\nIt can be written either way. Indeed, $q$, via its definition in (4), gives zero weight to actions outside of $\\mathcal{A}^*$.\n\n> Typo 2: In Line 354, I believe it should refer to Theorem 10 rather than Theorem 11.\n\nYes, thanks for pointing this out.\n\n> Typo 3: In Line 349-351, it is mentioned that in Section 4, we choose $\\hat{p}=q$. However, this does not seem to be the case (see Line 299). I assume there are some typos here.\n\nThe choice of $\\hat{p}=q$ (in Lines 349-351) is made in the globally observable case, whereas line 299 refers to the choice of $\\hat{p}$ in the locally observable case. This key component is chosen differently in the analysis of locally and globally observable games."}]

Author rebuttal:

Meta-review: This paper considers the linear partial monitoring problem under the adversarial environment. The approach of exploration-by-optimization (EXO) is extended to the linear setting and an instance-dependent regret bounds (in the sense of the adversarial setting) are derived for locally- and globally-observable games.

While the reviewers appreciated the theoretical importance of the result, they also raised similar concerns on the presentation and the relation with existing work. I agree with these opinions; while it is somewhat unavoidable that the explanation on partial monitoring tends to notation-heavy due to its inherent complexity and generality, I don't think that the proposed adaptation of EXO is well-positioned in comparison with those for other settings. In particular, while I understand that the approach is different from the existing EXO for partial monitoring with finite feedback symbols in not using the water-transfer operator, the essential benefit of the proposed approach does not seem to be formally discussed enough. Still, the reviewers also shared the opinion that there is enough contribution in the clear characterization of the EXO for linear partial monitoring and the derived bound, based on which I determined to recommend acceptance. I expect that the authors carefully improve the manuscript addressing the raised concerns in the final version.

The writing issue I found is the wrong references. Some references are not cited in the main body. Nevertheless, the supplementary material has another reference list, while the reference numbers for papers are not the same between the main body and the supplementary. Please also correct this issue.
Decision: Accept (poster)