Practical Contextual Bandits with Feedback Graphs
Authors: Mengxiao Zhang
Yuheng Zhang
Olga Vrousgou
Haipeng Luo
Paul Mineiro
Venue: NeurIPS 2023 poster (2023)
Keywords: Online learning with feedback graphs
Contextual Bandits
Practical algorithms

Abstract: While contextual bandit has a mature theory, effectively leveraging different feedback patterns to enhance the pace of learning remains unclear. Bandits with feedback graphs, which interpolates between the full information and bandit regimes, provides a promising framework to mitigate the statistical complexity of learning. In this paper, we propose and analyze an approach to contextual bandits with feedback graphs based upon reduction to regression.  The resulting algorithms are computationally practical and achieve established minimax rates, thereby reducing the statistical complexity in real-world applications.

Practical Contextual Bandits with Feedback Graphs
Mengxiao Zhang
Yuheng Zhang
University of Southern California mengxiao. zhang@usc. edu
University of Illinois Urbana-Chann Chammppgn yuhengz23 www.eiiiiiinii.....ioeiiiiiiiiim edu
Olga Vrousgou
Haipeng Luo
Microsoft Research
University of Southern California ha haipengl Sushnggluuseee.m edu
Olga. Vww.sgouuuiiccooooooooooo www.sagoommmccooc.ttt.cooo
Paul Mineiro
Microsoft Research
pmineeirommicrooff... com
Abstract
While contextual bandit has mature theory, effectively leveraging different feed- back patterns to enhance the pace of learning remains unclear. Bandits with feed- back graphs, which interpolates between the full information and bandit regimes, provides a promising framework to mitigate the statistical complexity of learning. In this paper, we propose and analyze approach to contextual bandits with feedback graphs based upon reduction to regression. The resulting algorithms are computationally practical and achieve established minimax rates, thereby reducing the statistical complexity in real-world applications.
Introduction
This paper is primarily concerned with increasing the pace of learning for contextual bandits [Auer al., 2002, Langford and Zhang, 2007]. While contextual bandits have enjoyed broad applicabil- ity [Bouneffouf et al., 2020], the statistical complexity of learning with bandit feedback imposes data lower bound for application scenarios [Agarwal et al., 2012]. This has inspired various mitigation strategies, including exploiting function class structure for improved experimental design [Zhu and Mineiro, 2022], and composing with memory for learning with fewer samples [Rucker et al., 2022]. In this paper we exploit alternative graph feedback patterns to accelerate learning: intuitively, there is no need explore potentially suboptimal action a presumed better action, when exploited, yields the necessary information.
The framework of bandits with feedback graphs is mature and provides solid theoretical foundation for incorporating additional feedback into an exploration strategy [Mannor and Shamir, 201 1, Alon al.. 2015, 2017]. Succinctly, in this framework, the observation of the learner is decided by directed feedback graph G: when an action is played, the learner observes the loss of every action which the chosen action is connected. When the graph only contains self-loops, this problem reduces to the classic bandit case. For non-contextual bandits with feedback graphs, [Alon et al., 2015] provides full characterization on the minimax regret bound with respect to different graph theoretic quantities associated with G according to the type of the feedback graph.
However, contextual bandits with feedback graphs have received less attention [Singh al., 2020, Wang et al., 2021]. Specifically, there no prior work offering a solution for general feedback graphs
"qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and function classes. In this work, we take an important step in this direction by adopting recently developed minimax algorithm design principles in contextual bandits, which leverage realizability and reduction to regression to construct practical algorithms with strong statistical guarantees [Foster et al., 2018, Foster and Rakhlin, 2020, Foster et al., 2020, Foster and Krishnamurthy, 2021, Foster et al., 2021, Zhu and Mineiro, 2022]. Using this strategy, we construct a practical algorithm for contextual bandits with feedback graphs that achieves the optimal regret bound. Moreover, although our primary concern is accelerating learning when the available feedback is more informative than bandit feedback, our techniques also succeed when the available feedback is less informative than bandit feedback, e.g., in spam filtering where some actions generate no feedback. More specifically, our contributions are as follows.
Contributions. In this paper, we extend the minimax framework proposed in [Foster et al., 2021] to contextual bandits with general feedback graphs, aiming to promote the utilization of different feedback patterns in practical applications. Following [Foster and Rakhlin, 2020, Foster et al., 2021, Zhu and Mineiro, 2022], we assume that there is an online regression oracle for supervised learning on the loss. Based on this oracle, we propose Square G, the first algorithm for contextual bandits with feedback graphs that operates via reduction to regression (A (Algorithm 1). Eliding regression regret factors, our algorithm achieves the matching optimal regret bounds for deterministic feedback graphs, with ((VaT) regret for strongly observable graphs and Ö(d's T regret for weakly observable graphs. where a and d are respectively the independence number and weakly domination number of the feedback graph (see Section 3.2 for definitions). Notably, SquareCB. G is computationally tractable, requiring the solution to a convex program (Theorem 3.6), which can be readily solved with off-the-shelf convex solvers (Appendix A.3). In addition, we provide closed-form solutions for specific cases of interest (Section 4), leading to more efficient implementation of our algorithm. Empirical results further showcase the effectiveness of our approach (Section 5).
2 Problem Setting and Preliminary
Throughout this paper, we let [n]] denote the set {1, n2 for any positive integer n. We consider the following contextual bandits problem with informed feedback graphs. The learning process goes in T rounds. At each round t E [T], an environment selects a context x E X, a (stochastic) directed feedback graph G2 E [0, A] and loss distribution P,- X' A(| 1}^); where A is the action set with finite cardinality K. For convenience, we use AA and [K] interchangeably for denoting the action set. Both G, and H, are revealed to the learner at the beginning of each round t. Then the learner selects one of the actions 02 E A. while at the same time, the environment samples a loss vector l, 1J- from (-(a))).. The learner then observes some information about l, according to the feedback graph G,. Specifically, for each action j. she observes the loss of action j with probability ().. resulting in a realization A,, which is the set of actions whose loss is observed. With a slight abuse of notation, denote G+(-la) as the distribution of A, when action a is picked. We allow the context V4, the (stochastic) feedback graphs G, and the loss distribution P.(-(ara) to be selected by an adaptive adversary. When convenient, we will consider G to be a K- K-by- K matrix and utilize matrix notation.
Other Notations. Let A(K) denote the set of all Radon probability measures over a set [K]. (S) represents the convex hull of set S. Denote I as the identity matrix with an appropriate dimension. For a K -ddimensional vector v, diag(v) denotes the K-by-K matrix with the i-th diagonal entry i, and other entries 0. We use R to denote the set of K- -ddimensional vectors with non non-negative entries. For positive definite matrix M e k we define norm ||œ||ar v2 M for any vector E R
We use the ((-) notation to hide factors that are polylogarithmic in K and T.
Realizability. We assume that the learner has access to a known function class F C (X' x A + 1I) which characterizes the mean of the loss for given context-action pair, and we make the following standard realizability assumption studied in the contextual bandit literature [Agarwal et al., 2012, Foster al., 2018, Foster and Rakhlin, 2020, Simchi-Levi and Xu, 2021].
Assumption (Realizability). There exists a regression function I E F such that Elbea xx] = f (zr, a) for any a E A and across all t E [T].
2

---

Two comments are in order. First, we remark that, similar to [Foster et al., 2020], misspecificatiin can be incorporated while maintaining computational efficiency, but we do not complicate the exposition here. Second, Assumption I induces a aeemi-adversarial" setting, wherein nature is completely free to determine the context and graph sequences; and has considerable latitude in determining the loss distribution subject to a mean constraint.
Regret. For each regression function f E F, let (x+) := argmin f (Ize a) denote the induced policy, which chooses the action with the least loss with respective to f. Define π := x as the optimal policy. We measure the performance of the learner via regret to n²: RegcB == Ex lr.. - -i (x,)) which is the difference between the loss suffered by the learner and the one if the learner applies policy n..
Regression Oracle We assume access to an online regression oracle Algsa for function class F, which is an algorithm for online learning with squared loss. We consider the following protocol. At each round [T), the algorithm produces an estimator ft E conv(F), then receives set of context-action-lot tuples {z a, keE) where A, S A. The goal of the oracle is to accurately predict the loss as function the context and action, and we evaluate its performance via the square loss EuEA, (fe a) l. We measure the oracle's 's cumulative performance via the following square-loss regret to the best function in F.
Assumption 2 (Bounded square-loss regret). The regression oracle Algsq guarantees that for any (potentially adaptively chosen) sequence {(x,, a, (i,)) (e in which A₁ S A.
T
ΣV A= aEAt
(F((zr) a) 4.a inf FEF
Σ Σ aEAt
(f(z) a) - l20 < Regsa
For finite F, Vovk's aggregation algorithm yields Regs, = (log]]]) [Vovk, 1995]. This regret is dependent upon the scale of the loss function, but this need not be linear with the size of A,, e.g., the loss scale can be bounded by 2 in classification problems. See Foster and Krishnamurthy [2021] for additional examples of online regression algorithms.
Algorithms and Regret Bounds
In this section, we provide our main algorithms and results.
3.1 Algorithms via Minimax Reduction Design
Our approach is to adapt the minimax formulation of [Foster et al., 2021] contextual bandits with feedback graphs. In the standard contextual bandits setting (that is, G2 = I for all t), Foster et al. [2021] define the PrrisiionEEstimatioon Coefficient (DEC) for a parameter y as (Fc.
sup fecoPe (Fc (F: 2)), where
dec,, (F: inf dec, (p,F; Frx) PEΔ(K)
((x,a) - ( (1)
inf sup Eawp PEA(K) [[[K] l'EF
Their proposed algorithm is as follows. At each round f, after receiving the context Ir, the algorithm first computes J. by calling the regression oracle. Then, it solves the solution Pt of the minimax problem defined in Eq. (1) with f and replaced by fo and z4. Finally, the algorithm samples an action from the distribution Pt and feeds the observation (æ,, a, l. ) to the oracle. Foster et al. [2021] show that for any value 7, the algorithm above guarantees that
E Regcal T dec, (F) + 7 Regsa
(2)
However, the minimax problem Eq. (1) may not be solved efficiently in many cases. Therefore, instead of obtaining the distribution Pt which has the exact minimax value of Eq. (I), Foster et al.
3

---

Algorithm SquareCB.G. Note Theorem 3.6 provides an efficient implementation of Eq. (4).
Input: parameter 7 2 4, regression oracle Algsq
for t 2........ do
Receive context 2, and directed feedback graph G2-
Obtain an estimator ft from the oracle Algsq'
Compute the distribution pt E A(K) such that p: = argmin dec, (p: Fi, Gi), where
(ec,(p; Se, G+)
sup Banp (I(,a) (x), E La'AA
Σ (filze,a)) -S( (4)
a'=[k] fee"
and + X' x I
Sample from Pt and observe fle, HEA, where A, ~ Gi(-lar).
Feed the tuples {1r,, laa)i to the oracle Algsa
end
[2021] show that any distribution that gives an upper bound C.y on (p, xx) also works and enjoys a regret bound with (F), replaced by C, in Eq. (2).
To extend this framework to the setting with feedback graph G, we define dec, (F; f. x. G) as follows
dec, (F:J,,.. C)
inf dec, (p, Fi Fif, PEA(K)
inf sup Eucop a' f'EF
('( (xx,)')) 7 (a-G(11) 4
(3)
La'EA
Compared with Eq. (1), the difference is that we replace the squared estimation error on action by the expected one on the observed set A G(-la), which intuitively utilizes more feedbacks from the graph structure. When the feedback graph is the identity matrix, we recover Eq. (1). Based on dec, F, G), our algorithm SquareCB. G is shown in Algorithm 1. As what is done in [Foster et al., 2021], in order to derive an efficient algorithm, instead of solving the distribution ps with respect to the supremum over f E F, we solve that minimize dec, (p: f. 2z, Gt) (Eq. (4)), which takes supremum over I* (X' [K] + R), leading an upper bound on dec,, (F; J, Ie, G.). Then, we receive the loss [erj)jeA,, and feed the tuples [xt. j. bej))jeA,, to the regression oracle Algsa Following similar analysis [Foster et al., 2021], we show that to bound the regret Regcs.
only need to bound dec, (pri Fr, Nz, G.).
Theorem 3.1. Suppose dec, (pri Pey It, G.) S 8 for all t E [T] and some B > O, Algorithm 1 with = max (4, + Regs, Pil
guarantees that E [Regce] S o o Regsa
The proof is deferred to Appendix A. In Section 3.3, we give efficient implementation for solving Eq. (4) via reduction to convex programming.
3.2 Regret Bounds
In this section, we derive regret bounds for Algorithm 1 when G,'s are specialized to deterministic graphs, i.e., G, E {0, 1 We utilize discrete graph notation G = (KK),)) E),, where E S [K] x [K] and define (G,( è {i e A: (i.j) E E} as the set of nodes that can observe node In this case, at each round I, the observed node set A, is a deterministic set which contains any node satisfying o E (in i). In the following, we introduce several graph-theoretic concepts for deterministic feedback graphs [Alon et al., 2015].

---

Strongly/Weakly Observable Graphs. For directed graph G (KK), node is observable An observable node is strongly observable if either E N ( a) or N (G
[N" (G.i) i) *
[K], and weakly observable otherwise. Similarly, a graph is observable if all its nodes are observable. An observable graph strongly observable if all nodes are strongly observable, and weakly observable otherwise. Self-aware graphs are a special type of strongly observable graphs where E N (G, for all i [K].
Independent Set and Weakly Dominating Set. An independence set of directed graph is a subset of nodes in which no two distinct nodes are connected. The size of the largest independence set of graph is called its independence number. For weakly observable graph G ([K), F)), weakly dominating set is subset of nodes D C [K] such that for any node j in G without self-loop, there exists i E D such that directed edge (i, E E. The size of the smallest weakly dominating set of graph is called its weak domination number. Alon et al. [2015] show that in non-contextual bandits with a fixed feedback graph G, the minimax regret bound is (vvaT) when is strongly observable and (ddTT) when G' is weakly observable, where a and d are the independence number and the weak domination number of G, respectively.
3.2.1 Strongly Observable Graphs
In the following theorem, we show the regret bound of Algorithm for strongly observable graphs. Theorem 3.2 (Strongly observable graphs). Suppose that the feedback graph G2 deterministic and strongly observable with independence number no more than a. Then Algorithm I guarantees that
dec,, (pG: fr. Fe. G1) 50 (
(o)g(K))))
In contrast to existing works that derive a closed-form solution of pt order to show how large the DEC can be [Foster and Rakhlin, 2020, Foster and Krishnamurthy, 2021], in our case we prove the upper bound of dec, (pe: fi, x2. Gt) by using the Sion's 's minimax theorem and the graph- theor-tt lemma proven in [Alon et al., 2015]. The proof deferred to Appendix A.1. Combining Theorem 3.2 and Theorem 3.1, we directly have the following corollary:
Corollary 3.3. Suppose that G2 is deterministic, strongly observable, and has independence number no more than a for all E [T]. Algorithm I with choice = max / VaTT (ee/Ra guarantees that
Regcal S x0(1 (
For conciseness, we show in Corollary 3.3 that the regret guarantee for Algorithm depends on the largest independence number of G, over E [Z]. However, fact are able to achieve move
adaptive regret bound of order Ō (VET acRegsa where a is the independence number of G
is straightforward to achieve this by applying a standard doubling trick on the quantity Σ ag. assuming compute ay given Ge. but we take one step further and show that it is in fact unneces- sary to compute a, (which, after all, is NP-hard [Karp. 1972]): we provide an adaptive tuming strategy for y by keeping track the the cumulative value of the quantity minpe dec. (p: fr, It G.) and
show that this efficient method also achieves the adaptive ō (VVi or Rega see Appendix D for details.
regret guarantee;
3.2.2 Weakly Observable Graphs
For the weakly observable graph, we have the following theorem.
Theorem 3.4 (Weakly observable graphs). Suppose that the feedback graph G. is deterministic and weakly observable with weak domination number more than d. Then Algorithm 1 with 2 16d guarantees that
dec, Fc. x2, Gt) 1 (1 d +
ā alog(Ky) (Ky)
5

---

where ă is the independence number of the subgraph induced by nodes with self-loops in Gt-
The proof deferred to Appendix A.2. Similar to Theorem 3.2, we do not derive a closed-form solution to the strategy but prove this upper bound using the minimax theorem. Combining Theorem 3.4 and Theorem 3.1, we are able to obtain the following regret bound for weakly observable graphs, whose proof is deferred to Appendix A.2.
Corollary 3.5. Suppose that G2 is deterministic,, weakly observable, and has weak domination number no more than for all I. [T]. In addition, suppose that the independence number of the subgraph induced by nodes with self-loops in Gt is no more than i for all E [T]. Then, Algorithm d' T Regsa
with = max(16d, fāT Regsq:
guarantees that
E RegcB I Ô ( & VaTRegsa)
Similarly to the strongly observable graph case, we also derive an adaptive tuning strategy for y achieve a more refined regret bound δ ( (VEI=
(LLVVR vd.) Regsa/ where ä is the independence number of the subgraph induced by nodes with self-loops in G, and de is the weakly domination number of Gy. This is again achieved without explicitly computing āj and de see Appendix D for details.
agggss + (VEi,
3.3 Implementation
In this section, we show that solving a()) dec,, (p; J, G) in Algorithm is equivalent to solving convex program, which can be easily and efficiently implemented in practice.
Theorem 3.6. Solving argmin dec,(p; (p; f, G) is equivalent solving the following convex optimization problem.
p p
min (K)(K),
subject to
Va E [K] -111 callatag(G p) S f(z, +
7
G p
where I in the objective is shorthand for f(x,)) -) E R.K ea is the a-th standard basis vector, and > means element-wise greater.
The proof deferred to Appendix A.4. Note that this implementation not restricted the deter- ministic feedback graphs but applies to the general stochastic feedback graph case. In Appendix A.3, we provide the 20 lines of Python code that solves Eq. (5).
Examples with Closed-Form Solutions
In this section, we present examples and corresponding closed-form solutions of that make the value dec., (p: f, G) upper bounded by at most constant factor of min, dec, (p: f. x. G). This offers an alternative to solving the convex program defined in Theorem 3.6 for special (and practically relevant) cases, thereby enhancing the efficiency of algorithm. All the proofs are deferred to Appendix B.
Cops-and- Robbers Graph. The "cops-aandrrobbers" feedback graph GeR 11 - T, also known as the loopless clique, is the full feedback graph removing self-loops. Therefore, GeR is strongly observable with independence number = 1. Let a be the node with the smallest value of ʃ and a2 be the node with the second smallest value of f. Our proposed closed-form distribution p is only supported on {a1, 02) and defined as follows:
Cops-and-Robbers
Par
2 + 7F - -Sa)"
Paz 2 T - -aa))
(6)

---

In the following proposition, we show that with the construction of pf in Eq. (6), dec, (p; f.z, f,z,Ge GCR) is upper bounded by ((7/), which matches the order of min, dec, (p; f I. G) based Theorem 3.2 since a = 1.
Proposition 1. When G = GCR, given any J. context the closed-form distribution p in Eq. (6)
guarantees that dec., (p; f GCR) S O
Apple Tasting Graph. The apple tasting feedback graph GAT
consists two nodes,
where the first node reveals all and the second node reveals nothing. This scenario originally proposed by Helmbold et al. [2000] and recently denoted the spam filtering graph [van der Hoeven al., 2021]. The independence number of GAT is 1. Let fi be the oracle prediction for the first node and let fa be the prediction for the second node. We present closed-form solution p for Eq. (4) as follows:
f S f2 J 12
P1
P2 1 P1-
4+ f2)
We show that this distribution p satisfies that dec, (p: J a. GAT) is upper bounded by ((17) in the following proposition. We remark that directly applying results from [Foster et 2021] cannot lead to valid upper bound since the second node does not have a self-loop.
Proposition When G GTT. given any f. context a, the closed-form distribution p in Eq. (7) guarantees that dec (p; F, GAT S O
Inventory Graph. this application, the algorithm needs to decide the inventory level order to fulfill the realized demand arriving at each round. Specifically, there are K possible chosen inventory levels 01 < 02 < ... < 0K and the feedback graph Giny has entries G(i,j) = for all otherwise, meaning that picking the inventory level a, informs about all actions ajzı- This is because items are consumed until either the demand or the inventory is exhausted. The independence number of Ginv 1. Therefore, (very) large K is statistically tractable, but naively solving the convex program Eq. (5) requires superlinear K computational cost. We show in the following proposition that there exists analytic form of p, which guarantees that dec, (p: f. x, Giuv) can be bounded by ((1²).
1 i S K and G(i.j)
Ginv, given any J, context x, there exists closed-form distribution p E A(K) guaranteeing that dec, (p: J, Gine) S (+)), where is defined as follows: Pj = max 14707, f.) ΣE>>D''' 0 0} for all j E [K].
Proposition 3. When
Undirected Self-Aware Graph. For the undirected and self-aware feedback graph G, which means that symmetric and has diagonal entries all 1, we also show that certain closed-form solution of p satisfies that dec, (p: f. x, G) is bounded by ($))
Proposition 4. When G an undirected self-aware graph, given any F, context x, there exists flosed-form distribution p E A(K) guaranteeing that (p; G) < O
Experiments
In this section, we use empirical results to demonstrate the significant benefits of SquareCB.c G in leveraging the graph feedback structure and its superior effectiveness compared SquareCB. Following Foster and Krishnamurthy [2021], we use progressive validation (PV) loss as the evaluation metric, defined as [Tv(T) = + b.a.. All the feedback graphs used in the experiments are deterministic. We run experiments on CPU Intel Xeon Gold 6240R 2.4G and the convex program solver is implemented via Vowpal Wabbit [Langford et al., 2007].
7

---

SquareCB.G SquareCB
0.6
0.9
PV Loss
0.7
0.4
PV
0.5
0.3
0.3
Bandit Graph
Full Information Graph
Cops and Robbers Graph
Iterations
Iterations
Figure 1: Left figure: Performance of SquareCB.G on RCV1 dataset under three different feedback graphs. Right figure:
Performance comparison between SquareCB.c and SquareCB under random directed self-aware feedback graphs.
5.1 SquareCB.G under Different Feedback Graphs
In this subsection, we show that our SquareCB.G benefits from considering the graph structure by evaluating the performance of SquareCB. G under three different feedback graphs. We conduct experiments on RCVI dataset and leave the implementation details in Appendix C.I.
The performances of SquareCB.c G under bandit graph, full information graph and cops- hops-and-robbers graph are shown in the left part Figure We observe that SquareCB. performs the best under full information graph and performs worst under bandit graph. Under the cops cops-and-robbers graph, much of the gap between bandit and full information is eliminated. This improvement demonstrates the benefit of utilizing graph feedback for accelerating learning.
5.2 Comparison between SquareCB.C G.G and SquareCB
In this subsection, we compare the effectiveness of SquareCB. G with the SquareCB algorithm. To ensure fair comparison, both algorithms update the regressor using the same feedbacks based on the graph. The only distinction lies in how they calculate the action probability distribution. We summarize the main results here and leave the implementation details in Appendix C.2.
5.2.1 Results Random Directed Self-aware Graphs
We conduct experiments on RCVI dataset using random directed self-aware feedback graphs. Specif- ically, at round t, the deterministic feedback graph G, is generated follows. The diagonal elements of G2 are all 1, and each off-diagonal entry is drawn from a Bernoulli(3/4) distribution. The results presented in the right part of Figure Our SquareCB.C G consistently outperforms SquareCB and demonstrates lower variance, particularly when the number of iterations was small. This is because when there are fewer samples available train the regressor, it is more crucial design effective algorithm that can leverage the graph feedback information.
5.2.2 Results Synthetic Inventory Dataset
In the inventory graph experiments, we create synthetic inventory dataset and design loss function for each inventory level o, [0, with demand d, E [o, 1]. Since the action set [0, 1] is continuous, we discretize the action set in two different ways to apply the algorithms.
Fixed discretized action set. this setting, we discretize the action set using fixed grid size E E (10 300 300 which leads to finite action set A of size + 1. Note that according Theorem 3.2, our regret does not scale with the size of the action set (to within polylog factors), as the independence number is always 1. The results are shown in the left part of Figure 2.

---

Fixed Action Set
Adaptive Action Set
SquareCB, SquaraCe, kx301
SquareCa
SquareCa.G
SquareCa, ked01
SquareCB.G.
0.13
SquareCB. G, k-301
0.12
SquareCa.G, kmd01
PV Loss
0.11
0.09
0.08
0.07
0.06
0.08
10' Iterations
Iterations
Figure 2: Performance comparison between SquareCB.G G and SquareCB synthetic inventory dataset. Left figure: Results under fixed discretized action set. Right figure: Results under adaptive discretization of the action set. Both figures show the superiority of SquareCB.G compared with SquareCB.
We remark several observations from the results. First, our algorithm SquareCB. G outperforms SquareCB for all choices K E {101,301, 501}. This indicates that SquareCB. G utilizes a bet- ter exploration scheme and effectively leverages the structure of Givv Second, we observe that SquareCB. G indeed does not scale with the size of the discretized action .A, since under different discretization scales, SquareCB. has similar performances and the slight differences are from the improved approximation error with finer discretization. This matches the theoretical guarantee that we prove in Theorem 3.2. On the other hand, SquareCB does perform worse when the size of the action set increases, matching its theoretical guarantee which scales with the square root of the size of the action set.
Adaptively changing action set. In this setting, adaptively discretize the action set [0, 1] according to the index of the current round. Specifically, for SquareCB. G, we uniformly discretize the action set [o, 1] with size [VE], whose total discretization error (VTT) due to the Lipschitzness of the loss function. For SquareCB, optimally balance the dependency and the discretization error, we uniformly discretize the action [0, I] into [ actions. The results are illustrated in the right part of Figure 2. We can observe that SquareCB.G consistently outperforms SquareCB by clear margin.
the size of the action
6 Related Work
Multi-armed bandits with feedback graphs have been extensively studied. An early example is the apple tasting problem Helmbold et [2000]. The general formulation was introduced by Mannor and Shamir [201 I]. Alon et al. [2015] characterized the minimax rates in terms of graph- theoretic quantities. Follow-on work includes relaxing the assumption that the graph observed prior to decision [Cohen et al., 2016]; analyzing the distinction between the stochastic and adversarial settings [Alon et al., 2017]; considering stochastic feedback graphs [Li et al., 2020, Esposito et al., 2022]; instance- instance-adaptivity [Ito et al., 2022]; data-dependent regret bound [Lykouris et al., 2018, Lee et al., 2020]; and high-probability regret under adaptive adversary [Neu, 2015, Luo et al., 2023].
The contextual bandit problem with feedback graphs has received relatively less attention. Wang al. [2021] provide algorithms for adversarial linear bandits with uninformed graphs and stochastic contexts. However, this work assumes several unrealistic assumptions on both the policy class and the context space and not comparable to our setting, since we consider the informed graph setting with adversarial context. Singh al. [2020] study stochastic línear bandits with informed feedback graphs and are able to improve over the instance-optimal regret bound for bandits derived in [Lattimore and Szepesvari, 2017] by utilizing the additional graph- based feedbacks.

---

Our work is also closely related to the recent progress in designing efficient algorithms for classic contextual bandits. Starting from [Langford and Zhang. 2007], numerous works have been done the development of practically efficient algorithms, which are based on reduction to either cost-sensitive classification oracles [Dudik al., 2011, Agarwal al., 2014] or online regression oracles [Foster and Rakhlin, 2020, Foster et al., 2020, 2021, Zhu and Mineiro, 2022]. Following the latter trend, our work assumes access to an online regression oracle and extends the classic bandit problems to the bandits with general feedback graphs.
7 Discussion
In this paper, we consider the design of practical contextual bandits algorithm with provable guaran- tees. Specifically, propose the first efficient algorithm that achieves near-optimal regret bound for contextual bandits with general directed feedback graphs with an online regression oracle.
While we study the informed graph feedback setting, where the entire feedback graph is exposed to the algorithm prior to each decision, many practical problems of interest are possibly uninformed graph feedback problems, where the graph is unknown at the decision time. It is unclear how to formulate an analogous minimax problem to Eq. (1) under the uninformed setting. One idea is to consume the additional feedback in the online regressor and adjust the prediction loss to reflect this additional structure, c.g., using the more general version of the E2D framework which incorporates arbitrary side observations [Foster et al., 2021]. Cohen et al. [2016] consider this uninformed setting in the non-contextual case and prove a sharp distinction between the adversarial and stochastic settings: even if the graphs all strongly observable with bounded independence number, in the adversarial setting the minimax regret is ( whereas in the stochastic setting the minimax regret due to realizability of the mean loss, and
is (vaTT). Intriguingly, our setting is therefore it apriori unclear whether the negative adversarial result applies.
In addition, bandits with graph feedback problems often present with associated policy constraints, e.g., for the apple tasting problem, it is natural to rate limit the informative action. Therefore, another interesting direction is to combine our algorithm with the recent progress in contextual bandits with knapsack [Slivkins and Foster, 2022], leading more practical algorithms.
Acknowledgments
HL and MZ are supported by NSF Awards IIS- 1943607.
References
Alekh Agarwal, Miroslav Dudfk, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26.
PMLR, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
Noga Alon, Nicolo Dasa--Binchhi, Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. Advances in Neural Information Processing Systems, 26. 2013.
Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pages 23-35. PMLR, 2015.
Noga Alon, Nicolo Cesa-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-1822 2017.
Peter Auer, Nicolo Cesa-Bianchi Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 22(1):48-77 2002.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey applications of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1-8. IEEE, 2020.
10

---

Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. International Conference on Machine Learning, pages 811-819. PMLR, 2016.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Seventh Conference on Uncertainty Artificial Intelligence, pages 169-178, 2011.
Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven, and Nicolò Cesa- Besa-Bianchi, Learning on the edge: Online learning with stochastic feedback graphs. In Advances in Neural Information Processing Systems, 2022.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548, PMLR, 2018.
Dylan J Foster and Akshay Krishnamurthh. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances Neural Information Processing Systems, 33:1 1 1489, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 1xXi:2212.113493 2021.
David Helmbold, Nicholas Littlestone, and Philip M Long. Apple tasting. Information and Computation, 161(2)85-139, 2000.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems, 2022.
Richard M Karp. Reducibility among combinatorial problems. page 85-103, 1972.
John Langford and Tong Zhang. The spoch-greedy algorithm for contextual multi-armer bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
John Langford, Lihong Li, and Alex Strehl. Vowpal wabbit online learning project, 2007.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. Artificial Intelligncce and Statistics, pages 728-737. PMLR, 2017.
Chung-Wer Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, pages 6-644. PMLR, 2020.
David D Lewis. Yiming Yang, Tony Russell-Rose, and Fan Li. Rev1: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361-397, 2004.
Shuai Li, Wei Chen, Zheng Wen, and Kwong-Saa Sak Leung. Stochastic online learning with probabilistic graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 4675-4682, 2020.
Haipeng Luo, Hanghang Tong, Mengxiao Zhang, and Yuheng Zhang. Improved high-probability regret for adversarial bandits with time-varying feedback graphs. In International Conference Algorithmic Learning Theory, pages 1074-1100. PMLR, 2023.
Thodoris Lykouris. Karthik Sridharan, and Êva Tardos. Small-loss bounds for online learning with partial information. In Conference on Learning Theory, pages 979-986. PMLR, 2018.
Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. Advances in Neural Information Processing Systems, 24, 2011.

---

Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perfone pettheefformance deep learning library. Advances in neural information processing systems, 32, 2019.
Mark Rucker, Joran T Ash, John Langford, Paul Mineiro, and Ida Momennejad. Eigen memory tree. arXiv preprint arXiv:2210. 14077, 2022.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
Rahul Singh, Fang Liu, Xin Liu, and Ness Shroff. Contextual bandits with side-observations. arXiv preprint arXiv:2006.0395/ 2020.
Aleksandrs Slivkins and Dylan Foster. Efficient contextual bandits with knapsacks via regression. arXiv preprint arXiv:2211.07484 2022.
Dirk van der Hoeven, Federico Fusco, and Nicolò Cesa-Bianchi. Beyond bandit feedback in online multiclass classification. Advances in Neural Information Processing Systems, 34: 14800-1113 2021.
Vladimir G Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
Lingda Wang. Bingcong Li, Huozhi Zhou, Georgios B Giannakis, Lav Varshney, and Zhizhen Zhao. Adversarial linear contextual bandits with graph-structured side observations. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10156-10164, 2021.
Yinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning in continu- ous action spaces. In International Conference on Machine Learning, pages 27574-27590. PMLR, 2022.
12

---

A Omitted Details in Section 3
Theorem 3.1. Suppose (pt: Jo Ft, Gt) Cy- for all t (T] and some B > Algorithm /
with y max(4, (CT) * Regsa #41 guarantees that E |Regcal & O C Regsa
Proof. Following [Foster et al., 2020], we decompose RegeB as follows:
E E[RegBB
E
(21, az) - Σ (
E
(2) - -f (x,)
2 (
Σ -
LaEn
T
2/ )
2 E
Σ (f(
+
E BA-G((laa
4
LaEd
<
E
max [[
Baiapi - ((xt; -1(r, 7 BAnca(aa
Σ
[((set) Mar,, (()
]E(Xx(
LOEA
7
E
E BAGa(lod
Σ
- (f
LaEd
T
dec, (pe: Fe, xe, Gi)
?
T
Σ
-f(( (z))a)) 2
E
+
E BA-G((la
(8)
4
LEEd
CT
+
E
E BA-Gillas
Σ
F(( -f
1=1
LaE
Next, since E(lr,a
xr]
= 1' for all E [T] and a E A, we know that
(e((sr))) - a)) a)) 2 )
E
E
LaEA
Σ ()( - laa) ) - >5 (M le,a2²
E
BANGi(lee)
< Regsa (9)
LoEd
aEA
where the final inequality is due Assumption 2.
Therefore, we have
E Regeal S CTT--3 8 ? Regsa
Picking 7 max 4,
CT Regsa
obtain that
Regcs] < (0:0000000000 (cotrrrati Regs
गF
A.1 Proof of Theorem 3.2
Before proving Theorem 3.2, we first show the following key lemma, which is useful in proving that dec,, (p: f.x, G') is convex for both strongly and weakly observable feedback graphs G. We
13

---

(,r.G) G) is crucial for both proving the upper bound of highlight that the convexity of dec, (p: F. minpeA(K) (pc G) and showing the efficiency of Algorithm I.
Lemma A.I. Suppose v, v, TRd with (v, > O. Then both g(x) are convex in
(u,z) and h(x))
[1- (1-(u.))) (0,0)
(0,2)
Proof. The function fxx,v) = x²/y yy is convex for >> 0 due to
2 {a,(, y
y 2 0.
By composition with affine functions, both g(x) = f((u, x) (v, x)) and h(x) = f(1-(u, (u, x)) are convex.
Theorem 3.2 (Strongly observable graphs) Suppose that the feedback graph G. is deterministic and strongly observable with independence number no more than a. Then Algorithm guarantees that
dec,, (pt: Fe, xz. Gt) S 5o log log((K)) K<)
Proof. For conciseness, we omit the subscript
Direct calculation shows that for all at [K].
E Easp
-f
7
E
(F(x,a0) - fx,
d'ENim(G.a)
K
Σ a
2 Σ
Wo - (x,
where Wa = (in Par. Therefore, taking the gradient over f" (ar, and we know that
K (" -)
K
Σ La=1
2 - W. (f(z,a)- (() )
sup
[' + R)
Σ (x) - F(z, 111 ea. Ilaiinc(w) 1.
Then, denote J K to be J(x,) -) and consider the following minimax form:
K
Σ pof((z -((x,))F((x,c1) -lp car laing(W)-1
inf sup pEA(K) E'
min max pEA(K)a'E.
Σ Paf(z,a) -(xx +
K
1
2
1 1 - pat
(10)
? axa
W.
? Wa.
pa qu)
qa (1 Po)
min max PEAR G
(pa (paFo +
(11)
W.
WWa
K
p2 (1 qa)
K
qa (1 Pa)
max min gEAx PEAK
(Pa - va)Ja Σ a=1
(12)
Wa
W
where the last equality due to Sion's 's minimax theorem and the fact that Eq. (10) convex in p E A(K) by applying Lemma A. with defined as fa.i = ( a) E), = [K],E). E [K].
and v Gn for each E [K], where ga E (0, 1]
Choose P.
444 * for all E [K]. Let be the set of nodes in [K] that have self-
Then upper bound the value above follows:
max min (EA(K) (K) PEA(K)
Σ
K
(Pa
go Ja
K
p
ga
K (a
pa)²
Wa
7 Wa
a=l
14

---

(1 )aa + 7k) -
(1 - qa) 4a (1 (1- (1-+)4. 2) 5k
1 Σ
max gEA(K)
+
7
Wa
2
1
2
(1
) + 7イ² (1
4a)
+ 9a
1 - (1 + )90)
max (EA(K)
+
7
7
Wa
2
2
1
24
9a) + 24a (1
qu
2 +
20 7
max GEA(K)
7
72
7
Wa
a=1
(Wa EjeN Pj 2 7k
for all a E [K)
K
2 K
2
2
2
Qa
(1
9a)
Lo
max (EA(K)
+
7
72
7
W.
73 a=1
W.
max GEA(K)
2
2
2
K
(1
9a)
2
Σ
La
3
2
(13)
7
72
W.
73
W.
?3
W.
SES
ag
K
2
2
(1 (al
Le
< max MEA(K)
72
Wa
73
la
K-1
aES
a&S 7k
(i & S, Wa =1
Po
2
K K-1 7K
K
8
2
(1 {a)
max yEA(K)
(K 2)
7
Wa
Next we bound
2 for each E [K]. I E [K] we have Wa 1 - Pa and W.
2qa (1
Qu)
29a 9a)
24 (1 9a)
Wa
1-
7. 140
1
1
(1 7
[) 4a)
+
K-1
5
I
qa
S
4ga
(14)
7
7
If a E S, we know that
29 (1 qo)
2q - 9a)
Wa
aES Σj (j.N"(G.a) ((1 )9j 7
aES
2((1 1 )/9 + }xx( Qu)
7 aES E EjENin(G.o ((1 --11 }) 7k
((1 2) 7k
4 aES E, JjENiN(G,a) ((1
I log (Ky),
(15)
1) + 7K
where the last inequality is due to Lemma 5 in Alon et al. [2015]. We include this lemma (Lemma E. for completeness. Combining all the above inequalities, we obtain that
K Σ
inf sup PEA(K) &
paJ a) - A(x, a²) + -1p ear Ilaingew))1
K
2 (1 - qa)
K
9a(1 - p2)
max min (EA(K) PEA(K)
Σ (pa qa) +
7 a=1
Wa
WWa
a=1
8
2
K
qa (1 {a)
a aog(({))
< max (K)(K)
50
7
7 a=1
Wa
15

---

A.2 Proof of Theorem 3,4
Theorem 3.4 (Weakly observable graphs), Suppose that the feedback graph Ge is deterministic and weakly observable with weak domination number no more than d. Then Algorithm 1 with y 2 16d guarantees that
dec-(pi; Se, Rt, G))=s ( ā log K>)
log(K))
y
where ō is the independence number of the subgraph induced by nodes with self-loops in Gt-
Proof. Similar to the strongly observable graphs setting, for weakly observable graphs, we know that
dec, (pi J, G)
max min gEAx PEAK
Σ (pa - qa) +
K
Pa
qa)
K +
qa
Pa) W.a
(16)
Wa
Choose Pa - nd)gga + 1 n1afa D} where D with |D|
d is the minimum weak
7
dominating set of G and 0 < S 4d is some parameter to be chosen later. Substituting the form of to Eq. (16) and using the fact that [fal for all [K], we can obtain that
dec, (p: f. G)
K
P
9a)
K 2u
Pa)2
I max qEAn
+ nd
W.
?Wa
a=1
Then we can upper bound the value above as follows:
dec, f, G)
K (1- nd)a + * + tn D1)² (1 (1- (u)
S max yEAR
+ nd +
Wa
a=1
K Ya
1 1- (1 7 qd)
Wa
a=1
+ 7k) (1 ya) la ((1 Qa) + 1/2 8a ndgg) )²
Qa
S max 9EAx
pd
+
7
? a&D
W.
2 (1 go) + 9u (1 qa) + 9a + ndqu
Qu
4k +1)
Wa
oED
2 (g
1 (1 qa) + 39a (1 qa)² 2- 2 + d2d.
x²(²
< max gEAr
+ nd +
7
7 a
Wa
1
3
_/ + K
+ 172 (1 - qa) + 3ga
((1 ga)
)
25 7 +
1) L
(17)
Wa
aED
Now consider a E D. If E S. then we know that W, > 7/. Otherwise, know that this node can be observed by at least one node in D, meaning that W, 2 1.. Combining the two cases above, we know that
qu + K² + n²²) (1 qu) + 340 (11 9a)² + 9 + +1 r2
Wa
16

---

3
Σ
?² + 1²) (1 (1-9a) 9a) + 9a (1- ga)2+
72 7290 90 + n/dd % )
1
96
+
m
aEn
3
Σ
+ 17 d q/ + ?2K² t
qa
la
+
72 %a
M7
REN
dn
1
0
(1 S zd and 2 16d)
m
7
n
00
(18)
where the last inequality is because 17 and > 16d. Consider & D. Let So be the set of nodes which either have a self loop or can be observed by all the other node. Recall that S represents the set of nodes with self-loop. Then similar to the derivation of Eq. (13), we know that for So.
2 210 + 7²K2)
1 (1 qa) + 3qa (1 qa)² + 2 + n
Wa
D,
24 2a) + +3ga (1- qa)² + + o
[/2
1
Wa
7
1775
(W, 2 7
i S and Wa 2 n if E [K](S)
0
Σ
aa(1 9a)
Σ
La +
Σ
+
Wa
73
73
K-1
72
770K
DEDD.aRD
aES,aED
aESp.a DUS
7k
pd
+0
Σ
df
La
+
Σ
qu 7
of
aESaaE
aESo.a DUS
(for a So, a $ S. W. 2 max K-1
7))
7k
50
Σ
aa - 4o)
1
(19)
Wa
777
DDD
For a & So. we know that Wa 2 Therefore,
(1 4a) + 3ga (1 (1-gae qa)² + 2 + P
1
l/ + ,55
7
Wa
DUS
L2
-2 )
Σ
qa + 72K2
(1 qa)
+ 3qa
(1- qa)
+
M
72
DUS,
2q
3
Σ
2qa qa)
79
722 K2
72
16
DgDuS
0
(20)
Plugging Eq. (18), Eq. (19), and Eq. (20) to Eq. (17), we obtain that
pd 1 Σ
qa qa)
dec, f,r G) S O 7 ?
(21)
Wa
aED
Consider the last term. If a E So similar to Eq. (14), we know that
(1 4a)
ga - ga)
ga ga)
<
5
5
7 nd la S O(ga),
Wa
(1 1 dn)qa I
(1
n1 90)
1
7
7K
17

---

where the last inequality is due to 2 16d and
S 1 If S, similar to Eq. (15), we know that id'
Σ
qa
9a)
qa 9a)
Wa
E (jENi ((1 -nd)g; + 7k
1
((1 3/4 - nd)daa + (1-1qu)
7
E
5 - -nn E (), (11 - - -nd)ag + 7
aES
-nddg0 + 7k -
2 Σ aES EjENin(G.))
(y 4, 11)
(11 nd))gs + 7K
S S log( ()),
(22)
where the last inequality is again due Lemma in [Alon et al., 2015] and ā is the independence number of the subgraph induced by nodes with self-loops G. Plugging Eq. (22) to Eq. (21) gives
+ (lg((?))
dec f. G) 5 nd
Picking 1) = 7d ld proves the result.
Next, we prove Corollary 3.5 by combining Theorem 3.4 and Theorem 3.1.
Corollary 3.5. Suppose that G2 is deterministic, weakly observable, and has weak domination number no more than d for all t E [2]. In addition, suppose that the independence number of the subgraph induced by nodes with self-loops Ge no more than â for all [T). Then, Algorithum with y max[16d, fār/ ( d T Regsa
-3
guarantees that
Regce I 2 à
Regs
VTTRegsa)
Proof.
Combining Eq. (8), Eq. (9) and Theorem 3.4, we can bound Regcs as follows:
E Regec 0o (11 T aT log( K7) + RegCc
Picking y max { 16d, v
(RTg/g d Regsq
finishes the proof.
A.3 Python Solution Eq. (5)
def makeProble em (nactions)) import cvxpy as op
sqrtgammaG cp. Parameter (nacciion, nactions), nenneg=True)
gartgammafhat op. Parameeer (nactions)
cp. Variable (nactions, nenneg-True) sqrtgammaz cp. Variable objective Minimize (sgrggamafhatt p sqrtganmaz) constraints
cp.sum (p) =
cp. sp.sum(l ep.quad over_ li lin pi, vi)
for i, (pi, vi) enumerate (zip (p, v)
for eai in (1 if
a else 0,)
}) <= sqrtgamma fhata + sqrtgammaz for in (sqrtgammaG @ p,)
for a, sqrtgammafhate fhata enurerate (sqrrganmaaagg
problem = cp. PpobPrele (cbjetee constraints)
assert problem.is is__dc. (dpp=True) $ proof of convexity return problem, sqrtgamnaG, sqrtgammafhat, P, sqrtgamnaz
18

---

This particular formulation multiplies both sides of the constraint in Eq. (5) by v while scaling the objective by V7. While mathematically equivalent to Eq. (5), empirically has superior numerical stability for large y For additional stability, when using this routine we recommend subtracting off the minimum value from f. which is equivalent to making the substitutions /5f Vif v min, fa constraint.
and 2 <- + vy ming Sa and then exploiting the
A.4 Proof of Theorem 3.6
Theorem 3.6. Solving argm dec, (p: x, G) is equivalent to solving the following convex optimization problem.
min ),
p f
(5)
1 -1lp en G p) S [xx, +
subject to
Va [K] -
7
G p
where J in the objective is shorthand for fxx, E R.K En is the a-th standard basis vector, and > means element-wan greater.
Proof. Denote f (*) E RRK. Note that according to the definition of G, we know that (GT p); denotes the probability that action i's loss is revealed when the selected action a is sampled from distribution p. Then, we know that
(p: F.I,G)
[fa fa f 2
sup Earop fay - fa. 4
E
Σ LEE
a' [(K]]]
f ERE
sup (p Ca. TT 7
Σ
17 1'1 (
a'=(K]
dE[K]
f"ERK
sup (p Ca. TT - 11p ear (laing((TT)) a'E(K]
x 0)
[1 17
ff max ['E[k]
1pp cur llátag(GT p)-1 c/. c..
where the third equality is by picking 1 be the maximizer and introduces constraint. Therefore, the minimization problem minpEa(K) dec, (p: x, G¹) can be written as the following constrained optimization by variable substitution:
p f
min (K)
1 1pp
subject to
Ya [K]
ea llanng p) S c f. 2,
7
G GTpx - 0.
The convexity of the constraints follows from Lemma A.I.
B Omitted Details in Section 4
In this section, provide proofs for Section 4. We define W. := En'e E Pa to be the probability that the loss of action is revealed when selecting action from distribution p. Let f= f(,-) E k and f(x,-) E K Direct calculation shows that for any at E [K].
ft = argmax Enop f(x,a) f(a,a))(a=a)-))))- - 7.
Σ a'E a'ENia(G.a)
(Fllz,d) - f(x,a'))²
FERK
19

---

(W) -p-e)) +
Car)
Therefore, substituting I into Eq. (4), we obtaín that
dec, (p: x),
max a'E(k]
1
Pa
1 2po
) + +
(23)
We
Wa
Without loss of generality, we assume the min ft 0. This is because shifting f by m f :ar:f) In the following sections, we provide proofs showing that certain closed-form of leads optimal dec, (v5 F. G) up to constant factors for several specific types of feedback graphs, respectively.
does not change the value of p Car: f).
B.1 Cops-and-Robbers Graph
Proposition 1.
When G = GCR, given any J. context x, the closed-form distribution p in Eq. (6)
guarantees that dec, (p: f, x Gcn) S O
Proof. We use the following notation for convenience: P1 := Pai P2 == Pou. fi == foz = 0,
fa == fag. For the cops-and-robbess graph and closed-form solution p in Eq. (6), Eq. (23) becomes:
dec, (p: f. GCR) max {
1 7
př
(1 (1- P1)² (1-P1)²
1 - 2po- ) (p - ea. (p-ea..)) }
P1
P1
Wa.
If a" * 01 and at + a2, we know that
1
1
(1 - (1-p1)²
1 1 2pn
+ (p- +p---aa, ear;
7
P1
P1
Wa-
Pi
2
(1 1-pp1 p1)²
+1
+ +PIsi + +pafa - Pa.
7
P1
P1
p
(1 (1-11)²
<
+1)
p1fa
(la- 2 222
7
p1
P1
1
$
+1 +1+1
f2f2
(p1 E 1. 1 2 (0.
7
1 1-11 p1
(4
(4+7fa)
-11
1
82
2 x/2
If a² = 02, we can obtain that
Pi
(1-
+
1 2pa'
car
P1
P1
Wa.
p
+
(1 p1)
+
1 2pp
+ tpift + +pefe- -
1 P1
P1
P1
<
P
(1 - (1-p1)²
+
1 1- 2(1 pP)))
-Pife
=
7 1 Pl
PL
P1
1
+1+2 - 1
<
_
- P2
(pi E 1 11 P2 E (0,
7
P1
P1
5 ( (1 + f
Fo
(p) = 24
7
20

---

If a" = 41. we have
Pi
(1 -
1 - -2pa
+
+ p ea- car
1 Pl
P1
Wa
1
(1 - (1-11)
+ 1 - 221
+ (11 - p1)
7
P1
P1
1 p1
1
(1 - p1)²
1 1 P1
+ (1 PL)f2
7
P1
1
1 2
fz
|
+
(pi E 1 1)
7
2 2+ 752
3
Putting everything together, we prove that dec, (p; J. GCR) S S o (1)
B.2 Apple Tasting Graph
Proposition 2.
When G = GAT, given any f. context the closed-form distribution p in Eq. (7)
guarantees that dec., (p; J, GTT S (
Proof. For the apple tasting graph and closed-form solution p in Eq. (7), Eq. (23) becomes:
dec, (p: fp: G)
max E'E(K]
1
P1 +
(1 p1)²
1 2pa- ) + (p- }
ca.
1
P1
War
Suppose fi 0, we know that p1 1, P2 and
1. If a= 1, we have
1
(1 p1)
1 2pa.
) <p +pp-- ca. (p-ca,))=00 =0. 0.
P1
P1
W..
2. If a² 2, direct calculation shows that
{(pu
+ (1 - p:)²
2pa
2 + (p ear 5) 5 7)
p1
P1
W..
Suppose f2 0, we know that p1 1-751' P2 =
Pı and
1. If a 1, we have
P1 + (1 (1-p1)2
2pa
+ (p car 8)
+
P1
Wa.
1
(1 - p2)
+ 2p1
P1 +
- (1 -i
7
2(1
p1)
(1 p1)ff
PP
72)
(2
(1 (1-Pi)fi
+(4+71))
4+
2h A S
4+ 7
2. If at = 2, direct calculation shows that
1
(1 - 21)²
2pa
+ (p ear, -)=
2p1
2f
3
p1 +
+ prfi
+
<
7
P1 Wa.
7
4 + +
21

---

Putting everything together, we prove that (p: GAT) S - < 5 4
B.3 Inventory Graph
Proposition 3. When G = Ginv, given any T, context n, there exists closed-form distribution
p A() guaranteeing that dec, (p: x, Gine) S O(2),, where is defined as follows: Pj =
max 1+70,--min) f.) EE>s Py. 0} for all j E [K].
Proof. Based on the distribution defined above, define A S [K] to be the set such that for all i A,
P: > and denote = |A]. We index each action in A by 1y < h2 < ... < ky K. According to the definition of ps. we know that is strictly positive only when f. < fy for all j > i and specifically, when pj O, we know that W; Σz.:P = 1
(recall that min; f since
shift f). Therefore, define WKN+: = O and we know that
dec, (p: f. Giuv)
1
P2 max
1 2pa WW
Σ
Fa.
Pk. kk
7
Wa
E'E(K]
a=1
N
(Wki
WREHi)
Fine +
+ max a'E[K]
1 2pa
Par
Wa
i=1
N-1
+
Ba + max a'E(K)
- 2pa
Par
1 1+7.k
1+
WWa
i=1
-- + Σ
3
f
fko
1 2pa
Pa
max a E[K]]
7
1 + ffk
WW..
==
According to Lemma 9 of [Alon et al., 2013] (included as Lemma E.2 for completeness), we know that
Jr. Pr 1 Tfa
Jr. PR fRz
mas(G
(24)
7
where GA is the subgraph of G' restricted to node set A and mas(G) is the size of the maximum acyelic subgraphs of G. It is direct to see that any subgraph G of Giuv has mas(G) =1
Next, consider the value of a* [K] that maximizes 1-2p ?..- Fa.. a S k1, then we know that
W and 1-2p,- - < 7. Otherwise, suppose that k; < a² I hit1 for some i E [N 1].
1
According to the definition of p. if a" + hit1 we know that Pa- = and
< Σ py
Whit Wa..
TSat
5'za"
Therefore,
2pa
Fa.
1
Sa. S 1 3
Wa.
WWa.
Otherwise, W.. Wk and 1-2p W..
Far 5 WWx.41
Prom
1_ Combining the two cases
7-
above and Eq. (24), we obtain that
5 ---- + = + 0 1
3
1 1
(p: Ginv)
7
?.
7
22

---

B.4 Undirected and Self-Aware Graphs
Proposition 4. When G is an undirected self-aware graph, given any J, context there exists closed-form distribution p E (KK) guaranteeing that dec,(p; f. x, G) S 0
Proof. We first introduce the closed-fome form of p and then show that dec, (p: f, x. G) S O Specif- ically, we first sort Ja an increasing order and choose maximal independent set by choosing the nodes greedy way. Specifically, we pick k = argmin;g[k]] f:- Then, we ignore all the nodes that are connected b and select the node with the smallest fo in the remaining node set. This forms maximal independent set C [K], which has size no more than a and is also a dominating set. Set Pa = atッF. for E [ and pt, = Ea of Pa. This a valid distribution as we only choose most a nodes and Pa I 1/a for all a E [M Now we show that dec, (p; f. x, G) = ( Specifically, we only need to show that with this choice of p. for any a' E [
Σ PaJa Pa. +
Pa
1 -2p
50 =
Wa
WW
Plugging in the form of p, we know that
Σ PaJa
K
Ja.
K
Pe 1 - 2pa
2
Wa
WWa.
Σ
fo
Sa. + - 2pa
1
(p. S Wa for all a E [K)
+ Yfa
WWa
7
1 2pa
s Fa.
( S a)
WWa.
If a" = k1, then we can obtain that 7
1-2pa
S
7W2, S 2 as ps, 2 according to the definition of for
Otherwise, note that according to the choice of the maximal independent set 1, W 2 att7fa'
some a' such that Ja. Sar. Therefore,
-Ta- + 1 1-2pa- < -aa
a a 7fa 1 < -
S 7
WW
Wa.
7
Combining the two inequalities above together proves the bound.
C Implementation Details in Experiments
C.1 Implementation Details in Section 5.1
We conduct experiments on RCVI [Lewis et al., 2004], which is a multilabel text-categorization dataset. We use subset of RCV1 containing 50000 samples and K 50 sub-classes. Therefore, the feedback graph in our experiment has K = 50 nodes. We use the oag-of-worde vector of each 47236 and treat the text categories the arms. In each
sample as the context with dimension round I, the learner receives the bag-of-words vector 2i and makes prediction E [K] as the text category. The loss is set to be L,,, if the sample belongs to the predicted category a, and lr,a, otherwise.
The function class we consider is the following linear function class:
( (ax a) (M))))d((Ms))),, M (xd),
where Sigmoid(u) I+e-= for any RR. The oracle is implemented by applying online gradient descent with learning rate searched over (0.1, 0.2, 0.5, 1, 4). As suggested by [Foster and
23

---

Krishnamurthy, 2021], we use time-varying exploration parameter " c. vat, where t is the index of the iteration, c searched over {8. 16, 32, 64, 128). and the independence number of the corresponding feedback graph. Our code is built on PyTorch framework [Paszke et al., 2019]. We run 5 independent experiments with different random seeds and plot the mean and standard deviation value of PV loss.
C.2 Implementation Details in Section 5.2
C.2.1 Details for Results Random Directed Self-aware Graphs
We conduct experiments on a subset of RCV1 containing 10000 samples with K 10 sub-classes. Our code is built on Vowpal Wabbit [Langford and Zhang, 2007]. For SqaureCB, the exploration parameter "/ at round is set to be N c VKt, where t is the index of the round and c is the hyper- parameter searched over set {8, 16, 32, 64, 128]. The remaining details are the same as described in Appendix C.I.
C.2.2 Details for Results Synthetic Inventory Dataset
In this subsection, we introduce more details in the synthetic inventory data construction, loss function constructions, oracle implementation, and computation of the strategy at each round.
Dataset. In this experiment, we create synthetic inventory dataset constructed as follows. The dataset includes data points, the t-th of which represented as (#t, d,) where x2 E I is the context and de is the realized demand given context Iz. Specifically, in the experiment, we choose m 100 and 24 's are drawn i.i.d from Gaussian distribution with mean 0 and standard deviation 0.1. The demand d, is defined as
de
0 5t.
V
where 0 E _ is an arbitrary vector and E is one-dimensional Gaussian random variable with mean 0.3 and standard deviation 0.1. After all the data points ((r,, de) de))?= are constructed, we normalize
(4-minn'err de
de [0, by setting de maxi'e de miii//irrryr d, In all our experiments, set 10000.
Loss construction. Next, we define the loss at round when picking the inventory level a, with demand d, which is defined as follows:
le h max de, 0} + bb max (d: a,, 0}
(25)
where h > 0 is the holding cost per remaining items and > 0 is the backorder cost per remaining items. In the experiment, we set h 0.25 and b 1.
Regression oracle. The function class we use in this experiment is as follows:
F= f(x a) = max(a Tx + 3),0} + b max(= To 3 a, 03, RT R
This ensures the realizability assumption according the definition of our loss function shown in Eq. (25). The oracle uses online gradient descent with learning rate ?) searched over (0.01, 0.05, 0.1, 0.1,0.5,1)
Calculation of Pt. To make SquareCB.C G more efficient, instead of solving the convex program defined in Eq. (5), we use the closed-form of pt derived in Proposition 3, which only requires O K) computational cost and has the same theoretical guarantee (up constant factor) the one enjoyed by the solution solved by Eq. (5). Similar to the case in Appendix C.I, at each round f, we pick T/ = c. vt with searched over the set (0.25, 0.5, 1, 2, 3, 4). Note again that the independence number for inventory graph is 1.
run 8 independent experiments with different random seeds and plot the mean and standard deviation value of PV loss.
24

---

D Adaptive Tuning of without the Knowledge of Graph-Theoretic Numbers
In this section, show
adaptively tune the parameter in order to regret in the strongly observable graphs case and achieve δ OVVE" ar aeRes
how
(E
vde) Regsa
E ie Regsa in the weakly observable graphs case.
D.1 Strongly Observable Graphs
In order to achieve Ö (Ei= at Rggga regret guarantee without the knowledge a,, we apply doubling trick on y based on the value of minpeα(K) dec, (p; ft, Ur Gt). Specifically, our algorithm
goes in epochs with the parameter being 7/s in the s-th epoch. We initialize m V Regsa proven in Theorem 3.2, we know that
As
? min dec, (p; fr, 04. G+) s Ö(a.).
pEA(K)
Therefore, within each epoch (with start round by), at round f, we calculate the value
Q0
Σ
min dec,, (p: Fe, u4, Gt), PEA(K)
(26)
which bounded by Ō ( 1 Er=b, 04) and is in fact obtainable by solving the convex program.
Then, we check whether Q %o Regsq. If this holds, continue our algorithm using Yai otherwise, we set Ys+1 = 2% and restart the algorithm.
Now we analyze the performance of the above described algorithm. First, note that for any t, within epoch s,
Σ 5aa)
Q+ 5
meaning that the number of epoch S is bounded by S log2 C1 log, Σig at for certain C₁ which only contains constant and log terms.
Next, consider the regret in epoch with I, [b,, e.). According to Eq. (8), know that the regret within epoch is bounded as follows:
E
Σ
(1t, az)
(Mr, x (cx))
Leel
1ET.
<
E
decy, (pri FestDe, Gi)
7s Regsa +
4
Liel.
<
E
decy, (pri Pr, Gi)
+
ace
+
Y
Regsa
7
4
< Regsa)
(27)
where the last inequality is because at round = e, - 1, Q. S 7. Regs, is satisfied. Taking summation over all S epochs, know that the overall regret is bounded
E Regcal
<
Ö(y,Regsa
Σ
(
/Regsa
==1
T
s 5 5
TRegsq
=6
Σ
ag Regsa
(28)
which finishes the proof.
25

---

D.2 Weakly Observable Graphs
For the weakly observable graphs case, to achieve the target regret without the knowledge of a and de, which are the independence number of the subgraph induced by nodes with self-loops in G2 and the weak domination number of G1, we apply the same approach as the one applied in the strongly observable graph case. Note that according to Theorem 3.4, within epoch 8, we
--m va= 2i ä+ for certain C2 >
have Qs S C2
only containing constants and log know that the number of epoch is bounded by EΣ (ELiva)
VT
factors. In the weakly observable graphs
Σ de loga
= 2 log2 C2 + max
logı
since we have
/T Reg
T Σ
VT.
7s 4C²
max
at:
Regsa
Regs
[=1
and at round / in epoch S,
E+=
ar
Er Vdr
Q C2
75
Regsa
78
V'8
meaning that epoch S will never end. Therefore, following Eq. (27) and Eq. (28), we can obtain that
Regeal S =ō 50(5
TRegsa)= =
Σ
Regsa
Σ dd
Regsa
which finishes the proof.
E
Auxiliary Lemmas
Lemma E.1 (Lemma 5 in [Alon et al., 2015]). G (V, E) be directed graph with [V| = K,
in which NV i) for all vertices i [K]. Assign each E V with a positive weight w; such
that Σm= W/ < 1 and w; 2 for all E V for some constant 0 < E <<< 2. Then
Σ
W;
4K S S4a(G)
(G.)) Wj
a(G))
where (G(G) is the independence number GGG Lemma E.2 (Lemma 9 in [Alon al., 2013]), Let G = EV,E) be a directed graph with vertex
|V = K, in which i E (G, i) for all i E []]. Let be an arbitrary distribution over [K]. Then, we have
K
Σ
Pj
S mas (G),
EjEN"(G.)) Pj
where mas(G) is the size of the maximum acyclic subgraphs of G.
26


Reviews:
[{"review_id": "ZQ4uRMeUSg", "reviewer": "Reviewer_towH", "summary": "This work studied contextual bandits with feedback graphs. The authors provided an algorithm based on the recent Decision-Estimation Coefficient (DEC) framework that finds the next-step action distribution by solving a minimax optimization problem. To address the issue that the minimax problem is hard to solve, the authors also showed that there exists an efficient implementation of the solver, and the closed-form solution also exists for some special cases. For the experiment, the authors compared the proposed algorithm with a vanilla baseline algorithm that does not utilize the feedback graph information. ", "questions": "See Weaknesses. ", "limitations": "The authors addressed the limitations. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation is clear. The overall approach to solving the contextual bandits with feedback graph is convincing. The theoretical results are sound. \n\n", "weaknesses": "The importance of this work remains unclear. The proposed algorithm is very similar to the original E2D algorithm proposed by Foster et al. 2021 with an additional expectation over the feedback graph. The analysis technique is also very similar. The key difficulty in proving the regret of SquareCBG is to build an effective estimate the DEC constant. However, from the proof of Theorem 3.2, it seems that the proof is pretty standard by following the decomposition technique developed in Foster et al. 2021 (like their Proposition 5.1), while utilizing the graph node estimation lemma proposed by Alon et al. 2015. Therefore, I would recommend the authors highlight the main challenge for them to derive the theoretical results. \n\n\nA typo. Line 62, for some action $j$-> $a_t$. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We address the issues you mentioned as follows.\n\n**1. The importance of this work remains unclear. The proposed algorithm is very similar to the original E2D algorithm proposed by Foster et al. 2021 with an additional expectation over the feedback graph. The analysis technique is also very similar. The key difficulty in proving the regret of SquareCB.G is to build an effective estimate of the DEC constant. However, from the proof of Theorem 3.2, it seems that the proof is pretty standard by following the decomposition technique developed in Foster et al. 2021 (like their Proposition 5.1), while utilizing the graph node estimation lemma proposed by Alon et al. 2015. Therefore, I would recommend the authors highlight the main challenge for them to derive the theoretical results.**\n\nWe agree that our graph-based DEC term is inspired by the work of [1]. However, the E2D algorithm is defined for general sequential learning problems and it is unclear whether this is an **efficient** algorithm for learning  for contextual bandit with **general graph** feedback due to the complexity of solving the min-max problem. In [1], all the instances of the DEC upper bound is derived in the bandit feedback case while we propose the **first efficient algorithm** for contextual bandit with general graph feedback with optimal regret bound. This is achieved by first showing that the minimax problem can be solved in an efficient way and then proving that DEC is well-bounded with respect to corresponding graph-theoretic numbers. Although the graph-theoretic lemma in [2] is an existing technique, how to apply it to bounding the specific DEC term for contextual bandit with feedback graph is unclear and requires non-trivial analysis. The analysis for contextual bandit in [1] relies on the constructive inverse gap weighting probability distribution, which is a closed form solution to the min max problem. However, this kind of closed form solution does not exist in our problem. Instead, in our analysis, we use a careful combination of Sion’s minimax theorem and the graph-theoretic lemma and achieve minimax regret bound $\\widetilde{\\mathcal{O}}(\\sqrt{\\alpha T})$ for strongly observable graphs. Moreover, we analyze the weakly observable graphs, where the available feedback is less informative than the bandit feedback. In this scenario, we also achieve the minimax regret bound $\\widetilde{\\mathcal{O}}(d^{1/3}T^{2/3})$.\n\nNotably, we also want to highlight that our contribution is not limited to the theoretical side but our algorithm is practical and can be implemented efficiently in practice. Our experimental results prove the effectiveness of our approach.\n\n**2. A typo. Line 62, for some action $j\\rightarrow a_t$**\n\nThis is not a typo. In Line 62, we consider the stochastic feedback graph case. Given the selected action $a_t$ and the stochastic feedback graph $G_t$, we observe the loss of action $j$ with probability $G_t(a_t,j)$.\n\n[1] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.\n\n[2] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pages 23–35. PMLR, 2015.\n"}, {"review_id": "hD7HfJ0og9", "reviewer": "Reviewer_q6E5", "summary": "This work studies the contextual bandits problem in the presence of a feedback graph G_t. An edge (i -> j) in G_t means that taking action a_i allows us to observe the loss for action a_j. The work extends the SquareCB algorithm to this setting, the primary difference being the way the action sampling probability p_t is learned (Eq. (1) vs Eq (4)). The authors also present regret bounds for strongly observable and weakly observable graphs where the bounds improve over the standard contextual bandits setting when the independence number and cardinality of the dominating set is small.", "questions": " - Are there any intermediate characterizations of graphs between strongly and weakly observable? In the strongly observable case, for nodes without self-loops, you require an edge from all other nodes. What if there are edges from most nodes (but not all)? Or what if most nodes are strongly observable but not all? Broadly, I am trying to understand how conservative the bounds are when the graphs are weakly observable (but perhaps not too weak). Is the algorithm expected to the complexity of the graph somehow?\n - Follow-up to the above, the regret bounds take the worst-case graph over all the rounds. You allow the graph to change over t. Does the regret of your proposed algorithm also improve when the graphs are favorable for a large number of time steps?\n\n(CB is not my area of expertise so I understand that both of the above assumptions are probably standard for doing regret analysis, but I think experimentally it would be nice to get some insight into how the actual algorithm performs relative to the theoretical regret).", "limitations": "See weaknesses part. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " - Overall I found the paper to be well-written where the setup was explained well and the notation was easy to follow.\n - This paper builds on the SquareCB algorithm. I appreciated the fact that the work makes an effort to try to separate their own contributions from the SquareCB paper.\n- The paper covers both strongly and weakly observable graphs. In general, the statements in Theorems 3.2 and 3.4 are fairly intuitive.", "weaknesses": " - By and large, the paper relies heavily on the SquareCB paper's analysis. Although the setting of feedback graphs is new, the analysis seems derivative.\n- I would suggest that the authors provide more intuition behind the proofs of the key theorems. Even though the theorem statements are easy to understand, it would be nice to get some insight into the proofs, and specifically what are steps different from the standard CB regret analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We address the issues you mentioned as follows.\n\n**1. By and large, the paper relies heavily on the SquareCB paper's analysis. Although the setting of feedback graphs is new, the analysis seems derivative.**\n\nThe analysis of SquareCB relies on the constructive inverse gap weighting probability distribution (which is a closed form solution) to bound the DEC term. However, this kind of closed form solution does not exist in the bandit with feedback graph problem. It is even unclear whether this min-max problem can be efficiently solved in the case with feedback graphs. In our analysis, we first show that the min-max problem can indeed be solved efficiently. Then, we use a careful combination of the Sion’s minimax theorem and the graph-theoretic lemma in [1] to bound the DEC term and to achieve the minimax regret for different types of feedback graphs, which is non-trivial.\n\n**2. I would suggest that the authors provide more intuition behind the proofs of the key theorems. Even though the theorem statements are easy to understand, it would be nice to get some insight into the proofs, and specifically what are steps different from the standard CB regret analysis.**\n\nThanks for the suggestion. We will highlight the differences between SquareCB regret analysis and our regret analysis in the revised version. Furthermore, we will provide additional insights of our proofs, particularly focusing on 1) proving that the min-max problem can be efficiently solved; 2) how we apply the graph-theoretic lemma in bounding the DEC term with feedback graph — a novel aspect that has not been studied before. \n\n**3. Are there any intermediate characterizations of graphs between strongly and weakly observable? In the strongly observable case, for nodes without self-loops, you require an edge from all other nodes. What if there are edges from most nodes (but not all)? Or what if most nodes are strongly observable but not all? Broadly, I am trying to understand how conservative the bounds are when the graphs are weakly observable (but perhaps not too weak). Is the algorithm expected to the complexity of the graph somehow?**\n\nAs proven in Theorem 9 of Alon et al. 2015, even if the graph has one weakly observable node, we can construct an instance such that the regret is at least $\\mathcal{O}(d^{1/3}T^{2/3})$ (and as shown in Corollary 3.5, our algorithm already achieves this minimax rate).  Regarding relative difficulty: minimax results indicate within each major graph class (strongly/weakly observable graphs) the rate is determined, but the relative difficulty of the problem is affected by an associated graph-theoretic quantity (independence or weak-domination number, respectively) which affects constants.  Our contextual results pleasantly correspond to the existing known non-contextual results.\n\n**4. Follow-up to the above, the regret bounds take the worst-case graph over all the rounds. You allow the graph to change over $t$. Does the regret of your proposed algorithm also improve when the graphs are favorable for a large number of time steps?**\n\nIn fact, our regret bound scales with respect to $\\sum_{t=1}^T\\alpha_t$ ($\\sum_{t=1}^Td_t$) in the strongly (weakly) observable case by applying a doubling trick on the choice of $\\gamma$. We refer the reviewer to our response for question 1 of Reviewer n8Cc and Reviewer WhSo for details on how to tune $\\gamma$. Therefore, when the graphs are favorable, i.e., the independence number is small, our regret bound also improves upon the one with the worst-case graph.\n\n\n[1] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pages 23–35. PMLR, 2015.\n"}, {"review_id": "TgoqsQU8iH", "reviewer": "Reviewer_n8Cc", "summary": "This work is concerned with the problem of contextual bandits with graph feedback. The authors consider a setting where the contexts and the graphs are generated in an arbitrary manner and revealed to the learner at the beginning of each round. For a given context, the mean loss of each arm is assumed to be fixed. Furthermore, it is assumed that the learner is provided with a class of functions mapping context-action pairs to their mean loss, and that this class contains the true function. Following prior works in contextual bandits, the authors use an online regression oracle to estimate the true mean losses. These estimates are then used within the estimation-to-decision framework of  Foster et al. (2021).  Within this framework, the proposed algorithm requires solving a convex program at each round, for which closed form solutions are provided for special cases of interest. The authors prove regret bounds that depend on the structure of the feedback graphs and the regret of the online regression oracle. Additionally, empirical evaluations are carried out to showcase the algorithm's ability to take advantage of the side observations provided via the feedback graphs.", "questions": "- Is it possible to obtain bounds that scale with the average independence number (or weak domination number) of the graphs perhaps via an adaptive choice of the value of gamma at each round?\n- What kind of regret bounds can we obtain for stochastic graphs using this approach?\n- Does the proposed approach offer an advantage over existing algorithms for learning with graph feedback in the non-contextual case?", "limitations": "The authors did address some of the limitations of their work. Notably the fact that their approach requires the knowledge of the feedback graph before choosing the action.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Although the adopted approach relies on existing techniques, the application of the estimation-to-decision framework of Foster et al. (2021) for bandits with graph feedback is still an interesting contribution. Most notably, in Theorems 3.2 and 3.4, the authors bound the decision estimation coefficient for their algorithm in terms of the independence number for strongly observable graphs and the weak domination number for weakly observable graphs, which respectively are the graph theoretic quantities that characterize the minimax regret for these settings. Overall, the paper is well written, the setting is adequately motivated, and the clarity of the presentation is decent.", "weaknesses": "- The regret bounds in Corollaries 3.3 and 3.5 are stated in terms of a uniform upper bound on the independence number or the weak domination number of the observed graphs. This is unsatisfactory since a single sparse graph could render the bound vacuous.\n- In the formulated setting, the graphs are allowed to be stochastic, where each edge is realized with a certain probability which is revealed to the learner at the beginning of the round. However, all the provided theoretical results are for deterministic graphs.\n- One point in need of clarification concerning the experiments is that it is mentioned in the beginning of Section 5 that all the graphs used in the experiments are deterministic, while the experiment described in Section 5.2.1 seems to involve stochastic graphs.\n- For the experiment of Section 5.1, it might be more informative to include more intermediate cases between bandits and full information.\n- A minor correction: In the discussion section, the authors address the limitation of their approach in the uniformed setting, where the feedback graph is only revealed to the learner after making a decision. The authors then cite results for the non-contextual case from (Cohen et al, 2016). However, in that work, the graph is never revealed to the learner, only the actions in the neighbourhood of the played action and their losses are observed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We address the issues you mentioned as follows.\n\n**1. The regret bounds in Corollaries 3.3 and 3.5 are stated in terms of a uniform upper bound on the independence number or the weak domination number of the observed graphs. This is unsatisfactory since a single sparse graph could render the bound vacuous. (Is it possible to obtain bounds that scale with the average independence number (or weak domination number) of the graphs perhaps via an adaptive choice of the value of gamma at each round?**\n\nThis is a good point. In fact, we write Corollary 3.3 and 3.5 with respect to the maximum independence number $\\alpha$ and maximum weak domination number $d$ only for simplicity, but our regret bound scales with respect to the averaged one $\\frac{1}{T}\\sum_{t=1}^T\\alpha_t$ and $\\frac{1}{T}\\sum_{t=1}^Td_t$ by applying a doubling trick on the choice of $\\gamma$. Specifically, for the strongly observable graph case, we set $\\gamma=\\sqrt{T}$ initially. If at some round t, $\\gamma<\\sqrt{\\sum_{\\tau=1}^t\\alpha_{\\tau}}$, then we double $\\gamma$ and restart the algorithm; otherwise, we keep using the same $\\gamma$. This gives the $\\widetilde{O}\\left(\\sqrt{\\sum_{t=1}^T\\alpha_t}\\right)$ regret bound. Applying a similar doubling trick for the weak domination number gives $\\widetilde{O}\\left(T^{1/3}\\left(\\sum_{t=1}^Td_t\\right)^{1/3}\\right)$ regret bound as well. For an improved adaptive tuning method **without even knowing/computing $\\alpha_t$ and $d_t$**, we refer to our response (1) for Reviewer WhSo.\n\n**2. In the formulated setting, the graphs are allowed to be stochastic, where each edge is realized with a certain probability which is revealed to the learner at the beginning of the round. However, all the provided theoretical results are for deterministic graphs. (What kind of regret bounds can we obtain for stochastic graphs using this approach?)**\n\nWhile our algorithm is technically defined for general stochastic graphs, in order to compare our results to the regret bound for standard bandits with feedback graphs, we consider the deterministic case and show that for both strongly observable and weakly observable graph cases, our regret bound matches the minimax rate . For stochastic graphs, if the realized feedback graphs are all strongly observable and $G_t(i,j)$ defines the marginal probability that edge (i,j) is realized, then our algorithm achieves $\\widetilde{O}\\left(\\sqrt{\\sum_{t=1}^T\\alpha_t}\\right)$ regret where $\\alpha_t$ is defined as the expected independence number given the stochastic feedback graph $G_t$. Similarly, for weakly observable graphs, our algorithm is able to achieve $\\widetilde{O}\\left(\\left(\\sum_{t=1}^Td_t^{1/3}\\right)T^{1/3}\\right)$ where $d_t$ is the expected weak domination number of the graph. To achieve this bound, we need to tune $\\gamma$ in an adaptive way and we refer the reviewer to our response (1) of reviewer WhSo.\n\n**3. One point in need of clarification concerning the experiments is that it is mentioned in the beginning of Section 5 that all the graphs used in the experiments are deterministic, while the experiment described in Section 5.2.1 seems to involve stochastic graphs.**\n\nIn Section 5.2.1, we sample a graph from a certain distribution and this (deterministic) graph is informed to the learner at the beginning of each round. Thanks for pointing this out, and we will clarify it.\n\n**4. For the experiment of Section 5.1, it might be more informative to include more intermediate cases between bandits and full information.**\n\nFollowing the reviewers suggestion, we conducted an additional experiment on dataset RCV1 with the inventory graph (whose independence number is 1) and the averaged regret is shown as follows:\n\n| round:t | averaged regret |\n|---------|-----------------|\n|  10000  |      0.3345     |\n|  20000  |      0.2739     |\n|  30000  |      0.2488     |\n|  40000  |      0.2361     |\n|  50000  |      0.2260     |\n\nwhich is close to the regret in the full-info and cops-and-robbers cases, showing that the regret indeed scales with the independence number.\n\n\n**5. Does the proposed approach offer an advantage over existing algorithms for learning with graph feedback in the non-contextual case?**\n\nNo, it does not. Our approach extends the recent framework of realizable contextual bandit with regression oracle to the more general feedback graph model and achieves the optimal regret bound in both strongly observable and weakly observable graph cases.  Our contribution is focused on the contextual bandit case.  While our approach does achieve minimax rates in the (non-contextual) bandit setting, in that setting, existing minimax-optimal algorithms (eg. Exp3.G in [1]) are available which make less assumptions and are therefore preferable (e.g., non-contextual algorithms do not require realizability as they essentially operate directly in policy space; moveover, non-contextual algorithms exist even for the uninformed graph setting). \n\nThanks for pointing out the other minor issues in the discussion section and we will fix that in the next revision.\n\n[1] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pages 23–35. PMLR, 2015.\n"}, {"review_id": "k4aH84ucjV", "reviewer": "Reviewer_WhSo", "summary": "The authors consider the adversarial contextual bandit problem with feedback graphs, in the finite function class setting with a realizability assumption, with an access to an online regression oracle. They extend previous approaches for the vanilla contextual MAB setting in order to obtain regret bounds of $\\tilde{O}(\\sqrt{\\alpha T})$ with fully observable graphs and $\\tilde{O}(d^{\\frac13} T^{\\frac23})$ for weakly observable graphs, where $\\alpha$ and $d$ denote the graph's independence number and weak domination number respectively. The authors demonstrate their results empirically and show that their algorithm performs better than existing approaches when side observations are available.", "questions": "Given the result presented in the paper, a very natural question that arises is whether or not for stochastic contexts and losses, the approach of [2] can be generalized to the feedback setting in order to obtain similar regret bounds, but with access to an **offline** regression oracle. I think such a result would be also very interesting, and I would expect that similar approaches to those that the authors used in this paper would work for extending [2], as their approach also extends SquareCB of [1]. I'd appreciate it if the authors could comment on whether or not they considered the stochastic setting as well, and if they think that they're approach could be used in order to obtain results with an offline oracle.\n\n[1] Foster, Dylan, and Alexander Rakhlin. \"Beyond ucb: Optimal and efficient contextual bandits with regression oracles.\" _International Conference on Machine Learning_. PMLR, 2020.\n\n[2] Simchi-Levi, David, and Yunzong Xu. \"Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.\" _Mathematics of Operations Research_ 47.3 (2022): 1904-1931.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The authors exhibit the first efficient algorithm for contextual bandits with feedback graphs, which obtains near-optimal regret guarantees both in the strongly observable and weakly observable settings.\n* The techniques utilized by the authors seem to neatly generalize the approach of Foster et al. ('21) to the feedback graph setting, by generalizing the inverse gap technique to solving a convex problem together with utilizing a combinatorial property of the feedback graphs.\n* The authors demonstrate in several empirical experiments that their algorithm out-performs SquareCB when feedback graphs are present, thus strengthening the idea that better performance can be obtained when side observations are available.", "weaknesses": "* This is not a very major issue, but the algorithm suggested by the authors requires knowledge of the feedback graphs' independence number (or a good bound on it), which is a hard quantity to compute in general. This is only a minor point because many previous works in the feedback graphs literature also require knowing such a parameter, but I will remark that some results can be obtained without this knowledge.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We address the issues you mentioned as follows.\n\n**1. This is not a very major issue, but the algorithm suggested by the authors requires knowledge of the feedback graphs' independence number (or a good bound on it), which is a hard quantity to compute in general. This is only a minor point because many previous works in the feedback graph literature also require knowing such a parameter, but I will remark that some results can be obtained without this knowledge.**\n\nThanks for pointing this out. In fact, for the strongly observable graph case, we are able to achieve the same regret bound **without** the knowledge of $\\alpha_t$ by picking the parameter $\\gamma$ in an adaptive way. Specifically, note that for strongly observable graphs, $\\gamma\\cdot \\min_{p\\in \\Delta_K}\\rm\\overline{dec_{\\gamma}}(p)\\leq\\widetilde{O}(\\alpha_{t})$ at round $t$. Therefore, we start from $\\gamma_1=\\sqrt{T}$ and keep track of the following value $V_t=\\sum_{\\tau=1}^t\\gamma_{\\tau}\\cdot \\min_{p\\in\\Delta_K}\\rm\\overline{dec_{\\gamma_\\tau}}(p)$, which is indeed obtainable by solving the convex program. When this value is doubled, we double $\\gamma_t$ and restart the algorithm; otherwise, we set $\\gamma_{t+1}=\\gamma_t$. This adaptive tuning does not require the knowledge of $\\alpha_t$ and achieve the same $\\widetilde{O}\\left(\\sqrt{\\sum_{t=1}^T \\alpha_t}\\right)$ regret bound with a factor of $\\log \\left(\\sum_{t=1}^T\\alpha_t/T\\right)$ overhead. \n\nFor the weakly observable graph case, since the weak domination number of a graph can be approximated efficiently within a factor of $\\log K$, we are able to apply doubling trick to adaptively tune $\\gamma$ by approximating the weak domination number directly on the sequence of observed graphs and achieve the same $\\widetilde{O}(T^{1/3}(\\sum_{t=1}^Td_t)^{1/3})$ regret bound. We will include the adaptive tuning part in the appendix in the next revision.\n\n\n**2. Given the result presented in the paper, a very natural question that arises is whether or not for stochastic contexts and losses, the approach of [2] can be generalized to the feedback setting in order to obtain similar regret bounds, but with access to an offline regression oracle. I think such a result would be also very interesting, and I would expect that similar approaches to those that the authors used in this paper would work for extending [2], as their approach also extends SquareCB of [1]. I'd appreciate it if the authors could comment on whether or not they considered the stochastic setting as well, and if they think that they're approach could be used in order to obtain results with an offline oracle.**\n\nThanks for pointing this out! In fact, in an ongoing follow-up, we have already had some results with respect to the stochastic context and loss using offline regression oracle. Specifically, we are able to obtain the same $\\widetilde{O}(\\sqrt{\\alpha T})$ regret bound when the graph is self-aware and $\\widetilde{O}(d^{1/3}T^{2/3})$ when the graph is weakly observable."}, {"review_id": "IQo1Kw68GA", "reviewer": "Reviewer_o1h9", "summary": "This paper studies online learning in a contextual setting when a feedback graph determines the feedback received by the learner. Namely, the learner observes all the losses experienced by the actions in the graph-neighborhood of the action it played. \n\nFeedback graphs are a well-known feedback model for online learning, and their study in the contextual setting is natural. The paper's main result is a general framework (Theorem 3.1) that reduces the problem to the solution at each time step of a convex program. Then the authors instantiate this general theorem for the strongly observable and weakly observable case, obtaining the same regret rates that characterize the non-contextual version of the problem. \n\nThe primary technical tool of the paper is the parameter defined in equation (3). Following Foster et al. 2021, the authors use this new formula instead of the bandit one (equation 1) to prove their results. \n", "questions": "None", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem studied is natural and well-motivated.\n- The regret bounds match the lower bounds in Alon et al., 2015, so they are tight. \n- The experimental results and the theoretical guarantees support the claim that a richer feedback structure improves the regret bounds w.r.t. the bandit case. \n- It is nice that the authors devoted some time to presenting the detailed results for some famous classes of feedback graphs. \n", "weaknesses": "- Once equation 3 is designed, the rest of the paper seems incremental to Foster et al.  \n- Equation 3 needs knowledge of the feedback graph. Therefore the paper works only in the informed setting. \n- The introductory model entails time-varying feedback graphs, while the results for strong and weakly observable feedback graphs need the graph to be deterministic and known up-front. \n\nMinor comment:\n- uniform the \\citet and \\citep notation\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. We address the issues you mentioned as follows.\n\n**1. Once equation 3 is designed, the rest of the paper seems incremental to Foster et al.**\n\nWe argue that achieving the tight regret bound with respect to the correct graph-theoretic dependence for different types of feedback graphs requires non-trivial analysis. We refer the reviewer to our response to Reviewer towH for details. \n\n**2. Equation 3 needs knowledge of the feedback graph. Therefore the paper works only in the informed setting.**\n\nYes, our work focuses on the informed graph feedback setting and we leave the uninformed setting as the future work.\n\n**3. The introductory model entails time-varying feedback graphs, while the results for strong and weakly observable feedback graphs need the graph to be deterministic and known up-front.**\n\nWe allow time-varying feedback graphs but the feedback graph needs to be informed at the beginning of each round.  Our algorithm is defined for stochastic graphs, but our analysis focuses on the deterministic graph case in order to create correspondence with classic (non-contextual) minimax bounds for bandits with deterministic feedback graphs.\n\nWe will fix the citation notations you mentioned in the next revision."}]

Author rebuttal:
We thanks all the reviewers for their valuable comments, especially for pointing out the adaptive tuning issue of the parameter of $\gamma$ without requiring knowledge of the graph-theoretic quantities and beyond the worst-case graph. We address your issues in separate sections as follows.

Meta-review: This paper studies the CB problem with stochastic feedback graphs in the informed setting. The authors propose a novel algorithm based on the SquareCB ideas. Reviewers find that the proposed approach is novel and that the paper has a good presentation. Multiple reviewers have expressed concern about the technical novelty of the proposed approach and in particular have noted that a large part of the proof follows the established approach in Foster et al. 2021. I find that the authors' rebuttal addresses the stated concerns. Multiple reviewers also note the issue with tuning $\gamma$. I find the rebuttal to address this issue, however, the authors should include the detailed derivation for the doubling trick in the final version of the paper.
Decision: Accept (poster)