Contextual bandits with concave rewards, and an application to fair ranking
Authors: Virginie Do
Elvis Dohmatob
Matteo Pirotta
Alessandro Lazaric
Nicolas Usunier
Venue: ICLR 2023 poster (2023)
Keywords: bandits
concave rewards
fairness
learning to rank

Abstract: We consider Contextual Bandits with Concave Rewards (CBCR), a multi-objective bandit problem where the desired trade-off between the rewards is defined by a known concave objective function, and the reward vector depends on an observed stochastic context. We present the first algorithm with provably vanishing regret for CBCR without restrictions on the policy space, whereas prior works were restricted to finite policy spaces or tabular representations. Our solution is based on a geometric interpretation of CBCR algorithms as optimization algorithms over the convex set of expected rewards spanned by all stochastic policies. Building on Frank-Wolfe analyses in constrained convex optimization, we derive a novel reduction from the CBCR regret to the regret of a \emph{scalar-reward} bandit problem. We illustrate how to apply the reduction off-the-shelf to obtain algorithms for CBCR with both linear and general reward functions, in the case of non-combinatorial actions. Motivated by fairness in recommendation, we describe a special case of CBCR with rankings and fairness-aware objectives, leading to the first algorithm with regret guarantees for contextual combinatorial bandits with fairness of exposure.

Published as a conference paper at ICLR 2023
CONTEXTUAL BANDITS WITH CONCAVE REWARDS, AND AN APPLICATION TO FAIR RANKING
Virginie Do
Elvis Dohmatob, Matteo Pirotta, Alessandro Lazaric, Nicolas Usunier
PSL University & Meta Al
Meta Al
vi rrginii edo@meta com
(dohmatos) tob, taceentobbpprioooooo pirttta, lazaric, usunier) (eriiierrmmeeettteeeeee @meta com
ABSTRACT
We consider Contextual Bandits with Concave Rewards (CBCR), a multi-objecctive bandit problem where the desired trade-off between the rewards is defined by a known concave objective function, and the reward vector depends on an observed stochastic context. We present the first algorithm with provably vanishing regret for CBCR without restrictions on the policy space, whereas prior works were restricted to finite policy spaces tabular representations. Our solution is based geomet- ric interpretation of CBCR algorithms as optimization algorithms over the convex set of expected rewards spanned by all stochastic policies. Building Frank- Wolfe analyses in constrained convex optimization, we derive a novel reduction from the CBCR regret to the regret of scalar-reward bandit problem. We illustrate how apply the reduction off-the-shelf to obtain algorithms for CBCR with both linear and general reward functions, in the case of non-combinatorial actions. Motivated by fairness in recommendation, we describe a special case of CBCR with rankings and fairness-aware objectives, leading to the first algorithm with regret guarantees for contextual combinatorial bandits with faimess of exposure.
INTRODUCTION
Contextual bandits are popular paradigm for online recommender systems that learn to generate personalized recommendations from user feedback. These algorithms have been mostly developed to maximize a single scalar reward which measures recommendation performance for users. Recent fairness concerns have shifted the focus towards item producers whom are also impacted by the exposure they receive (Biega et al., 2018; Geyik et al., 2019), leading to optimize trade-offs between recommendation performance for users and fairness of exposure for items (Singh & Joachims, 2019; Zehlike & Castillo, 2020). More generally, there is an increasing pressure insist on the multi- objective nature of recommender systems (Vamplew et al., 2018; Stray et al., 2021), which need to optimize for several engagement metries and account for multiple stakeholders' interests (Mehrotra et al., 2020; Abdollahpouri et al., 2019). In this paper, we focus on the problem of contextual bandits with multiple rewards, where the desired trade-off between the rewards is defined by known concave objective function, which we refer to as Contextual Bandits with Concave Rewards (CBCR). Concave rewards are particularly relevant to fair recommendation, where several objectives can be expressed as (known) concave functions of the (unknown) utilities of users and items (Do et al., 2021).
Our CBCR problem is an extension of Bandits with Concave Rewards (BCR) (Agrawal & Devanur, 2014) where the vector of multiple rewards depends on an observed stochastic context. We address this extension because contexts are necessary to model the user/item features required for personalized recommendation. Compared to BCR, the main challenge of CBCR is that optimal policies depend on the entire distribution of contexts and rewards. BCR, optimal policies are distributions over actions, and are found by direct optimization in policy space (Agrawal & Devanur, 2014; Berthet & Perchet, 2017). In CBCR, stationary policies are mappings from a continuous context space to distributions over actions. This makes existing BCR approaches inapplicable CBCR because the policy space is not amenable to tractable optimization without further assumptions or restrictions. As a matter of fact, the only prior theoretical work on CBCR is restricted finite policy set (Agrawal et al., 2016).
We present the first algorithms with provably vanishing regret for CBCR without restriction on the policy space. Our main theoretical result is reduction where the CBCR regret of an algorithm is

---

Published as a conference paper at ICLR 2023
bounded by its regret on a proxy bandit task with single (scalar) reward. This reduction shows that it is straightforward to turn any contextual (scalar reward) bandits into algorithms for CBCR. We prove this reduction by first re-parameterriznn CBCR as an optimization problem in the space of feasible rewards, and then revealing connections between Frank- Wolfe (FW) optimization in reward space and decision problem in action space. This bypasses the challenges of optimization in policy space.
To illustrate how to apply the reduction, we provide two example algorithms for CBCR with non- combinatorial actions, one for linear rewards based LinUCB (Abbasi-Yadkon) et al., 201 I). and one for general reward functions based on the SquareCB algorithm (Foster & Rakhlin, 2020) which uses online regression oracles. In particular, we highlight that our reduction can be used together with any exploration/exploitaiioo principle, while previous FW approaches to BCR relied exclusively on upper confidence bounds (Agrawal & Devanur, 2014; Berthet & Perchet, 2017; Cheung, 2019).
Since fairness of exposure is our main motivation for CBCR, we show how our reduction also applies to the combinatorial task of fair ranking with contextual bandits, leading the first algorithm with regret guarantees for this problem, and we show it is computationally efficient. We compare the empirical performance of our algorithm to relevant baselines on a music recommendation task.
Related work. Agrawal et al. (2016) address restriction of CBCR to finite set of policies, where explicit search possible. Cheung (2019) use FW for reinforcement learning with concave rewards, a similar problem to CBCR. However, they rely tabular setting where there few enough policies to compute them explicitly. Our approach is the only one to apply to CBCR without restriction on the policy space, by removing the need for explicit representation and search of optimal policies.
Our work is also related to fairness of exposure in bandits. Most previous works on this topic either do not consider rankings (Celis et al., 2018; Wang et al., 2021; Patil et al., 2020; Chen et al., 2020), or apply to combinatorial bandits without contexts (Xu et al., 2021). Both these restrictions are impractical for recommender systems. Mansoury al. (2021); Jeunen & Goethals (2021) propose heuristics with experimental support that apply to both ranking and contexts in this space, but they lack theoretical guarantees. We present the first algorithm with regret guarantees for fair ranking with contextual bandits. We provide a more detailed discussion of the related work in Appendix A.
2 MAXIMIZATION OF CONCAVE REWARDS IN CONTEXTUAL BANDITS
Notation. For any n E N, we denote by [n-] = (I....,n), ,n.. The dot product of two vectors æ and y in Rn is either denoted æT y or using braket notation (z 1). depending on which one is more readable.
Setting. We define a stochastic contextual bandit (Langford & Zhang, 2007) problem with D rewards. At each time step the environment draws context 2, ~ P, where E X' C R and P is probability measure over X. The learner chooses an action ae E A where A C R is the action space, and receives noisy multi-dimensional reward r, TR.. with expectation [//r2 a,} j(xx)ar, where : X - DxX is the matrix-valus contextual expected reward function.' The trade-off between the D cumulative rewards is specified by known concave function f R² + I ( Let A denote the convex hull of A and म. X + A be stationary policy,² then the optimal value for the problem is defined as f" = sup x f (E-~ [M(x))<(())
We rely on either of the following assumptions on
Assumption A f is closed proper concave? on R. and A is compact subset of KRKK Moreover, there is compact convex set K. S IR. such that
(Bounded rewards) V(z, a) E X A, A,x())a K. and for all t E No, Ta E KC with probability 1. (Local Lipschitzness) f is L-Lipschitz continuous with respect to |1-1|2 on an open set containing X.
Assumption B Assumption A holds and has C-Lipschitt-contiuuuus gradients w.r.f. 11-112 on K..
'Notice that linear structure between p(æz) and a, is standard in combinatorial bandits (Cesa-Bianchi & Lugosi, 2012) and it reduces to the usual multi-armed bandit setting when AA is the canonical basis of R
IIn the multi-armed setting, stationary policies return distribution over arms given context vector. In the combinatorial setup, π(Φ) E A the average feature vector of a stochastic policy over A. For the benchmark, we are only interested in expected rewards so there is to need to specify the full distribution over A. "This means that is concave and upper comi-contiuuous, is never equal 4-00 and is finite somewhere.
2

---

Published as a conference paper at ICLR 2023
The most general version of our algorithm, deseribed in Appendix D, removes the need for the smoothness assumption using smoothing techniques. We describe an example in Section 3.3. In the rest of the paper, we denote by Dx = sup || - zl112 the diameter Ic and use C = D
2,a'EK
We now give two examples of this problem setting, motivated by real-world applications in recom- mender systems, and which satisfy Assumption A.
Example 1 (Optimizing multiple metries in recommender systems.) Mehrotra al. (2020) for- malized the problem of optimizing D engagement metrics (e.g. clicks, streaming time) in a bandit- based recommender system. At each It represents the current user's features. The system chooses one arm among K, represented by vector 04 in the canonical basis of RR. which is the action space A. Each entry of the observed reward vector (re,))== corresponds to metric's value. The trade-off between the metrics is defined by the Generalized Gini Function: f(z) Eis wizk where (z.) (p denotes the values of z sorted increasingly and w E RDD is vector of non-incceaasin weights.
Example 2 (Fairness of exposure in rankings.) The goal is to balance the traditional objective of maximizing user satisfaction in recommender systems and the inequality of exposure between item producers (Singh & Joachims, 2018; Zehlike & Castillo, 2020). For a reconmendation task with m items rank, this leads to a problem with D m + objectives, which correspond the m items' exposures, plus the user satisfaction metric. The context #e E X C Rmd is a matrix where each Lz IRd represents a feature vector of item i for the current user. The action space A is combinatorial, i.e. it is the space of rankings represented by permutation matrices:
m
m
A = fa E 10.1m E [m]] Σ as =
and Vk E [[m]], Σ a. -
(1)
For E A, ai if item i is at rank k. Even though we use a double-index notation and call a permutation matrix, we flatten a as a vector of dimension = m² for consistency of notation.
We now give concrete example for which is concave usual for objective functions in fairness of exposure (Do et al., 2021). It is inspired by Morik et al. (2020), who study trade-offs between average user utility and inequality* of item exposure:
f(2)
2m++1
- 2m
Zyl
where 3 >> O is a trade-off parameter.
(2)
uillity
inequality of item exposure
The learning problem. In the bandit setting, P and μ are unknown and the learner can only interact online with the environment.Le. hr = (Ie, oe, I')) se[r-11 be the history of contexts, actions, and reward observed up to time T-1 and 8' > be a confidence level, then at step a bandit algorithm A receives in input the history h4, the current context dt, and it returns distribution over actions A and selects an action ae 2h,, Ne, 8'). The objective of the algorithm to minimize the regret
Rr f f(8T)
where š7
Σ 1=1
T
Note that setting subsumes classical stochastic contextual bandits: when D= 1 and f(=) 2, maximizing J ((T) amounts to maximizing a cumulative scalar reward Σ Yr. In Lem. 9 (App. C.3), show that alternative definitions of regret, with different choices of comparator performance measure, would yield difference of order (L1/ (1) and hence not substantially change our results.
3 A GENERAL REDUCTION-BASE APPROACH FOR CBCR
In this section we describe our general approach for CBCR. We first derive our key reduction from CBCR specific scalar-reward bandit problem. We then instantiate our algorithm the case of linear and general reward functions for smooth objectives f. Finally, we extend to the case of mon-smooth objective functions using Moreau- Yosida regularization (Rockafellar & Wets, 2009).
"Gini(21..... 2m) E ET l 2y} is an unnormalized Gini coefficient.
3

---

Published as a conference paper at ICLR 2023
3.1 REDUCTION FROM CBCR TO SCALAR-REWARD CONTEXTUAL BANDITS
There are two challenges in the CBCR problem: 1) the computation of the optimal policy sup f [(<>p[((<)<<<)) even with known Jr; 2) the learning problem when μ is unknown. #.--A
Reparameterization of the optimization problem. The first challenge is that optimizing directly in policy space for the benchmark problem -UP=:x=77 S [R [1(()) is intractable without any restriction, because the policy space includes all mappings from the continuous context space X' distributions over actions. Our solution is to rewrite the optimization problem as a standard convex constrained problem by introducing the convex set S of feasible rewards:
S 1 Ea> ([nr)(((()T(()) 7 X x A} so that f= sup f
( (Be-P|((x)F(a))
max f(s). #ES
x:X+A
Under Assumption A, S is compact subset of K. (see Lemma 7 in App. C) so f attains its maximum over S. We have thus reduced the complex initial optimization problem to a concave optimization problem over a compact convex set.
2: Reducing the learning problem to scalar-reward bandits. Unfortunately, since P and μ are unknown, the set S is unknown. This precludes the possibility of directly using standard constrained optimization techniques, including gradient descent with projections onto S. We consider Frank- Wolfe, projection-free optimization method robust approximate gradients (Lacoste-Julien et al., 2013; Kerdreux et al., 2018). At each iteration FW, the update direction is given by the linear subproblem: argmax, sES( (V s), where 24-1 is the current iterate. Our main technical tool, Lemma 1, allows to connect the FW subproblem in the unknown reward space S to a workable decision problem in the action space (see Lemma 13 in Appendix E for proof):
Lemma Let E, [.] be the expectation conditional on hy Let E K. be a functinn of contexts, actions and rewards up time t. Under Assumption A, we have:
Vt N., F. ( ( = max max (V(2)))))))
aEA
SES
For all (0, 1}, with probability at least 1 5, we have:
T
Σ
max V ([((=11)
max
(V]( & L.Dxv 2T aEA
(5)
8E8
Lemma 1 shows that FW for CBCR operates closely to a sequence of decision problems of the form (max.e.4 (V](= (x))aaa)))TT However, we have yet to address the problem that P and μ unknown. To solve this issue, we introduce reduction to scalar-reward contextual bandits. We can notice that solving for the sequence of actions maximizing Σí= (V (()))a) corresponds to solving a contextual bandit problem with adversarial contexts and stochastic rewards. Formally, using Ze = 82², we define the extended context 7, = (V xx), the average scalar reward (ā f(
and the observed scalar reward Fg = (V (6;-1) rt). This fully defines contextual bandit problem with scalar reward. Then, the objective of the algorithm is to minimize the following scalar regret:
T
T
T Σ (V (6)
Lsscal
Σ max ( aEA
F Σ
max m ( aEA
1=1
In this framework, the only information observed by the learning algorithm he = (āe, ag, Fe) (e( This regret minimization problem has been extensively studied (see e.g.. Slivkins, 2019, Chap. 8 for overview). The following key reduction result relates Recal to Rr, the regret of the original CBCR problem:
'For simplicity, we presented our reduction with 2; & other choices of 2, are possible (see Appendix D). The important point is that the reduction works without restricting z to S.
'n practice, this result is used in conjunction with an upper bound Rtsa (T. 8') on Re that holds with probability > - 8', which gives Ry S R (T.8')/T (W/n((18)/T with probability at least - 8--6 5' using the union bound.
4

---

Published as a conference paper at ICLR 2023
Theorem Under Assmpt. for every T E N. and 6 0, algorithm 2 satisfies, with prob. 2 1 6: = -== ((8))
Rep LDxv 2T 2n (0) (n(ee)
T
The reduction shown in Thm. hints us at how use or adapt scalar bandit algorithms for CBCR. In particular, any algorithm with sublinear regret will lead to vanishing regret for CBCR. Since the worst-case regret of contextual bandits is 52( (V) (Dani et al., 2008), we obtain near minimax optimal algorithms for CBCR. We illustrate this with two algorithms derived from our reduction in Sec. 3.2.
Proof sketch of Theorem 2: CBCR and Frank- Wolfe algorithms (fill proof in Appendix E). Although the set S is not known, the standard telescoping sum argument for the analysis of Frank- Wolfe algorithms (see Lemma 14 in Appendix E, and e.g. (Berthet Perchet, 2017, Lemma 12) for similar derivations) gives that under Assumption B, denoting = Vf($;-1):
T
TRT
m Is rz) + CCIn(eT).
SES
The result is true for every sequence (rt)ee(T) E K.T and only tracks the trajectory of à, in reward space. We introduce now the reference of the scalar regret:
T
TRT
( eEB
(s) aed
((xx)aa) + max [((x)aa r() +CIn(eTT) (8)
Regol
Lemma 1 bounds the leftmost term, from which Theorem 2 immediately follows using (8).
3.2 PRACTICAL APPLICATION: TWO ALGORITHMS FOR MULTI-ARMED CBCR
To illustrate the effectiveness of the reduction from CBCR to scalar-reward bandits, we focus on the case where the action space A is the canonical basis of R (as in Example 1). We first study the case of linear rewards. Then, for general reward functions, we introduce the FW-SquareCB algorithm, the first example of FW-based approach combined with an exploration principle other than optimism. This shows our approach has a much broader applicability to solve (C)BCR than previous strategies.
From LinUCB to FW-LinUCB (details in Appendix G). We consider CBCR with linear reward function, i.e., ((xx) Ox where Rxx (recall we have D rewards) and E R where the number of features. Let == flatten(0) and gt = (((=-)).. Using [+: to denote the vertical concatenation of matrices, the expected reward for action in context at time t can be written (g: u(z)a) = 9. Oxa = (0 ž,a) where ã, Dax is the extended context with entries ã. = [ : 9t. E R Dáxk This is an instance of a linear bandit problem, where at each time t, action a is associated to the vector āea and its expected reward is (Ø Tza). As a result, we can immediately derive a LinUCB-basee algorithm for linear CBCR by leveraging the equivalence FW-LinUCB(h,, zr. 8') = LinUCB (he, 3t, 5'). LinUCB's regret guarantees imply pecal (dvTT) with high probability, which, in turn give a O(1/VT) for Rr..
From SquareCB to FW-SquareCB (details in Appendix H). We now consider a CBCR with general reward function μ(x)). The SquareCB algorithm (Foster Rakhlin, 2020) is randomized exploration strategy that delegates the learning of rewards to arbitrary online regression algorithm. The scalar regret of SquareCB is bounded depending on the regret of the base regression algorithm.
For PW-SquareCB,, we have access to an online regression oracle jic, an estimate of μ which is function of hr which has regression regret bounded by Rovacle()) The exploration strategy of FW- SquareCB follows the same principles as SquareCB: let 9t = V f((-.) and denote ú = gl (x(x)). so that a
(gel (x)))))). Let 24, FW-SquareCB(lu,, Fe, 8') defined as
if a + a
K+ A: -Ja) Σ DoEA& (a)
Va E (a))
where a, E aargnax jo and i = -2,0
if a,
aeA
afa,
Then FW-SquareCBB has Ry in ( Roracte (T/VT) with high probability.
5

---

Published as a conference paper at ICLR 2023
Table 1: Regret bounds depending on assumptions and base algorithm 2, for multi-armed bandits with K arms (in dimension d for LinUCB). See Appendix G and H for the full details.
Algorithm (FW-<bandit>)
Assumptions (informal)
Bound on Rt (simplified, using d' =
LDDdD In ((1 TLDx 1/6) )
FW-LinUCB
((x) = Oza for E Ixd E R
VT
L K (Homrrt (T) ) DR In(T/o))
FW-SquareCB
[i((z)) - mu(x)aall Roracto(T)
VT
3.3
THE CASE OF NONSMOOTH f
When / nonsmooth, we use a smoothing technique where the scalar regret not measured using Vf( but rather using gradients of sequence (ft)IEN of smooth approximations of f. whose smoothness decrease over time (see c.g., Lan, 2013, for applications smoothing to FW). We provide comprehensive treatment of smoothing in general approach described in Appendix D, while specific smoothing techniques are discussed in Appendix F.
We now describe the of Moreau- Yosida regularization (Rockafellar & Wets, 2009, Def. 1.22):
fe(z) = maXyERD (f(v)
vt+1 28c ly - 2 =13) It is well-known that ft is concave and L-Lipschitz
y++T % -smooth (see Lemma 15 in Appendix F). A related smoothing method was used by Agrawal Devanur (2014) for (non-contextual) BCR. Our treatment of smoothing is more systematic than theirs, since we use smoothing factor Ba/ 8t/Vt- + 1 that decreases over time rather than a fixed smoothing factor that depends on a pre-specified horizon. Our regret bound for CBCR is based on scalar regret Re
whenever f is, and fo is
pecal.s where f 1)
is used instead of V ($t-1))
Recalsa
Σ max aEA
max ( p(z))))
Σ (V
(9)
Theorem Under Assumptions A, for every 2n E K. every T 2 and every ō > 0, > 0,
Algorithm 2 satisfies, with probability at least 8 8':
R
sm
LDk VT
Dx
L
+ 2 )
Rr
+ 3
(10)
T
LBo
Dx
The proof given in Appendix F. Taking B0
Dx leads simpler bound where Dr
+3
Lbn
4.
7,50
1xx
CONTEXTUAL RANKING BANDITS WITH FAIRNESS OF EXPOSURE
In this section, apply our reduction to the combinatorial bandit task of fair ranking, and obtain the first algorithm with regret guarantees in the contextual setting. This task is described in Example (Sec. 2). We remind that there is fixed are flattened permutation matrices (AA is defined in Ex. 2, Eq. (1)). The context ~ P is matrix s, [s]])))[[m] where each It,; E Rd represents a feature vector of item for the current user.
of m items rank at each timestep t, and that actions
Observation model. The user utility u(x;) is given by position-based model with position weights b(xz)) E 0, 11 and expected value for each item v(æ,) E [0, 1 Denoting u(x;) the flattened version of (2))) Rmxm the user utility is (Lagrée al., 2016; Singh & Joachims, 2018):
(u(xx)) a)
Σ Us (ITe) Σ (a
In this model, by (xx) E [0, 1] is the probability that the user observes the item at rank k. The quantity Em bi (xre) is thus the probability that the user observes item i given ranking We denote

---

Published as a conference paper at ICLR 2023
Algorithm 1: FW-LinUCBRand linear contextual bandits for fair ranking.
input:8' 0, 0, 80 K Vo
Ala yo Od, 0 Oad
for t= 1,.., do
Observe context It
Fiie Vi, 02,5 - Ti, + arl 11,,
// UCB on (x())) (def. of o in Lem. 26, App. I) 85 (8t- 01, + 05 (8--)))=_
I/ FW linear optimization step Observe exposed items @t E (0, 1)mm and user feedback a E {0, 1)m Update 8; + + 81-1)
ar top-Ti Dzm+i
m
V/2 - V + Σ
e Y1 x- 91-1 +
c and 0, +- Vi yt
regression
end
T = x S the maximum rank that can be exposed to any user. In most practical applications, & m. As formalized in Assumption D below, the position weights by (ar) are always non-increasing with k since the user browses the recommended items in order of their rank. We use linear assumption for item values, where Dx and Da are known constants:
Assumption C sup |all2 S Dx and 30 Rd |01|2 Do s.t. Vo Ni [m],u:(x) aT.. sE
We propose an observation model where values (x) and position weights b(x) are unknown. However, we assume that at each time step t, after computing the ranking a,, we have two types of feedback: first, et, E {0,1) is if item has been exposed to the user, and 0 otherwise. Second C,, E {0, }} which represents a binary kieedia a ikk feedback from the user. We have
= { (i(e)))
if Te, =1 if et, =0
Elet,/ a.
o (xxe
E(c,,lae,
ea.ll ex.l
(11)
1=1
This observation model captures well applications such as newsfeed ranking mobile devices or dating applications where only one post/profile is shown at a time. What we gain with this model is that b(x:) depend arbitrarily the context x. while previous work bandits in the position-based model assumes b known and context-independeer (Lagrée et al., 2016).?
Fairness of exposure. There are D = m 1 rewards, i.e., p(x) 1)x+m)xm² Denoting i4 (x) the ith-row of u(x), seen as a column vector, each of the m first rewards is the exposure of specific item, while the vn + 1-th reward is the user utility:
Vi E [m]] (1)()))))=
Σ (a)
and
1m+t( u(x))
(12)
The observed reward vector E IRD is defined by Vi E [m], Te.i = et,i and Te,m+1 = D Cr.. Notice that E[rr.m+1 [zz] = u(Iz). Let K. be the convex hull of E [0,1) E S k and 2m+1 S >i 21). we have DR S V R + 1 and T E K. with probability 1. The objective function f IR" R makes a trade-off between average user utility and inequalities in item exposure (we gave an example in Eq. (2)). The remaining assump- tions of our framework are that the objective function is non-decreasing with respect to average user utility. This is not required but is natural (see Example 2) and slightly simplifies the algorithm.
Assumption D The assumptions of the framework described above hold, as well as Assumption Moreover, Vz K. 8f 81(2) 0, and Vx E X, 2 by (x) 2 ... bx(x)) =...= bm (x) 0.
Dzmil
Algorithm and results. We present the algorithm in the setting of linear contextual bandits, using LinUCB (Abbasi- Yadkori et al., 2011: Li et al., 2010) as scalar exploration/exploiaaiio algorithm in
'When b is unknown, depends on the context æ, and we do not observe et. several approaches have been proposed to estimate the position weights (see e.g., Fang al., 2019). Incorporating these approaches in contextual bandits for ranking is likely feasible but out of the scope of this work.
7

---

Published as a conference paper at ICLR 2023
D-5, K-50
D-20, K=50
1.4
0.8-
Obyective
0.275
2.2
thigher
0.250
1.0
0.225
BWnLinnC FairLarm
0.200
10P
10A
10
109
10P
10a
100
10a
10
10*
MOLInCB
rounds
FW-LinUEB 1.0)
rounds
FR-LiniCahank
rounds
LinuCBRakk
0.0
Rerm inequality
0.2
0.4
0.6
(c- 0.01]
SquarcCB (y6- 1000)
Fairieam
Unbias-LiniCRRari
(Gini index, lower is betteri
Figure 1: (left) Multi-armed CBCR: Objective values on environments from (Mehrotra et al., 2020). (middle) Ranking CBCR: Fairness objective value over timesteps on Last.fm data. (right) Ranking CBCR: Trade-off between user utility and item inequality after 5 x 10t iterations on Last.fm data.
Algorithm 1. It builds reward estimates based on Ridge regression with regularization parameter A. As in the previous section, we focus on the case where f is smooth but the extension nonsmooth is straightforward, as described in Section 3. Appendix provides the analysis for the general case.
As noted by Do et al. (2021). Frank-Wole algorithms are particularly suited for fair ranking in the position-basel model. This illustrated by line 4 of Alg. I, where for E R", top-k(ū) outputs permutation (matrix) of [[m]] that sorts the top-k elements of û. Alg. is thus computationally fast, with a cost dominated by the top-I sort. It also has an intuitive interpretation giving items an adaptive bonus depending on V (e.g., boosting the scores of items which received low exposure in previous steps). The following result consequence (Do al., 2021, Theorem 1):
Proposition 4 Let & N. and iú such that Vi [m]] (r. = pa(e))) and jt,m++ ) viewed as a column vector, with i defined in line 3 of Algorithm 1. Then, under Assumption D, ot defined on line 4 of Algorithm satisfies: (V)()) praa) argiaxx ((;;;))) (aa)..
aeA
The proposition says that even though computing a as in line 4 of Alg. 1 does not require the knowledge of b(xz), we still obtain the optimal update direction according to jıx Together with the usage of the observed reward in FW iterates (instead of e.g. ,r as would be done by Agrawal & Devanur (2014)), this removes the need for explicit estimates of u(zz). This is how our algorithm works without knowing the position weights b(xz), which are then allowed to depend on the context.
The usage of é, to compute a follows the usual confidence-based approach to explore/cxploitation principles for linear bandits, which leads to the following result (proven in Appendix I):
Theorem Under Assumptions B, and D. for every 8' > O, every T E No, every 2 D3ck, with probability at least - 8', Algorithm 1 has scalar regret bounded by
Pe o LV [LVTKy
dln(T/8') (WTKkdll(TT8))) ( (Vdln(T/85 + DOVA+ vk/d)
(13)
Thus, considering only d, T, Te and 8 = 8' Alg. has regret Rr S 0
de (ull(T/))
w.p. least 1-6 8.
vT
EXPERIMENTS
We present two experimental evaluations of our approach, which are fully detailed in App. B.
5.1 MULTI-ARMED CBCR: APPLICATION TO MULTI-OBJECTIVE BANDITS
We first focus the multi-objeccive recommendation task of Example 1 where f(:) EP_ wxa..
Algorithms. We evaluate our two instantiations presented in Sec. 3.2 with the Moreau- Yosida smoothing technique of Sec. 3.3: (i) FW- SquareuB with Ridge regression and (ii) FW-LinUCB, where exploration is controlled by a scaling variable e on the exploration bonus of each arm. We compare them to MOL MOLinCB from (Mehrotra al., 2020).
8

---

Published as a conference paper at ICLR 2023
Environments.
We reproduce the synthetie environments of Mehrotra et al. (2020), where the context and reward parameters are generated randomly, and wi; = -- We set K = 50 and E {5, 20} (we also vary K in App. B). Each simulation is repeated with 100 random seeds.
Results. Following (Mehrotra et al., 2020), we evaluate the algorithms'' performance by measuring the value of ( E'=1 (((z)))) over time. Our results are shown in Figure (left). We observe that our algorithm FW- WW-SquareCB obtains comparable performance with the baseline MOLinCB. These algorithms converge after= z 100 rounds. In this environment from (Mehrotra et al.. 2020), only little exploration is needed, hence FW-LinUCB obtains better performance when 6 is smaller (e 0.01). The advantage of using an FW instantiation for the multi-objective bandit optimization task is that unlike MOLinCB, its convergence also supported by our theoretical regret guarantees.
5.2 RANKING CBCR: APPLICATION TO FAIRNESS OF EXPOSURE IN RANKINGS
We now tackle the ranking problem of Section 4. We show how FW-LinUCBRank allows fairly distribute exposure among items on a music recommendation task with bandit user feedback.
Environment.
Following (Patro al., 2020), we the Last.fm music dataset from (Cantador et al., 1), from which we extract the top 50 users and items with the most listening counts. We use a protocol similar to Li et al. (2016) to generate context and rewards from those. We use k = 10 ranking slots, and exposure weights (x) = I+ log) Simulations are repeated with 10 seeds.
1og(2)
Algorithms. Our algorithm is FW-LinUCBRank with the nonsmooth objective f of Eq. (2), which trades off between user utility and item inequality. We study other fairness objectives in App. B. Our first baseline is LinUCBRank (Ermis et al., 2020), designed for ranking without fairness. Then, we study two baselines with amortized fairness of exposure criteria. Mansoury et al. (2021) proposed a fairness module for UCB-based ranking algorithms, which we plug into LinUCBRank. We refer to this baseline as Unbiased-L Ltt.edd-iiUURBRRnnnn Finally, the Fairlearn(( (c, ax) algorithm (Patil et al., 2020) enforces as fairness constraint that the pulling frequency of each arm be 2 up to tolerance a. We implement as third baseline simple adaptation of FairLearn to contextual bandits and ranking.
Dynamics. Figure 1 (middle) represents the values of f over time achieved by the competing algorithms, for fixed 3 1. As expected, compared to the fairness-aware and -unaware baselines, our algorithm LW--inn reaches the best values of f. Interestingly, Unbiased-Lint Lintseddd-LLnUUBBanttt also obtains high values of f on the first 10* rounds, but its performance starts decreasing after more iterations. This is because Sabbiased-LLinnCCH trade-off between user fairness and item inequality.
is not guaranteed to converge optimal
At convergence. We analyse the trade-offs achieved after 5. 10 rounds between user utility and item inequality measured by the Gini index. We vary 3 in the objective f of Eq. (2) for FW-LinUCBRank and the strength e in FairLearn(c, ai), with tolerance a In Fig. (right), we observe that compared to FairLearn, FW-LinUCBRank converges to much higher user utility at all levels of inequality among items. In particular, it achieves cero-unfaimness at little cost for user utility.
CONCLUSION
We presented the first general approach to contextual bandits with concave rewards. To illustrate the usefulness of the approach, we show that our results extend randomized exploration with generic online regression oracles the concave rewards setting, and extend existing ranking bandit algorithms to fairnes-- aware objective functions. The strength of our reduction is that it can produce algorithms for CBCR from any contextual bandit algorithm, including recent extensions of SquareCB to infinite compact action spaces (Zhu& & Mineiro, 2022; Zhu et al., 2022) and future ones.
In our main application to fair ranking, the designer sets a fairness trade-off f to optimize. In practice, they may choose f among a small class by varying hyperparameters (e.g. /8 in Eq. (2)). An interesting open problem is the integration of recent elicitation methods for (e.g.. Lin et al., 2022) in the bandit setting. Another interesting issue is the generalization of our framework to include constraints (Agrawal & Devanur, 2016). Finally, we note that the deployment of our algorithms requires to carefully design the whole machine learning setup, including the specification of reward functions (Stray et al., 2021). the design of online experiments (Bird et al., 2016), while taking feedback loops into account (Bottou et al., 2013; 3; Jiang al., 2019; Dean & Morgenstern, 2022).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors would like thank Clément Vignac, Mare Jourdan, Yaron Lipman, Levent Sagun and the anonymous reviewers for their helpful comments.
REFERENCES
Yasin Abbasi-
Abbasi-Yadkori, Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Himan Abdollahpouri, Gediminas Adomavicius, Robin Burke, Ido Guy. Dietmar Jannach, Toshihiro Kamishima, Jan Krasnodebski, and Luiz Pizzato. Beyond personalization: Research directions in multistakcholder recommendation. arXiv preprint
2019.
Alekh Agarwal, Dean Foster, Daniel Hsu, Sham Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. Advances in Neural Information Processing Systems, 24, 2011.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pp. 989-1006, 2014.
Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and extension concave objectives. In Conference on Learning Theory, pp. 4-18. PMLR, 2016.
Quentin Berthet and Vianney Perchet. Fast rates for bandit optimization with upper-confidence frank-wolfe. Advances in Neural Information Processing Systems, 30, 2017.
Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Li Wei, Yi Wu, Lukasz Heldt, Zhe Zhao, Lichan Hong, Ed Chi, et al. Fairness in recommendation ranking through pairwise comparisons. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2212-220, 2019.
Asia Biega, Krishna P Gummadi, and Gerhard Weikum. Equity of attention: Amortizing individual fairness rankings. In The 41st international acm sigir conference on research & development in information retrieval, pp. 405-414, 2018.
Sarah Bird, Solon Barocas, Kate Crawford, Fernando Diaz, and Hanna Wallach. Exploring or exploiting? social and ethical implications of autonomous experimentation in ai. In Workshop Fairness, Accountability, and Transparency in Machine Learning, 2016.
Léon Bottou, Jonas Peters, Joaquin Quinonero-Cannnn Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14 (11), 2013.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint
2012.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Optimizing the generalized gini index. In International Conference on Machine Learning, pp. 625-634. PMLR, 2017.
Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik. 2nd workshop information heterogeneity and fusion in recommender systems (hetree 2011). I). In Proceedings of the 5th ACM conference on Recommender systems, RecSys 2011, New York, NY, USA, 2011. ACM.
10

---

Published as a conference paper at ICLR 2023
L Elisa Celis, Sayash Kapoor, Farnood Salehi, and Nisheeth K. Vishnoi. An algorithmic framework to control bias in bandit-based personalization. arXiv preprint arXiv: 2018.
Nicolo
and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System 2012.
Sciences, 78(5):
Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pp. 181-190. PMIR, 2020.
Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 32, 2019.
Kenneth L Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Transactions on Algorithms (TALG), 6(4):133,, 2010.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Sarah Dean and Jamie Morgenstern. Preference dynamics under personalized recommendations. arXiv preprint arXiv:2205. 13026, 2022.
Fernando Diaz, Bhaskar Mitra, Michael D Ekstrand, Asia J Biega, and Ben Carterette. Evaluating stochastic rankings with expected exposure. In Proceedings of the 29th ACM international conference on information & knowledge management, pp. 275-284, 2020.
Virginie Do and Nicolas Usunier. Optimizing generalized gini indices for fairness in rankings. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, pp. 737-747, 2022.
Virginie Do, Sam Corbett-Davies. Jamal Atif, and Nicolas Usunier. Two-sided fairness in rankings via lorenz dominance. Advances in Neural Information Processing Systems, 34, 2021.
Madalina M Drugan and Ann Nowe. Designing multi-objective multi-armed bandits algorithms: A study. In The 2013 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2013.
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 2242):674-701, 2012.
Beyza Ermis, Patrick Ernst, Yannik Stein, and Giovanni Zappella. Learning to rank in the position based model with bandit feedback. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 2405-2412, 2020.
Zhichong Fang, Aman Agarwal, and Thorsten Joachims. Intervention harvesting for context- dependent examination-bias estimation. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 825 834, 2019.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cx/0408007, 2004.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Leurning, pp. 3199-3210. PMLR, 2020.
Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks linear contextual bandits. Advances in Neural Information Processing Systems, 33: 33:14332-14377 2020.
Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Olivier Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint. arXiv preprint arXiv:2106.03778 2021.

---

Published as a conference paper at ICLR 2023
Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi. Fairesss- aware ranking in search & recommendation systems with application to linkedin talent search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pp- 2221-2231, 2019.
Thomas P Hayes. A large-deviation inequality for vector-valued martingales. Combinatorics,
Probability and Computing, 2005.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):1573355, 2016.
Martin Jaggi. Revisiting foafe-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pp. 427-435. PMLR, 2013.
Olivier Jeunen and Bart Goethals. Top-k contextual bandits with equity of exposure. In Fifteenth ACM Conference on Recommender Systems, pp. 310-320, 2021.
Ray Jiang, Silvia Chiappa, Tor Lattimore, András György, and Pushmeet Kohli. Degenerate feedback loops in recommender systems. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 383 383-390, 2019.
Thomas Kerdreux, Fabian Pedregosa, and Alexandre d' Aspremont. Frank-wolfe with subsampling oracle. In International Conference on Machine Learning, pp. 2591-2600. PMLR, 2018.
Till Kletti, Jean-Michel Renders, and Patrick Loiseau. Introducing the expohedron for efficient pareto-optimal fairness-utility amortizations in repeated rankings. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 498-507, 2022.. 2022.
Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International conference on machine learning, pp. 767-776. PMLR, 2015.
Simon Lacoste-Julee Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate frank- wolfe optimization for structural svms. In International Conference on Machine Learning, 2013.
Paul Lagrée, Claire Vernade, and Olivier Cappe. Multiple-play bandits the position- model. Advances in Neural Information Processing Systems, 29, 2016.
Guanghui Lan. The complexity of large-scale convex programming under linear optimization oracle. arXiv preprint arXiv: 309.5550, 2013.
John Langford and Tong Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 1799-1811,, 2011.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pp. 1245-1253. PMLR, 2016.
Zhiyuan Jerry Lin, Raul Astudillo, Peter Frazier, and Eytan Bakshy. Preference exploration for
efficient bayesian optimization with multiple outcomes. In International Conference Artificial Intelligence and Statistics, pp. 4235-4258. PMLR, 2022.
Debmalya Mandal and Jiarui Gan. Socially fair reinforcement learning.
arXiv preprint
arXiv:2208.11 12584, 2022.
Masoud Mansoury, Himan Abdollahpouri, Bamshad Mobasher, Mykola Pechenizkiy, Robin Burke, and Milad Sabouri. Unbiased cascade bandits: Mitigating exposure bias online learning to rank recommendation. arXiv preprint a0Xiv:2108.0:20 2021.
12

---

Published as a conference paper at ICLR 2023
Rishabh Mehrotra, James McInerney, Hugues Bouchard, Mounia Lalmas, and Fernando Diaz. Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems. In Proceedings of the 27th acm international conference on information and knowledge management, pp. 2243-2251, 2018.
Rishabh Mehrotra, Niannan Xue, and Mounia Lalmas. Bandit based optimization of multiple objectives music streaming platform. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3224-3233, 2020.
Kaisa Miettinen. Nonlinear multiobjective optimization, volume 12. Springer Science & Business Media, 2012.
Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. Controlling fairness and bias in dynamic learning-to-rank. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 429 438, 2020.
Hervé Moulin. Fair division and collective welfare. MIT press, 2003.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566 2017.
Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari. Achieving fairness the stochastic multi-armed bandit problem. In AAAI, pp. 5379-5386, 2020.
Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P Gummadi, and Abhijnan Chakraborty. Fair- rec: Two-sided fairness for personalized recommendations in two-sided platforms. In Proceedings of The Web Conference 2020, pp- 1194-11 1204, 2020.
Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg. Fair ranking: a critical review, challenges, and future directions. arXiv preprint arXiv:2201. 12662, 2022.
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pp. 461-469. SIAM, 2014.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194 2012.
Umer Siddique, Paul Weng, and Matthieu Zimmer. Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pp. 8905-8915, PMLR, 2020.
Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 2219-2228. ACM, 2018.
Ashudeep Singh and Thorsten Joachims. Policy learning for faimess in ranking. Advances in Neural Information Processing Systems, 32, 2019.
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv:1904.07272. 2019.
Jonathan Stray, Ivan Vendrov, Jeremy Nixon, Steven Adler, and Dylan Hadfield-Menell. What you optimizing for? aligning recommender systems with human values. arXiv preprint arXiv:2107.10933) 2021.
Kiran K Thekumparampil, Prateek Jain, Pranceth Netrapalli, and Sewoong Oh. Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. Advances in Neural Information Processing Systems, 33:12211-1222 2020.
Nicolas Usunier, Virginie Do, and Elvis Dohmatob. Fast online ranking with fairness of exposure. In 2022 ACM Conference Fairness, Accountability, and Transparency, pp. 2157-2167, 2022.
13

---

Published as a conference paper at ICLR 2023
Peter Vamplew, Richard Dazeley, Cameron Foale, Sally Firmin, and Jane Mummery, Human-aligna artificial intelligence is a multiobjecttiv problem. Ethics and Information Technology, 20(1):27 40, 2018.
Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure in stochastic bandits. In International Conference on Machine Learning, pp. 10686-10696. PMLR, 2021.
Haolun Wu, Bhaskar Mitra, Chen Ma, Fernando Diaz, and Xue Liu. Joint multisided exposure fairness for recommendation, arXiv preprint arXiv:2205.0000 000488, 2022.
Huanle Xu, Yang Liu, Wing Cheong Lau, and Rui Li. Combinatorial multi-armed bandits with
concave rewards and faimess constraints. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2554 2554-2560, 2021.
Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In Proceedings of the 29th international conference on scientific and statistical database management, pp. 1-6, 2017.
Nicholas Yannelis. Integration of Banach- Valued Correspondence, pp. 2-35. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. ISBN 978-3-666--07771-0,
Farzad Yousefian, Angelia Nedié, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56 2012.
Alp Yurtsever, Olivier Fercoq, Francesco Locatello, and Volkan Cevher. A conditional gradient framework for composite convex minimization with applications to semidefinite programming. In International Conference on Machine Learning, pp. 5727-5736. PMLR, 2018.
Meike Zehlike and Carlos Castillo. Reducing disparate exposure in ranking: A learning to rank approach. In Proceedings of The Web Conference 2020, pp. 2849-2855, 2020.
Meike Zehlike, Ke Yang. and Julia Stoyanovich. Fairness in ranking: A survey. arXiv preprint arXiv:2/03. 14000, 2021.
Yinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning in continu- ous action spaces. In International Conference on Machine Learning, pp. 27574-27590, PMLR, 2022.
Yinglun Zhu, Dylan Foster, John Langford, and Paul Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Muchine Learning, pp. 27428-27453. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2023
CONTENTS
A Related work
15
More on experiments
16
B.1 Ranking CBCR: Application to faireess of exposure in rankings with bandit feedback
16
B.2 Multi-armed CBCR: Application to multi-objective bandits with generalized Gini function
20
C Proof' of Section 2
21
C.I Brief reminder on Lipschitz functions and super-gradients
C.2 Preliminaries: the structure of the set S
21
C,3 Proof of Lemma
23
D The general template Frank- algorithm
24
Proof's for Section and Appendix D
27
E.1 proofs of the main results
29
F Smooth approximations of non-smooth functions
29
F.I Smoothing with the Moreau envelope
30
F.2 Randomized smoothing.
30
G FW-LinUCB: upper-confidence bounds for linear bandits with K arms
31
H FW-SquareCB: CBCR with general reward fuctions
33
H.1 Adaptation of SquareCB proof to CBCR
35
H.2 Final result
37
I FW-LinUCBRank: CBCR for fair ranking with linear contextual bandits
37
L1 Results for online linear regression (from (Li et al., 2016))
38
I.2 Guarantees for FW-LinUCB
38
J Additional technical lemmas
41
J.1 Proof of Lemma (S is compact)
J.2 Proof of Lemma 24
41
A RELATED WORK
The non-contextual setting of bandits with concave rewards (BCR) has been previously studied by Agrawal & Devanur (2014), and by Busa-Fekete et al. (2017) for the special case of Generalized Gini indices. In BCR, policies are distributions over actions. These approaches perform a direct optimization in policy space, which not possible in the contextual setup without restrictions or assumptions optimal policies. Agrawal et al. (2016) study setting of CBCR where the goal is to find the best policy in a finite set of policies. Because they rely on explicit search in the policy space, they do not resolve the main challenge of the general CBCR setting address here. Cheung
15

---

Published as a conference paper at ICLR 2023
(2019); Siddique et al. (2020); Mandal & Gan (2022); Geist et al. (2021) address multi multi-objective reinforcement learning with concave aggregation functions, a problem more general than stochastic contextual bandits. In particular, Cheung (2019) use FW approach for this problem. However, these works rely on a tabular setting (i.e., finite state and action sets) and explicitly compute policies, which is not possible in our setting where policies distributions over actions. Our work is the only one amenable to contextual bandits with concave rewards by removing the need for an explicit policy representation. Finally, compared to previous FW approaches to bandits with concave rewards, e.g. (Agrawal & Devanur, 2014; Berthet & Perchet, 2017), our analysis is not limited to confidence-bias based exploration/explottaionn algorithms.
mappings from a continuous context set to
CBCR is also related to the broad literature on bandit convex optimization (BCO) (Flaxman et al., 2004; Agarwal et al., 2011; I; Hazan et al., 2016; Shalev-Shwartz et al., 2012). BCO, the goal is to minimize a cumulative loss of the form Σiz (TT,), where the convex loss function & is unknown and the learner only observes the value (T()) of the chosen parameter Te each timestep. Existing approaches to BCO perform gradient- free optimization in the parameter space. While BCR considers global objectives rather than eumulative ones, similar approaches have been used in non-contextual BCR (Berthet & Perchet, 2017) where the parameter space is the convex set of distributions over actions. As we previously highlighted, such parameterization does not apply to CBCR because direct optimization in policy space is infeasible.
CBCR is also related to multi-objective optimization (Miettinen, 2012; Drugan & Nowe, 2013), where the goal is to find all Pareto efficient solutions. (C)BCR, focuses on one point of the Pareto front determined by the concave aggregation function f. which is more practical in our application settings where the decision
is interested in specific (e.g., fairness) trade-off.
In recent years, the question of fairness of exposure attracted a lot of attention, and has been mostly
studied in static ranking setting (Geyik et al., 2019; Beutel et al., 2019; Yang & Stoyanovich, 2017; Singh & Joachims, 2018; Patro et al., 2022; Zehlike et al., 2021; Kletti et al., 2022: Diaz et al., 2020; Do & Usunier, 2022; Wu et al., 2022). Existing work on fairness of exposure in bandits focused on local exposure constraints on the probability of pulling an arm at each timestep, either in the form of lower/upper bounds (Celis et al., 2018) merit-based exposure targets (Wang et al., 2021). In contrast, we consider amortized exposure over time, in line with prior work on fair ranking (Biega al., 2018; Morik al., 2020; Usunier et al., 2022), along with faimess trade-offs defined by concave objective functions which are more flexible than fairness constraints (Zehlike & Castillo, 2020; Do al., 2021: Usunier et al., 2022). Moreover, these works (Celis al., 2018; Wang et al., 2021) do not address combinatorial actions, while ours applies to ranking in the position-based model, which more practical for recommender systems (Lagrée al., 2016; Singh & Joachims, 2018). The methods of (Patil et al., 2020; Chen et al., 2020) aim at guaranteeing a minimal cumulative exposure over time for each arm, but they also do not apply to ranking. In contrast, (Xu et al., 2021: Li et al., 2019) consider combinatorial bandits with fairness, but they do not address the contextual case, which limits their practical application to recommender systems. (Mansoury et al., 2021; Jeunen Goethals, 2021) propose heuristic algorithms for faimesss in ranking in the contextual bandit setting, highlighting the problem's 's importance for real-world recommender systems, but they lack theoretical guarantees. Using FW reduction with techniques from contextual combinatorial bandits (Lagrée et al., 2016; Li et al., 2016; Qin et al., 2014), we obtain the first principled bandit algorithms for this problem with provably vanishing regret.
B MORE ON EXPERIMENTS
Our experiments are fully implemented in Python 3.9.
B.1 RANKING CBCR: APPLICATION TO FAIRNESS EXPOSURE IN RANKINGS WITH BANDIT FEEDBACK
B. DETAILS OF THE ENVIRONMENT AND ALGORIHTM
Environment Following (Patro et al., 2020) who also address fairness in recommender systems, we use the Last.fm music d from (Cantador al., 2011), which includes the listening counts of
httpps:/ :/w/:////www/ww/..../ last. Fm, the dataset is publicly available for non-commereial use.
16

---

Published as a conference paper at ICLR 2023
0.30
Item dbjecttvv
35
Obyectvve
55
0.77
1ourdds
rounds
Fart.am 10 10-1---- 25)
UTD
0.00
0.20
akjeciee
0.4
0:00
800
intiC Inarst
Tarrearr: L.c.m Eb1
8.50
0.00
0:0
Farm objorttoo
12
Objecttuv 1-2
12
mundd
Ioard)
Farrear L.c. C51
Figure 2: Lastfi-55:: Objective values over time for (top) Gini, (middle) eq. exposure, (bottom) welf.
892 users for the tracks of 17, 632 artists, which we identify the items. For the first environment, which we presented in Section 5 and which we call Lastfin-50 here, we extract the top n 50 users and scale, we also design another environment, Lastfm-2k,, where we keep all n 1.9k users and the top m 2.5k items having the most interactions. In both cases, to generate contexts and rewards, we follow protocol similar to other works on linear contextual bandits (Garcelon et al., 2020; Li et al., 2016). Using low-rank matrix factorization with d' latent factors", we obtain user factors u, E Rd and item factors V E Rd' for all j, E [n]] x [[m] We design the context set as X (flatten(u,u]]
50 items having the most interactions. In order to examine algorithms larger
draws uu) : j i, E [n]] x [m]] C. Rd, where d = d²² At each time step f, the environment uniformly random from [n]] and sends context 2, flatten(u,, uu), Given context 2e and item i, clicks are drawn from a Bernoulli distribution: C, ~ Buu,, [. m.).
We set k: = 10, and for the position weights, we use the standard weights of the discounted cumulative gain (DCG): vk E [R], by [1g,(1+ and be.1....,, bm 0.
Details of the algorithms For all algorithms, the regularization parameter of the Ridge regression set to À = 0.1.
The first baseline consider is the algorithm LinUCBRank of (Ermis et al., 2020), which is a top-k ranking bandit algorithm without fairness. equivalent to using FW-LinUCBRank with f(s) sm+1, which corresponds to the usual top-k ranking objective without item fairness. More precisely, m
each timestep, the algorithm produces a top-l ranking of (0T1 + az (1 2=1
Using the Python library Implicit, MIT License: https: if t. readthedocs i0/ 10 LoniUUUUaan appears under various names in the literature, including PBMLinUCBRank (Frmis et al., 2020) and Cascadel inUCB (Kveton al., 2015).
17

---

Published as a conference paper at ICLR 2023
Objective
0
Item
Fartuam 10 1-...... 251
UTD
0.12
olgestive
013
612
F1 lound
UnD LINL
Figure 3: Lastffn-2k: Objective values over time for (top) Gini, (bottom) welf.
0.125
total user utility
(higher is better)
0.120
0.115
0.1.0
(Gini)
Fairlearn (a = 1)
0.5
1.0
item inequality
(Gini index, lower is better)
Figure 4: Trade-offs between user utility and inequality Lastfmn-kk, after T 106 rounds.
We also consider as baselines two bandit algorithms with amortized fairness of exposure criteria. First, Mansoury al. (2021) proposed fairness module for cascade ranking bandits, which can be easily adapted to the position-based model (PBM). Their goals include reducing inequality in exposure between items, measured by the Gini index of exposures in their experiments. While they measure the exposure of an item as their recommendation frequency over time, we adapt their module to the PBM by using the observation frequency, i.e. Σi- Cv for item at time t. Transposed to our setting, their module consists in a simple modification LinUCBRank by multiplying the exploration bonus of each item i by factor:
E Crς E'= Er Cr.
Me.1
(14)
More precisely, at each timestep, the algorithm produces a top-T ranking of (0 Thi x ar(%) II 1=1 Following (Mansoury et al., 2021), we call this bascline Unbiased- LinbuseeddLUUUBBBnnkk.
Our second baseline with faimeess is the FairLearn(e, a) algorithm of Patil al. (2020) for stochastic bandits with a faimess constraint on the pulling frequency Ne,; of each arm at each timestep t. The constraint is parameterized by variable and tolerance parameter a: [ct] - NN. a. We adapt FairLearn(c, a) to ranking by applying the algorithm sequentially for each recommendation slot, while constraining the algorithm not choose the same item twice for given ranked list. We also
18

---

Published as a conference paper at ICLR 2023
adapt FairLearn to contextual bandits by using LinUCB underlying learning algorithm. More precisely, for the current timestep and slot, if the constraint is not violated, then the algorithm plays the item with the highest LinUCB upper confidence bound.
Objectives To illustrate the flexibility of our approach, we use algorithm FW-LinUCBRank to optimize three existing objectives which trade off between user utility and item fairness, in the form: [(s) 5m+1 + 3 (81m). Gini measures item inequality by the Gini index, as in (Biega et al., 2018; Morik et al., 2020; Do Usunier, 2022), and eq. exposure uses the standard deviation (Do et al., 2021):
(Gini) fllm (s)
Σ
m j+1
(eq. expo) file 1
8j¹
(15)
Since Gini is nonsmooth, we apply the FW-LinUCBRank algorithm for nonsmooth with Moreau- Yosida regularization, presented in Section 3.3 and detailed in Appendix F.1 (we use 3, 1 in our experiments). To compute the gradient of the Moreau envelope ft, we use the algorithm of Do & Usunier (2022) which specifically applics to generalized Gini functions and top-k ranking.
We also study additive concave welfare functions (Do et al., 2021; Moulin, 2003) where is parameter controlling the degree redistribution of exposure to the worse-off items:
(Welf) filem (s)
= =Z Sj a>0
(16)
1=1
B.1.2 ADDITIONAL. RESULTS
We now present additional results, which are obtained by repeating each simulation with 10 different random seeds.
Dynamics For the three objectives described, Figure 2 represents the values of the user and item objectives (left and middle), and the value of the objective f (right) over time, achieved by the competing algorithms on Lastfi-50.. We set 8 = 0.5 for all objectives and for welf. we set a = 0.5. We observe that with this value of B, the item objective fitem is given more importance in f than the user utility.
We observe that for Gini and welf. FW-LinU achieves the highest value of f across timesteps. This is because unlike LinUCBRank, it accounts for the item objective frlmm In both cases, Unbiased- LinUCBRank achieves a high value of f over time but starts decreasing, after 10 iterations for Gini and 5.10 iterations for welf. This is because Unbiased-LinUCBARe converge towards an optimum of f. For eq. exposure, when 3 = 0.5, Unbiased-LimUCCBRe obtains surprisingly better values of f than FW-LinUCBRank. Therefore, depending the objective Litiuseed-LnUUBBRnnn can be chosen as an alternative to FW-
is not designed to
to optimize and the timeframe, LinUCBRank. However, due to its lack of theoretical guarantees, it more difficult to understand in which cases it may work, and for how many iterations. Furthermore, unlike FW-LinUBBRand can be chosen to optimise wide variety of functions by varying the tradcoff parameter 3 in all objectives, and in welf to control the degree of redistribution. Unbiased- LinUCBRank does not have such controllability and flexibility.
Figure 3 shows the objective values for Gini and welf on Lastfi-24 2k. We observe similar results where FW-LanUCBRank converges more quickly than its competitors (* 5, 000 iterations for Gini and R 500 iterations for welf) and obtains the highest values of f. For the first 10 iterations of optimizing Gini, Unbiased-L.nte UnCRRan obtains significantly lower values than FW-L.nUUBRRakk on welf.
Fairness trade-off for fixed T' On the larger Lastfm-2k dataset, we study the tradeoff's between user utility and item inequality obtained by FW-LinUCBRRnk and FairLearn on Figure 4 after T = 1 rounds. The Pareto frontiers obtained as follows: FW-LinUCBRand optimises for Gini, in which we vary 3, and for FairLearn we vary the constraint value at fixed a = 1. Figure I in Section of the main paper illustrated the same Pareto frontier but for 5x more iterations and the smaller
19

---

Published as a conference paper at ICLR 2023
K=200
D-20, K-50
Ke-5
MOLinC8
00jecTiV
1.4
objective
objective
FI-UnnUCB (c-1.0)
0.011)
1.2
FW FW-SquareBB fro 1c3)
FW-SquareCBB (111 1o4)
0.6
10
FIW.EpSGreddy (r 0.01)
0.8
10'
10" roLind
10"
10a
10'
10
10'
10"
10
rounds
munds
Figure Multi-objective bandits: GGF value achieved various synthetic environments.
Lastfm-50 dataset. Although the algorithms might not have converged for this larger dataset, we observe that FW-LinUCBRank obtains better trade-offs than FairLeam, achieving higher user utility at all levels of inequality. We conclude that even in a setting with more items and shorter learning time, FW-LinUCBRRnk effectively reduces item inequality, at lower cost for user utility than the baseline.
B.2 MULTI-ARMED CBCR: APPLICATION TO MULTI-OBIECTIVE BANDITS WITH GENERALIZED GINI FUNCTION
We provide the details and additional simulations on the task of optimizing the Generalized Gini aggregation Function (GGF) in multi-objective bandits (Busa-Fckete et al., 2017: Mchrotra et al., 2020). We remind that the goal is to maximize a GGF of the D-dimensional rewards, which is a nonsmooth concave aggregation function parameterized by nonincreasing weights w사 uD 2 f(s) = El u;ss, where (s]) P denotes the values of sorted in increasing order.
Mehrotra et al. (2020) study the contextual bandit setting, motivated by music recommendation on Spotify with multiple metrics. They consider atomic actions a, E A (i.e., A the canonical basis of k and linear reward model: Vi E [D]. 30, E Rdd. E [rr..] = 0. a. These are the same assumptions as described in Table of Section 3.2 and in Appendix G.
GGFs are concave functions, but they are nondifferentiable. Therefore, FW approach for nonsmooth f (see Section 3.3), where we smooth the objective via Moreau- Moreau-Yosida regularization with parameter 3, 0.01, using the algorithm of (Do & Usunier, 2022) to compute the gradients of the smooth approximations ft.
the variant of our
Algorithms In the main body, evaluated two instantiations of our FW meta-algorithm, namely FW-LinUCB and FW-SquareCB. The level exploration in FW-LinUCB controlled by a variable More precisely, the exploration bonus is multiplied by ve, i.c. the UCBs are calculated as: oT Tr, + V af (6)l In FW-Square-CB, as detailed in Appendix H, the exploration controlled by sequence (74)21, growing as vi (higher " means less exploration). We set it to rov' with E
In addition the algorithms presented in Section 5, show the flexibility our FW approach, we also implement FW-e-greedy, another instantiation of our FW algorithm which uses e-grredy as scalar bandit algorithm.
We compare our algorithms with MOLinCB of Mchrotra et al. (2020), an online gradient descent-style algorithm which was designed for this task, but was introduced without theoretical guarantees, as an extension of the MO-OGDE algorithm of Busa-Fekete et al. (2017) who study the non-contextual problem. We use the default parameters of MOLinCB recommended by Mehrotra et al. (2020).
Environments Since the Spotify dataset of Mehrotra et al. (2020) is not publicly available, we only focus on their simulated, controlled environments. We reproduced these environments exactly as deseribed in Appendix A of their paper. For completeness.
restate the protocol here: we draw hidden parameter 0 E R Dxd uniformly at random in [0, 1], and each element of a context-arm vector Je. drawn from N 2 きz) Given context x; and arm k, the D-dimensional reward is generated
20

---

Published as a conference paper at ICLR 2023
draw from /V 0.01(6x(,k:)) We choose d = 10 in the data generation and À 0.1 in the Ridge regression, as recommended by Mehrotra et al. (2018).
In Section 5 of the main body, varied the number of objectives D {5, 20} and set K 50. Here we also experiment with K 200 to see the effect of varying the number of arms. The GGF weights are W - Each simulation is repeated with 100 different random seeds.
Results The extended results, with more arms and algorithms, are depicted Figure We observe that FW-e-greedy achieves similar performance to the baseline MOLinCB, with small exploration = 0.01. FW-SquareCB also achieves comparable performance to MOLinCB when there little exploration, i.e. with To = 10 rather than 10 This is coherent with observation in Section that FW-LinUCB obtains better performance when there very little exploration on this environment from Mehrotra et al. (2018). Note that there no forced exploration in their algorithm MOLinCB. Overall, we obtain qualitatively similar results when K = 200 compared to K = 50.
C PROOFS OF SECTION 2
In this section we give the missing details of Section 2. For completeness, remind the definitions of Lipschitz-continuity and super-gradients in the next subsection. Then, we start in Section C.2 the analysis of the structure of the set S defined in Section of the main paper, and more precisely its support function g + max,es gTs. This contains new lemmas that are fundamental for the analysis throughout the paper, in particular in the proof of Lemma 9, which is given in Section C.3.
C.1 BRIEF REMINDER ON LIPSCHITZ FUNCTIONS AND SUPER-GRADIENT
We remind the following definitions. Let D and D' be two integers, and f function :RD - RDD
We have:
(Lipschitz continuity) f is L-Lipschitz continuous with respect to ||.1|2 on a set 2 CRPi if
Vz, =' E Z, (=) ((')]l2 < L||= 2'112.
(17)
RR - R U [o a super-gradient of f at a point E RD where f(=) E R is a vector g such that for all s' E RD f(=') f()) (g|=' z).
(super-gradients) If f
We remind the following results when f: D + R U [ is proper closed concave function:
f has non-empty set of super-gradients
every point where f(z) E R.
if f is L-Lipschitz on Z C R and Z is open, then for every 2 Z and every super-gradien g of
f at 2, we have ||gl|2 I L.
The assumption of Lipschitz-continuity of on a set Z implicitly implies the assumption that 2 is in the domain of f-
Remark (About our Lipschitzness assumptions) We use Lipschitzness over an open set contain- ing I. in Assumption because we use boundedness of the super super-gradients of f. In fact, a more precise alternative would be to require that super-g graddengsss are bounded uniformly on K. by L. We choose the Lipschitz.ormuuattie formulation because we believe more natural.
As side note, in assumption B, we use Lipschitzness of the gradients on K., not on an open set containing K. This is because smoothness in used in the ascent lemma (see Eq. 50), which uses Inequality 4.3 of Bottou et al. (2018), the proof of which directly uses Lipschitz-continut of the gradients on (Bottou et al., 2018, Appendix B), without relying on an argument of boundedness of gradients.
C.2 PRELIMINARIES: THE STRUCTURE OF THE SET S
We denote by FI.T = (#1...., .., pT) a sequence of contexts of length T. Let
S E ((nr(((Z))(())
7: A
(18)
Var X. .((1i))
T Σ ((x))T(2)))
(19)
21

---

Published as a conference paper at ICLR 2023
straightforward to show that S(ILT) - p(a+)TTe (,,,..,,TT!! E A
These sets
are particularly relevant because of the following equality, for every f: 1R - + U =
s = sup m:X-A
/ (Berr ((())(((()><<))) = sup f(s) s(s)
(20)
xES
and
f
sup (st)
Σ ((()))))) .ES(F)))
sup
f(s).
(21)
We study in this section the structure of these sets, We provide here the part of Assumption A that is relevant to this section:
Assumption Á A is compact subset Tf a( E X A, p(x)a K.
TR and there is a compact convex set K. C RD such that
We remind the following basic results from convex sets in Euclidian spaces that we use throughout the paper without reference:
Lemma Let A be a compact subset of We have:
(Rockafellar & Wets, 2009, Corollary 2.30) The convex hull A of a, denoted by A, is compact. For every w E RK maxx w = max TTa.
atA
The following lemma allows us use maxima instead of suprema over S and S(x):)). The proof of this lemma deferred to Appendix J.1.
Lemma Under Assumption A, S is compact and VT E N.., VILT E XT, (((1T) is compact.
The next result regarding the support functions of S and ((1)r) is the key to approach:
Lemma 8 Let R and T E N.. Under Assumption A, have
Bryprr
max (EET())))
TTs
max wTs.
(22)
Moreover, for every 8 E (0, 1), we have with probability at least 1 8:
2 2l1 118-11
T max
| |1012Dic
(23)
T
2nn
The inequality max wts max wis D (ES())r)
also holds with probability 8.
sES
T
Proof. The first result is a direct consequence of the maximization of linear functions over the simplex. Using (20) with f(s) = wTs and the linearity of expectations, we have
max TT max Eg-r (tt=r[(T((=<<(00 ((x)=(x)) #ES
(24)
#X-AA
The optimal policy given w, denoted by π is thus obtained by optimizing for every x the dot product between wT (xx)) E BK and (I)) E A R Since, for each it is linear optimization, we can find an optimizer A (see Lemma 6), which gives:
max T s E wt p(x)
where म <(())
argmax wi p(x)a, (25)
SES
aeA
(x))
where in the equation above we mean that " is measurable selection of x argmax T p(z)a.
T
For the same reason, we have max xES(x1T)
T
" (zx). We obtain
T
1
E Exp w
E
ExiTon PT
Td (xx)
EENP [nn)(("((E)] max wT (26)
(ES(Zir)
T
1=1
22

---

Published as a conference paper at ICLR 2023
which is the first equality.
For the broh-brobabilityy inequality, let X, (xx))))))) - Ex~p (x)]. Since the (2t).et) are independent and identically distributed (i.i.d.), the variables (Xt), are also i..d., and have
Xxx S wT (u(x)))T (xt) Bg (x))))((())) S 110l22
and E [x.] 0.
(27)
EK
eK
Given E (0, 1), Hoeffding's inequality applied to + Ei= Xe gives, with probability at least
2 2
max xES(ET)))
w
max #ES
w
T Σ X S 2
(28)
The reverse equation is obtained by applying Hoeffding's inequality to EE X
C.3 PROOF LEMMA
Lemma 9 Under Assumption A, VT E N., Vo E (0, 1], we have, with probability at least 1 8:
ln dea 8 ff - SDDNV
where ft
max (MI..... (T)...
1
Σ u(x))
We also have, with probability
5 over contexts, actions, and rewards:
2In(2228-1)
T Σ
[ - ((ss))f($r))) s LDR V
where ST = T p(xx)ar
T
The first statement shows that the performance of the optimal non-stationary policy over steps converges to f* at rate O(I/VT). Furthermore, measuring the algorithm's performance by expected rewards instead of observed rewards would also amount to a difference of order OLIVVT). This choice would lead what is commonly referred to a pseudo-regret. Since the worst-case regret of BCR is 221/V/ (Bubeck & Cesa- Cesa-Bianchi, 2012), the previous lemma shows that the alternative definitions of regret would not substantially change our results.
Proof. We start with the first inequality.
We first prove that w.p. greater than 1 5/2, we have f S
2h
Since f is continuous K. and since S C K. and S is compact by Lemma there is s" S such that f f(*).. Similarly, since S(F is compact, there is sh. such that f(s)) max,e f(s).
Using (20), we need to prove that with probability at least 1 - 6/2, we have f(st) S f(s") 2
LDx
Using the concavity of f. let g² be supergradient of f s" We have
f(st) & f(s") (g" St s*)
(29)
Σ f(x)) + max (g" | 8*) SES(Z1:7)
(30)
In 3
w.p. 21 2-8/22
f(s)) < f(s") + max (g" Is - 8*) +11g 112x
SES
T
20 by def of
(by Lemma 8)
2 2
3 f((") + LD
(by the Lipschitz assumption)
23

---

Published as a conference paper at ICLR 2023
We now prove f S f + LDxV / 2n with probability at least 8/2.
Let n E wrwgmaxx..-- / [Rap (((n)(((())(()))) (an optimal policy exists by Lemma 7). Denote by (X, = p(xx)= (x))) a sequence independent and identically distributed random variables obtained by sampling Zt P.
We have Xx EXE] & Dr and EX, = s². By the Lipschitz property of f, we obtain
T f(s)) s f( xx)+ x
T +
Σ x t=1
(31)
Using the version of Azuma's inequality for vector-valued martingale with bounded increments of Hayes (2005, Theorem 1.8) to obtain, for every 0:
Σ X1
20 S 2 12
(32)
DE
Setting 2
T22 and solving for gives, with probability at least - 6/2:
T Σ + fr S fl T
In 4ea
ln 4e2
T + LDK
(33)
T
t=1
For the second inequality: using I-LLppchitzness of f. the inequality is a direct consequence of the lemma below, which is itself a direct consequence of (Hayes, 2005, Theorem 1.8).
In the following lemma and its proof, we use the two following filtrations:
Cx), where 3, is the r-algebra generated by ( Pl,..,,..................... " at- (t-1,
(8T) where Jr is the o-algebra generated by (I1 (o.... a1-1; r1-1; Tz, az).
Our setup implies that the process (at),eN, is adapted to 3 while (rt),en, is adapted to 3.
Lemma 10 Under Assumption A, if the actions (aI..... aT) define process adapted to (8r (TT)EM
then, for every T E N. for every with probability
we have:
2 In
20a 8
|| - &T|l2 S Dx1
(34)
T
Dx. and (XT) is martingale adapted to (3r)ren satisfying X, O. We can then use the version of Azuma's inequality for vector-valued martingale with bounded increments of Hayes (2005, Theorem 1.8) to obtain, for every <> 0:
Proof. Let XT = -t- T- p(x))ar We have
XT-1l1 1|2 -
P(]
Xr Dx
20) 2e2e 22
(35)
Solving for gives the desired result.
D THE GENERAL TEMPLATE FRANK-WOLFE ALGORITHM
A more general framework The analysis of the next sections is done within a more general famework than that of the main paper, which described Algorithm Similarly to the main paper, 2(h,, Zz, 5') (Line 3 of Alg. 2). However, we allow for
the action is drawn according to generic choice of Frank- Wolfe iterate with respect to which we compute (an extension of) the scalar regret (presented in (36) below). The update direction is denoted by Pt and is chosen according to a function 11(h+11, 8'), a companion function from h, xt. 8'). Note that the update direction is chosen given h441 (h,, (Ia, 0r, rz)), the history after the actions and rewards have been taken.
24

---

Published as a conference paper at ICLR 2023
Algorithm 2: Generic Frank- Wolfe algorithm for CBCR.
input: initial point 2 E XC, Approx. RLOO confidence parameter
for / 1......o do
Observe 34 P
Observe reward rt E K, update temporal average of observed rewards Explore/exploit step
Pull ar ~ (1, Zt, 8¹)
Let Pt = _((4+1,8')
// Generic Frank-Wolfe update
Update = zt-1 + (p= 2-11)
end
The proofs of the main paper apply to the special case of Alg. where VI 2 1, rt. We then have the FW iterate 2, in Line 6 of the algorithm satisfy Vt 2 1, 2t = 3t.
The reason study this generalization is to show how our analysis applies in cases where the FW iterate is not the observed reward. In prior work on (non-contextual) BCR, Agrawal & Devanur (2014, Algorithm use an upper-confidence approach and use the upper confidence on the expected reward as update direction. The generalization made by introducing 11(h+11, compared to the main paper allows for our analysis to encompass their approach.
We need to update Assumptions A and B to account for the fact that is used in place of rt-
Assumption A' is closed proper concave on RD and A is compact subset of RKK Moreover, there is compact convex set K _ TR. such that
(Bounded rewards and iterates) For all t E N.,, E K. and pt K. with probability 1.
(Local Lipschitzness) f is L-Lipschitz continuous with respect to I1-112 on an open set containing K.
Assumption B' Assumption holds and f has C-Lipschitz- gradients w.r.t Il-I12 on K.
In Assumption we added p(xx, )a, E for clarity, but is not necessary since p(xz)a; probability is implied by Te IC with probability 1. The difference between Assumption A' and Assumption to make sure that the updates Pt. and thus the iterates 2, belong to IC and are in the domain of definition of Notice that in the special case of Pt Tt, Assumption A' reduces to Assumption and, similarly, Assumption B reduces to Assumption B'. We use the term smooth as a synonym of Lipschitz-contimuuus gradients.
with
Analysis for (possibly) non-smooth objective functions We are going to present single analysis that encompasses both the case where is smooth (Assumption B the main paper), and the case where f may not be smooth, which we briefly discussed in Section 3.3. In order for our analysis to be agnostic the type of smoothing used and also encompass the case where f is smooth, we propose the following assumption, where (fr)keN is sequence of smooth approximations of f:
Assumption E Assumption A' holds and 3(3. L, M,, M2) E R1 such that (ft)ee satisfy:
1. vt E N, ft RD + BU( is proper closed concave on D,
Vt N, fi is differentiable on IC with sup (V S L, and ft is VHI
smooth on K.
3. VI E N. Vz E K,,lf((=)) Jr [=)1 My and [f(()) - [(=) < Mg Bo
Notice that any function satisfying Assumption with coefficient of smoothness satisfies Assumption E with 8n 1/C, Mi M2 = O. Regarding non-smooth f, we discuss in more details in Appendix specific methods to perform this smoothing, including the Moreau envelope used in Section 3.3.
The generalization of the scalar regret takes into account both the approximation functions (fe)ee and the general update z9:
Rgen
max V ((-1(((11))) ((2s))) AEA
V (f--1 + LT 8r122
(36)
1=1
25

---

Published as a conference paper at ICLR 2023
The general regret bound then takes the following form, where distinguish between smooth and non-smooth f. Recall that C //2
Theorem 11 Under Assumptions B', using VT E ST For every T N, every za E K, every 8 0, Algorithm satisfies, with probability least 6:
De + LDx
27 1n Cli(eT)
RT
(37)
T
Theorem 12 Under Assumptions E, for every 20 E R, every T 2 1 and every d > 0, Algorithm satisfies, with probability at least 8:
DR + 4M, + 2M + LDx 2
peen T
RT
(38)
VT
The proof' are given in Appendix E.
The worst-case regret of contextual bandits is 22( (((VT) (Bubeck & Cesa- Beaa-Biachhi, 2012; Dani et al., 2008; Lattimore & Szepesvári, 2020), which gives lower bound for the worst-case regret of CBCR in 0 (T) ). The dependencies on the problem parameters are all directly derived from the regret bounds RT of the underlying scalar bandit algorithm (LinUCB, SquareCB, etc.). Therefore we obtain CBCR algorithms that are near minimax optimal as soon as R I O(VT). The residual terms O terms are tied to the use of Azuma's inequality (Lemma 13) and FW analysis (using Lipschitz and smoothness parameters), and the dependencies to these parameters match usual convergence guarantees optimization (Jaggi, 2013; Clarkson, 2010; Lan, 2013). As we rely on a worst-case analysis in deriving our reduction guarantees, it remains open question whether problem-dependent optimal bounds could be recovered as well.
We make three remarks in order:
Remark 2 (Why we need a specific result for smooth f) The result for C-smooth f has a better dependency than the general result using Bu 1/C (In(eT) instead of /T), which makes fundamental difference in practice if the smoothness coefficient is close to /T. This is why we keep the two results separate.
Remark (Comparison to the smoothing as used by Agrawal & Devanur (2014)) Agrawal & Devanur (2014, Thm 5.4) present an analysis for non-smooth where, at high-level, they the smooth algorithm using JT instead of a sequence (Jt) and then apply the convergence bound for smooth f. Our analysis has two udvantages:
1. Anytime bounds: our approach does not require the horizon to be known in advance. Better bound: they obtain a bound on /InT/T by suitably choosing the smoothing parameter, 12
whereas we obtain a bound of /T. In practice, it may not make a difference if 4 is itself in VlnT/T /T, but the advantage of our approach is clear far as the analysis of FW for (C)BCR is concerned.
Remark 4 (About the confidence parameter 8' in 21,,, 8', and (1(b(41,8')) In practice, ex- ploration/eeplooiation algorithms need confidence parameter that defines the probability of their regret guarantee. For instance, in confidence-burt the confidence intervals are valid at every time step. In our case, it means that explicit upper bounds on RE are of the form Rgea (T,8") which hold with probability 1- 8'. where 8'is the confidence parameter in 21(r,, 81,88). Using the union bound, obtain bounds of the form
approaches, it is the probability with which
RT S T (TT8")/T+ C O(( In(1/6)) that are valid with probability 8 8
Note the difference in the roles of and 8': 8 is not parameter of the algorithm, it is only here to account for the randomization over contexts.
26

---

Published as a conference paper at ICLR 2023
E PROOFS FOR SECTION 3 AND APPENDIX D
This section contains the proof' for the results Section 3. All the proofs are made for the more general framework described in Appendix D. The framework of the paper can be recovered as the special case Vt E N, Pt = rt and 2 &t-
Proof of Lemma Lemma is the special case of Lemma 13 when f is smooth. Note that every satisfying Assumption A satisfies the assumptions of Lemma 13.
Proof of Theurem 2. Thm. is a special case of Theorem 11 of Appendix D, using E N, and 2 $t. The proof of Theorem 11 is given in Section E.I.
Lemma 13 Assume that VT, is differentiable on K. with Vz E K. [Vr(())] S L. Then, for every 2 E K, have:
Eaur aed
Ceor/mmxx([V))) max [n(x)a)] = max E Fe-rl(VVii- =aa(Vh--1(a) (39) TX-A
Assume furthermore that 2, function of contexts, actions and rewards up to time t. Let oj argmax(V (()))a)) For all 8 E (0, 1), with probability at least 1 - 8, we have:
aEA
T
max SES
V fi-1((2-111 - & LDk 2T In
(40)
8
Proof. Let E K. We first prove (39). The first equality in (39) comes from the maximization over functions over the simplex with linear objective: define
x
such that कद (2) E
((())))
(41)
aEAA
using some arbitrary tie- bre-breaking rule when the argmax is not unique. We have, for every policy
m:
Egn (V/= S Egp
(42)
max E [Vfi==(3) - (E (43)
XX-+A
On the other hand, it is clear that
Eg-r [e fe- (=) ((x) (x))
<
Ey-p [V-
(44)
EX-Z
and get the first equality of (39).
The second equality in (39) holds by the definition of S since for every policy ,, we have
Ep~ (V (
= [a
(45)
We now prove (40). Let (E, [-)) 121 be the conditional expectations with respect to the filtration = (z))21 where 8. is the rlalebrra generated by (s/g a/ r()ret--1]- i.e., contexts, actions and rewards up time
so that we have:
Eg ( ( (
E.-r (V)--( (()))
(46)
Using (39) gives E,
( ((xr) = max (a (s), from which we obtain sES
max ft-1 s - ((zz))a)) .ES
E, (V ft ( (1 (xx))) (V
X7 Et_ max ( (2 ( thus defines martingale adapted to S. and, using
Xo = O. we have, for all
|x X, < L sup u(z)a|12 L sup ||2 - 2'112 S LDx.
(47)
$
2.z'E
The results then follows from Azuma's inequality.
27

---

Published as a conference paper at ICLR 2023
The next lemma is the main technical tool of the paper. The proof is not technically difficult given the previous result, using the telescoping sum approach of the proof of Lemma 12 of Berthet & Perchet (2017) and organizing the residual terms.
Lemma Under Assumption E, denote Vt N, Si = max fe(s), and Rí(z) = ft -f()))
aES
Let C(T), F' (T) in R {+00} such that, VT E N. we have:
D Cr-1 C(T),
T Σ
Σ
(Ri(zz) - Re- Re-1(z)) S (T)
(48)
2
7m
And let B(T)= (T) + (T). Then, for all zo E K, VT, V0 > 0, A8 > 0, Algorithm 2 satisfies, with probability at least 8:
B(T) + RT
+
LDx
21 In
fi fr(TT) S
(49)
T
Proof. We start with the standard ascent lemma using bounded curvature on K. (Bottou et al., 2018, Inequality 4.3), denoting Ö
D Or:
f(-1(2)) 2 (2-1() (V (V 2-11)
(50)
12
2-1) fi-1 - f(-1 S f f 1 (V -p +
(51)
t²
Let us denote by g: Vt- (2(-1) and let az argmax (9t (((x))a) We first decompose the middle term:
(g: Pp 21-1) max(g: |s 21-1) max(g: u(z))a)) (g (o(l)zz))a pe)
(52)
max(gi 2 fū-1 f1-1(21-1)
Is u(xs)aa)) (ge p(zz)at - Pc)
sES
Pe
(by (53) below)
Where the last inequality uses the concavity of fe: for all 87 E argmax (s)1 we have:
fr f(-((-)) & (Vfi-(2(-11 s 2m11 (fx(VV(-1((1-1) 21-1)
(53)
ses
and thus we get
ft-1 f(-(()) S (fi-1 - fo- fe- 1 +) + Ō,
(54)
(2-1) + a +ct Õ.. + ((((zz)) R(-1(2))) (55)
tR((zi) S (t 1)
T
T Σ + Σ
T
T
C
TRT(2r) <
Σ a4
+
(Re(zz) Rx-1(z))) + Σ
(56)
t=1
1=1
t=1
1=1
Using the Lipschitz property for JT, we finally obtain
T
Ō (57)
TRr(3T) <
at +
Pt + TL
STIl2
t (Re(z)) - R +
SLDK 2T ln(1/8)+ RE"" w.p. 21-0 by (36) Lemma 13.
$F (T)
(C(T)
Which is the desired result.
28

---

Published as a conference paper at ICLR 2023
E.1 PROOFS OF THE MAIN RESULTS
We now prove the results of Appendix D.
Proof of Theorem 11. First, notice that since f differentiable on K. (since it is smooth) and since both
2T and + Σi=1 ( are in Λc, using vt, ft f, we have R = f - f((r) = ff (Sr)..
Using the notation of Lemma 14, we then have C(T) 0 and (T) 0. Also:
D Σ
Č 1
((n(()) + +)
(58)
2
The result then follows from Lemma 14.
Proof of Theorem 12. Using the notation Lemma 14, we specify C(T), F' (T) in turn
Σ
I
D
C+-1
Σ
T
D
D
VT.
VT.
(59)
2
2
30
1=1
1=1
For F' F'(T) (T), we decompose (z)) (2x) into two terms:
2M
(z)) - 1211(2)) = Si fi-1 f(-(2z)- f((2)))
(60)
tvE
Using Ei=1 vi S 2VT, we obtain F² (T) 2M Σ
+ IV
S 4M, MM.V.. Lemma 14 gives
D Bg
+ 4M1 + LDK V 21n(8-1/2)
f fr(sT) < pgen
(61)
VT
To finish the proof, notice that:
8 f(ST) - (r(r)) s sup 1fT(2') - f(=') S 2M2
(62)
s'ek
VT
The result follows from (61) and (62) using:
Rr - f((r) - - 2M₂
(63)
VT
F SMOOTH APPROXIMATIONS OF
FUNCTIONS
We discuss here in more details two specific smoothing techniques: the Moreau envelope, also called Moreau- Yosida regularization in Section F.I, then randomized smoothing in Section F.2. As in Appendices D and E, focus the general framework described in Algorithm 2.
Proof of Theorem 3. Usinh Theorem 12 above and Lemma 16 below gives the result since
DR 3
D2
Dr
+ 3 L
+ 4M, + 2M2 = + 3T. = =LDx
(64)
1
Dr
29

---

Published as a conference paper at ICLR 2023
F.1 SMOOTHING WITH THE MOREAU ENVELOPE
For functions that are non-smooth, we propose first a smoothing technique based on the Moreau envelope, following the approach described by Lan (2013). Let f R R {#o) be closed proper concave function. The Moreau envelope (or Moreau- regularization) of f with parameter ST (Rockafellar & Wets, 2009, Def. 1.22) is defined as
fa(=)= = max MERD
(5()
2 llv - 213)
(65)
For B O, let the proximal operator proxg argmax (v)) The basic properties of the Moreau envelope (Rockafellar & Wets, 2009, Th. 2.26) are that if f RD - R [ is an upper semicontinuous, proper concave function then /a is concave, finite everywhere, continuously differentiable with 3-Lipschitz gradients. We also have that the proximal operator prox is well- defined (the argmax is attained in a single point) and we have
1 ff(z)) 3 (z prox
(66)
is immediate to prove the following incqualities for every 12" and every 0:
f(=) S fs(2) S (prox
(67)
The following properties of the Moreau envelope (See (Yurtsever et al., 2018, Appendix A. and (Thekumparampil al., 2020, Lemma 1)) are key to the main results:
Lemma 15 Let 0, f: IRD + (U be a proper closed concave function, and C RDD be a convex set such that I' is locally L-Lippchitt-coniimuuus on Z. Then:
Yz Z such that pr) Z, we have ||= prox (z)] - L3 and:
L
fa(2)
$ f(z) S fa(2).
(68)
2
22 E Z such that prox proxx(=) 2, v3 > and Br > 0. we have:
f for +
B I prox,
1
L2B 8
-1)
(69)
3r
2 3r
We reformulate the lemma above in the language of Appendix D:
Lemma 16 Under Assumption A, assuming furthermore that f is L-Lipschitz on R.D Let fo fr. with 3e values of Bo and L, M2 -
8o Then f and (ft)te satisfy Assumption E with the corresponding
V L28 and M1 L.3g
Proof. By Lemma 15, fo is L-Lipschitz on ID for every t, and we have M2 = I. Moreover, Le
2
Lemma 15 also gives < f(-1 fe(x) <
(VI+T Vi) <
La
and thus M1 21
%o
n
2
F.2 RANDOMIZED SMOOTHING
We now describe the randomized smoothing technique (Lan, 2013; Nesterov & Spokoiny, 2017; Duchi et al., 2012; Yousefian et al., 2012), which consists in convolving f with a probability density function A. Following Lan (2013) who combines Trank-Wolfe with randomized smoothing for nonsmooth optimization, we present our results with A as the random uniform distribution in the balball (z E IRP ||=||2 < 1). Let > and & random variable with density A. Then the randomized smoothing approximation of f is defined as:
fa(z) Ex BE) / f(x By))
(70)
30

---

Published as a conference paper at ICLR 2023
Following (Lan, 2013; Duchi et al., 2012), abuse notation and take the "gradient" of f inside integrals and expectation below, because f is almost-everywhere differentiable since it concave. We restate the following well-known properties of randomized smoothing (see c.g., (Yousefian et al., 2012, Lemma 8)):
Lemma Let and fa defined as in Eq. (70).
Vz EK, [(z) S Ja(=) S [(z) + LB.
Sa I-Lipschitz continuous over K.
fe is continuously differentiable and its gradient is LVD
-Lipschitz continuous.
3
V= K, Vfa(=) E[V -E))-
We obtain the following results, stated in the language of Theorem 12 of Appendix D.
Lemma 18 Under Assumption A, assuming furthermore that f is L-Lipschitz on RDD.
påDz, and let 9o .DDe.
For t 2 1, let St = fo. with 3, vi+1
Then J and (St)LEN satisfy Assumption E with the corresponding values of Bo and L, M2 LD' Dr and M1 2L.
Proof. By Lemma 17, fe is L-Lipschitz on Iº for every t, so that ft has L-bounded gradient. Moreover, with this definition of Bo. fe VFFI -moothh
Bo
We have M2 LD Dic because:
DD
- f()] = [=] + B(E) - B[f(=)] (= ((E) - f(=)1I s 33
Vt
(71)
We also have M1 = 2LD Dxc because:
1a-1 - Els< Bi-18) fxx 3,E11 1|3 3el [[]]
(72)
=LD V Vt+I
1
2LD Dx
(73)
G FW-LINUCB: UPPER-CONFIDENCCE BOUNDS FOR LINEAR BANDITS WITH K ARMS
In this section, we have:
a finite action space AA which is the canonical basis of R i.e., we focus on the multi-armed bandit setting
X' C jgd where d is the dimension of the feature space. Given æ E X, the feature representation of arm A given by the matrix-vector product za, Given matrix E D we denote by |[@]| the frobenius norm of 6, i.e., ||@]| ||flaten (f) In addition, we make here the following linear assumption on the rewards:
Assumption F There is 0 E T Dxd such that ||0|| S Do such that Vo E X,1(x)a = 0xa.
Moreover, there Dx such that supl[zal|z S Dx-
zEX
We perform the analysis under Assumption E, which is the more general have. In particular, assume that we have access to a sequence (fr)eety of smooth approximations of f. We focus on the special case of Algorithm 2 that is described in the main paper, i.e., where pr Ft-
31

---

Published as a conference paper at ICLR 2023
Algorithm 3: FW-linUCB: linear CBCR with K arms.
input:8 0, 0, K. Vo AIaD Vo OaD;00 0o OAD
for t 1,....d. do
Observe context H2 ~ P. 24 E Bd
9i ( Bt t (0.02
vi E [K] Rr,; t 8 Lt, + ai 1
// see (75) and (76) for def. of Il-lyy and og
at f o u4a
Observe reward rt. let Pt g
Update & - 8 + : (r+ - 81-1)
Vi V (ōree) ye yt-1 fziza and 0. Vi yt
|/ regression
end
The algorithm. As hinted in Section 3.2, FW-LinUCB applies the LinUCB algorithm (Abbasi- Yadkori et al., 2011), designed for scalar-reward contextual bandits with adversarial contexts and stochastic rewards, to the following extended rewards and contexts, where we use [] to denote the vertical concatenation of matrices and gr = V ff
ht E Ddxk is the extended context with entries ž -g..00t......0000.) R Ddxk that the ...
feature vector of action a at time is ž,a;
f, r.'r, is the scalar observed reward,
i flatten(0) RdD is the ground-trute truth parameter vector and jo(x)) 0T ē; is the average reward function.
Notice that under assumption A and F, denoting
X 19..0. .9. ||9l|2 S L, X}
and D max
|
(74)
BEX
aEA
we have Vt, By E X with probability 1 and D& S LDx. Moreover, 1i Ma (ael S LDx, which implies in particular that for every / E [T]. Fr is T.Dx/2-subgausiin
Given this notation, the FW-LinUCB algorithm is LinUCB applied to the scalar-reward bandit problem above. The algorithm is summarized in Algorithm for completeness, where À is the regularization parameter the ridge regression, Ó, the current regression parameters, the matrix V. and the vector yt are incremental computations of the relevant matrices to compute 0, The crucial part of the algorithm is Line 3 which defines upper confidence bound on ji(r))a, denoted by û, E Rg and defined by:
Vi E [K], i4,; = 0 + (x(8 (2),
where | =
V VI Vi
(75)
and a; is defined according to Theorem 2 of Abbasi-Yadkon et al. (2011):
LDk
1+TD
2/2
as (6') = 2 dDIn
+ VXDg-
(76)
5'
Under Assumption E, have with probability 1- 8//2: et al., 2011, Theorem 2).
1-18/22: VI
N., in ji(x))a (Abbasi- Yadkori
The result. Let d dD. The regret bound of LinUCB (Abbasi-Yadkori et al., 2011, Theorem 3) and Azuma inequality give:
Theorem 19 Under Assumption E, for every T E No, for every 8' > 0, Algorithm 3 satisfies, with probability least 8':
LDx
peral <4
(VADs + 2 2m + din TD (Adi)) (77)
+ +LDx 211(288))))
32

---

Published as a conference paper at ICLR 2023
Algorithm 4: FW-SquareCB: contextual bandits with concave rewards and regression oracles
input: :nitial point $n K., exploration parameters (M))EN- A is the canonical basis of TR
for 1... do
Observe I2 P Compute (Tr( using RegSq Let g: = ( and A, = g (a(e) E R
see (81)
Let E argmax P. and L = -, aEA
// use arbitrary tie breaking rule
if + a
K K+y P (T)
Let Va E (,)
// Explorattion/explootttoon step
aEA (a)
if a = a
272
Draw ag ~ 2
Action taken at time step
Observe reward ry and update & = 8 + (r= 82-1)
end
Proof. Recall that noted in (6) We decompose the scalar regret Rypal into pseudo regret and residual term:
T
Decal T
max
((
Σ
M( Ta +
(((a))aa fz
(78)
aEA
pseudo-regret
The pseudo-regret term is bounded using Theorem 3 by Abbasi- Yadkori et al. (2011). The result applies as-is, except that they assume rewards |0Tă,| < 1, which is not the case here. The bound still valid without changes, as in our case we have max.e.4 Ta A < LDxx. The steps in the proof where they use the assumption 0, < 1 is below Equation 7 (Abbasi- Yadkori et al., 2011, I, Appendix C), which in our notation and our assumption can be written as:
Abbasi-Yadkori
max (( T I min (2 (2ar(8/2)ll 12)1 LDkk) LDx) aEA
(79)
S 20,(66 /2) (l
(80)
where the first inequality comes from Abbasi- Yadkori et al. (2011) and the second one is true in case because 20, (5') 2 LDx. From here on, the proof of Abbasi- Yadkori et al. (2011)'s regret bound follows the same as the original result." Theorem from Abbasi-Yans Yadkori et al. (201 1) gives the first term of the regret bound of the theorem, which true with probability least 8 /2 in our case because we use (8'/22))
Abbasi-Yadkori
For the rightmost term, let 3 = (3:) IEN. be the filtration where 3, is the o-algebra generated by (z1, (1,,,1.......................... Zt-1, 0t- 10-1, az). Then (Xt)teN, martingale difference sequence adapted to 3 with [X, < LDx. By Azuma's inequality, have Σ X, S LDk 2TT kn & with probability - 8' /2. The final result holds using a union bound.
Bound of Table 1. The bound is obtained by keeping the main dependencies in T, d, and Dr. ignoring the dependencies and Do, and using the fact that D I L.Dx (as described below (74)).
H FW-SQUARECB: CBCR WITH GENERAL REWARD FUCTIONS
The SquareCB algorithm was recently proposed by Foster & Rakhlin (2020) for zero-regret contextual multi-armed bandit with general reward fwwarffunctinn functions, based on the notion of online regression oracles.
In short, they have different bounds, one involving the varance of rt and the other one involving average rewards j(.). We assume rewards rr uniformly bounded in K., we do not have to deal with two different quantities bounds and have I.Dg everywhere.
33

---

Published as a conference paper at ICLR 2023
They propose, for single-reward contextual bandits with adversarial contexts and stochastic rewards, a generic randomized exploration scheme that delegates learning to an online regression algorithm. Their exploration//eploiiatoon strategy then has (bandit) regret bounded as function of the online regret of the regression algorithm. In this section, we extend the SquareCB approach to the case of CBCR. The main interest of this section is that by building on the work of Foster & Rakhlin (2020), we obtain at nearly no cost an algorithm for general reward functions for multi-armed CBCR problems.
This section shows how to extend this algorithm to our setting of concave rewards. To simplify the notation, we consider the case of finite K with atomic actions, i.e., |A| K. Our algorithm is based on an oracle for multi-dimensional regression RegSq, which provides approximate values for p.
AL, Va E X, (x) RegSa (a11,
1,, r))
(81)
The key assumption is that the problem is realizable and that RegSq has bounded regret:
Assumption G There is a function T + Raracle (T) E R. non-decreusing in T, and b a class of functions from X' to BDXK such that, for every T E N:
(Realizability) j E Q, 2. (Regret bound) For every (xe, az, rx)EETT) E (X x A K.)", we have:
Elld((z))a - -rall2
inf Σ DED
[(xx)a - rill2 - (T)a
(82)
For every (It, ae, Te)eem E x (T((T)ar K.
Assumption G is the counterpart for multidimensional regression of Assumptions 1 and 2a of Foster & Rakhlin (2020), which are the basis of the original SquareCB algorithm.
Remark 5 (The "informal" assumption used in Table 1) Notice that in Table 1, describe an
"informal" version of this assumption, which reads (x))))
)all 1|2 S Roracte (T), which is the counterpart for calti-diimensonall regression of Assumption 2b by Foster & Rakhlin (2020). Our choice in the table was to simplify the presentation, as this assumption is shorter. Our analysis is also valid under this alternative assumption. Our proofs are made under Assumption G because it is more widely applicable (more discussion of these assumptions can be found in (Foster & Rakhlin, 2020)).
Algorithm 4 describes how SquareCB principles apply to our framework. We use the framework of the main paper, or, equivalently, the special case of Algorithm 2 where E N, P: = rr and 2t = &,- Note that the algorithm is parameterized by (TI)EE, instead of the desired confidence level 8' to make the analysis more general. Theorem 20 gives a formula for 7 as a function of the desired confidence 8'. As for the previous sections, we describe the algorithm for the general case of smooth approximations of f, using ft-1 rather than V in Line of the algorithm.
At time step the regression oracle provides an estimate of p(xx), then the algorithm computes 2,, with a larger probability for the action which maximizes a + (V)(& (1))))))) The exact formula for these probabilities 21, follow the original SquareCB algorithm, with the exception that we use an ferrationddependent 7/ instead of a constant 7.
The main result of this section is the following (see Section H.2 and the next section for intermediate lemmas):
Theorem 20 Let 8' > 0. For every t E Nr. let 71
2/ (orrola())+88))) lu 42
1K
Then, under
Assumptions E and G, Algorithm 4 satisfies, with probability at least 1
8'
47
2
RSCH S AAL KT (Roracie &D& In 8' + LDD
2T In
(83)
8'
Monotonicity of Roracle is not required in (Foster & Rakhlin, 2020). We use in (94) below deal with time-dependent "t. Mcaningful (oracte(T) (T) are non-decreasing with 7 since they bound a cumulative regret. Throughout the paper, chose to provide anytime bounds rather than bounds that depend on horizon- dependent parameters. The analysis with fixed 7 casier.
34

---

Published as a conference paper at ICLR 2023
Recall that Assumption B is special case of E when Pt Tr, are here. Thus, the bound on RT is the same irrespective of whether we use the algorithm for smooth f (in which case Repcal RT ) or with smooth approximations (in which case 1e 1t7" This is because only the Lipschitzness (ft),en is used in the analysis of Re for FW-SquareCB.
The following result is direct corollary of Theorem 20, and gives the order of magnitude we obtain for smooth f. Obtaining a similar for smooth approximations of f, using Theorem 12 instead of Theorem I is straightforward.
Proof of the FW-SquareCB regrei bound of Table 1. We apply the bound obtained by Theorem 20 within the bound of Theorem 11, using 8' := 20/3 and := 6/3. We obtain:
ALV KT KT (T) + 8 In 12r2 8 + +LL 27 Eli(eT)
RT
(84)
T
The bound given in the theorem uses the sub-additivity of v to group the terms in vnn for better readability.
The proof of Theorem 20 is decomposed into two subsections: in the next subsection, we make the necessary adaptations to the SquareCB analysis to account for multi-dimennional regression. This proof follows essentially the same steps as the original analysis of SquareCB. There are only two changes:
We use multi-dimenssooal regression instead of scalar regression, while need to bound scalar regret. There is an additional step to go from the scalar regret to the multi-dimensional regression, but it turns out there is no added difficulty (see first line of the proof of Lemma 23).
For coherence with the overall bounds of the paper, we use an anytime analysis using an increasing sequence of (7r) instead of a fixed exploration parameter y that needs be tuned for a specific horizon determined a priori. This introduces bit more difficulty, where the main tool is Lemma 24. Our choice of anytime bound is more for coherence in the presentation of the paper than an intended contribution.
Nonetheless, what we gain with our anytime bound is that the exploration parameter 7y does not depend on fixed horizon. What we lose, however, is that we need high-probability bound on cumulative errors based on (tracie that is valid for every t (see Lemma 23), while the "fixed gamma" case only requires this bound to hold for the horizon T. This is the reason for the In T factor in our bound, which is not present in the original paper. In the next sections, we the following notation:
Jt V 18
M: 96 Me(s),
" max u1 a,
(85)
aEAA Ar max L.a.
4 = 97 (x)))
(86)
aEA
H.1 ADAPTATION OF SQUARECB PROOF TO CBCR
In the SquareCB paper, Foster & Rakhlin (2020) study high probability bounds on a different type of regret, based on average rewards associated to the actions p( )a, rather than observed rewards ri- However, this difference has little influence since we can start with the following incquality, which is similar to (Foster& & Rakhlin, 2020, Lemma 2).
Lemma 21 Under Assumption E,, for every E N., every 8' > Algorithm satisfies
T g. rr)
T
Σ(e
Ea [45 - [Ta]] + LDxv 2T ln(11"))).
(87)
Proof. The proof is by Azuma's inequality. Let F = (3t)eeN. be the filtration where 3 21), and let denote Xy
is the o-algebra generated by (21, P2. 1e-1, It1 Eawa, [4Ta]] gfr.. Then, (Xr)reN a martingale adapted to filtration and satis- fies [x, X,-1| S LDk. We obtain the result by noticing that X1- Ets (ug glrr) Di Eawa, [nj []a] and applying Azuma's 's inequality to Xy.
35

---

Published as a conference paper at ICLR 2023
Notice that the difference between (Foster & Rakhlin, 2020, Lemma 2) and our Lemma 21 is that consider the randomization over actions and rewards, while they only consider the randomization over actions because they study average rewards. However, since it does not change the upper bound on the variations of the martingale, this additional randomness does not change the bound.
The next step the fundamental step in the proof of the original SquareCB algorithm. Even though the notation differ slightly from the original paper, the proof is the same as in (Foster & Rakhlin, 2020, Appendix B):
Lemma 22 (Foster & Rakhlin, 2020, Lemma 3) For every E No, the choice of it and M(hb, Te, 8') of Algorithm guarantees:
Ea [Mg 11
2K %
" EB ((T))=)
(88)
The last step of these preliminary lemmas is to relate the cumulative expected error to the oracle regret bound. We use here the same proof as (Foster Rakhlin, 2020, Lemma 2). We then have:
Lemma 23 Under Assumption E, for every 8' > 0. Algorithm 4 satisfies, w.p. at least - 8':
21
VT N., Σ Ba-a, 1 -0----11 aTaa)² s 2L22Roractee (T) 16L In
(89)
8'
Proof. We first notice that Σt= Eawa, (ATT- S L2 L Ba-a, - We then apply the same steps as the proof of (Foster Rakhlin, 2020, Lemma 2) to Ein Ea-a, [[ā((z) - p( )a[[]] (which we do not reproduce here) to obtain: for every every T' E N. every 8/4 > O, with probability at least 1 - 8/:
1
Σ E Easa. [M]] -aTaa < 2L Roacte (T) 16L In
(90)
8
Let 8' > 0. Applying union bound and taking 5, 2 the desired result.
8' that Σt= 8,
x² 8 s 8', obtain 12
Notice the log T factor in the bound, which appears because the bound is valid for all time steps. This is because propose anytime convergence bounds, with the exploration parameter that decreases with time, whereas (Foster & Rakhlin, 2020) only prove their result in the case where the exploration parameter is chosen for specific horizon.
As the main first step for the final result, we need these two lemmas which are the main technical steps to anytime bound. The proof is deferred Appendix J.2
Lemma 24 Let (Nt).eN E RT be sequence of non-negative numbers, denote Ar Σt= de and let (TT)TeN such that VT E N, Ar > 0 and Ar 2 Ar.
X
2 Ar. A
(91)
We get the following corollary
Lemma 25 Let R (T,8') 21, Roracte (T) 16T.2 In 2T
8. Under the conditions of Lemma
23, assume that there 7 > such that Vl E [T], = =70y F. Then, for every 8' > Algorithm 4 satisfies, w.p. at least 8
T
Σ
Ba-a, [R]aa 14Ta < 27o TR' (T,
(92)
36

---

Published as a conference paper at ICLR 2023
Proof. Using >/ S / (t,8'' the sum on the left hand side of (92) has the form of Lemma 24
multiplied by no VT, with probability 1 8' by Lemma 23, The result thus follows from applying both Lemmas.
H.2 FINAL RESULT
Proof of Theorem 20. Notice that the value of Tt given in the theorem is equal
2
7t V
(93)
R'
orocle (1,8'/2)
Using this formula, we have
2K
K
R Rt, (t,8'12)
Ry oraclo (T,8'/2)
1
(94)
7t
Vt
12KTR (T, (2).
(95)
Where the first line comes from the monotonicity of Roracte (T) of Assumption G.
Using Lemmas 22 and 25, we thus have, with probability - 82/2:
T
Σ
Eawai [e -4 S 2 2KTR (T,8/2).
(96)
Using union bound and Lemma 21, we obtain, with probability at least 8':
2
Σ (Mt sire) s $2 2KT (T,8'12) LDK 27 In
(97)
8'
I FW-LINUCBRANK: CBCR FOR FAIR RANKING WITH LINEAR CONTEXTUAL BANDITS
Algorithm FW-iinUBBRakk: linear contextual bandits for fair ranking.
input: : > 0, > 0, 8u E K. Vo for 1,....... do
Al yo Og, 0 O2
Observe context ~ P
UCB on is (2x), see Lem. 26 for def. of on // FW linear optimization step Observe exposed items et ( 11m and user feedback et E {0, 1mm
bi, - -4, arl || [x1,,,l
top-ke 0s--1 (8, (8--1) : + 8z,
0h--1 (8-1))
0amti
Update & f- 8 (r: $c-1)
m
V, V + Σ end
e Ye x- 1t-1
a and 0, Vi= yt
regression
In this section and following the previous sections, analyze Algorithm 5 under Assumption E, which is more general than the bound proposed in the main paper, which used Algorithm under Assumption B. The only difference in the algorithms is the use of f--1 instead of f in Line 4 of Algorithm 5. This allows us to provide the algorithm for both smooth and non-smooth objective functions f-
The bound decomposed into two parts: we describe the results for online regression within our observation model for ranking in the next subsection. Then dive into the final result.
37

---

Published as a conference paper at ICLR 2023
1.1 RESULTS FOR ONLINE LINEAR REGRESSION (FROM (Li ET AL., 2016))
Even though our linear contextual bandit setup is different from e.g.. (Lagrée et al., 2016) for ranking, the availability of the feedback 6,,i, which tells us whether item i has been exposed, makes the analysis of the online linear regression similar to the general setup of linear bandits, Our approach builds on the confidence intervals developed by Li (2016), which expands the analysis of confidence ellipsoids for linear regression of Abbasi-Yadkont Yadkori et al. (2011) to cascade user models in rankings.
Each Cr is -subgaussian (because Bernoulli), and is conditionally independent of the other random variables conditioned and on ε,,i and Zy,;- The incremental linear regression of line of Algorithm is the same as (Abbasi-Yadkori Yadkori et al., 201 I). Our observation model satisfies the conditions of the analysis of confidence ellipsoids of Li et al. (2016), from which we obtain:
Lemma Under the probabilistic model described in Section 4, and under Assumption Let 8' > 0 and À 2 Di and let
1 (Ve((Vr) 2
arr(0')
In
+ VADa.
(98)
Vgo
Then, under Assumption and with the notation of Algorithm 5, we have:
(LLi et al., 2016, Lemma 4.2)) with probability 1 8'. all T 0, 0 lies in the confidence ellipsoid:
Cr (0 E RR 1|ō 0lv5 ar(()))
(99)
((Li et al., 2016, Lemma 4.4)):
1 2
TD 1+
(r( -
2
+ dln
+ VAD=-
(100)
8
Ad
These results stem from (Li et al., 2016, Lemma A.4 and A.5) that claim that, with the assumptions of Lemma 26, the following inequality holds with probability 1:
ΣΣ
m
det V1 1e, 21n det(VV)
s 2ddnn (1+
TD Ad
(101)
Notice that terms equivalent Dx and Dy do not appear in (Li et al., 2016) because they assume they are < 1. The D3 term comes from modification necessary in (Li et al., 2016, Lemma A.4) while Da required by the initial confidence bound proved by Abbasi- Yadkori al. (2011). The term Te plays the constant C. of (Li al., 2016).
1.2 GUARANTEES FOR FW-LINUCB
We start by writing an alternative to Assumption for the case where f is not smooth to carry out analysis with little assumptions on f as possible:
Assumption D' The assumptions of the framework of Sec. 4 hold, as well as Ass. E. Moreover, 0f. Vt E N Szm+i
(z) > O, and Vx E X, 2.12 by (x) 2 by(z) =... = bm(()) O.
Lemma 27 Under Assumptions and C Let T > 0,8' > 0 and A z D2 Then for every 8' 0,
Algorithm 5 satisfies, with probability at least - 8':
3 8 (V2m
TD2
Xd )
3 g I..xy 2T
RE 2T Th
1 2d 1+
where oer is defined in Lemma 26.
38

---

Published as a conference paper at ICLR 2023
Proof. Let 9: V and of argmax.e.1 p r2)- Let furthermore 8' > 0. Assume the algorithm uses (r(88))), so that C, {0 E R. 1|0, 0llv, S (8)3333)
Let us define tu similarly to Proposition 4, i.e., Vt E N.. Ae such that vi E [m]] Pl,s = pz(2z) and ft = 8,b(x,)) viewed as column vector, with i defined line of Algorithm 5, We have:
T
T
Σ
max (((zraa - -r)) Σ (g (((xs)a meas) EEA
+
ge p.ac plxx)a
1=1
B,
T
(ge
Hllz )az - -
:=
Step 1: Upper bound on Ei= A via optimism Let O. For 0 E Rd,, denote mg(#) D (recall = m + 1), the average reward function where parameters replace 8. We first show that for every a E A, we have maxgec, (9x (g( S (gx éta),, where iz is given in Line 3 of Algorithm
Given A. let denote by mat(a) the view of di-dimmesional column vector). Recalling that T3 is a m X matrix and 9r. E Rm+1 let us denote by Iem the vector containing the first m dimensions of gr. We have:
x permutation matrix (instead of an
(ge (g(x)))) (1..maa(())b(a. - pt.m x
(102)
therefore:
max(gi (gg(x))) = I. mat(a) + gt. max (gt.m+ xx mat(a))(x.))
(103)
REC.
$ 1 mat (a)b( + mt.m+1 (a)(ba)((aa)) = (ge ((za).
(104)
The first equality is because Mt.++1 2 0. The second equality is deduced by direct calculation from the definition of C, in Lemma 26, which gives it,; maxgec, @T
By Proposition 4 we have that defined at Line 4 of Algorithm 5 maximizes (ge (ar) over We thus have maxac.A maxgec, (9t. (ug(xz) S (9.. ((ra)).
By Lemma 26, we have 0 E C2 for all t 2 0 with probability 1 1 8//3. Therefore, with probability 1- 1-6'/3. 8'/3, we have for all t 2 0: (gr (o(x)))t)) I (gr (ear). Noting that u0( = u(xx) by definition of f. we obtain that Vt, A, S and thus Ei= As S with probability 8//3.
8-//3
Step Upper bound on Σ B, using linear bandit techniques Let a E ET denote the i-th row of ma), which contains only Os except 1 at the rank of item i in a. Since fú, and u(zz) only differ the last dimension, which is the user utility, we have, using (102):
B, m1. ((iz (Tat(a))))
-t
Σ (fe. (xxe))
(105)
Denoting Ct,; = b(rr)) E R the expected exposure item i in ranking a; given context 2t, we have:
m
> m (0.-1 - (01-1-0)TaL T)T + (8) pally, ees (106)
B, = gt
Σ - (((x))e))
E L.
< L
[10,-1 01lv1 || 1ly, + ar(8' ( Ee,
(by Cauchy-Schwarz)
1=1
39

---

Published as a conference paper at ICLR 2023
By Lemma 26, have, with probability 1 - 83/3: 110-- 8llv. ax1(8/3), and thus:
8'
m
Bi S 2Lay
Le 1, E,,
(107)
8'
2La
-
a 1 (Ee, - e(i))
Σ I |aaallle 01,
(108)
3
X
We first deal with the sum over t the right-hand side, using Ct,i E {0, 1}:
m
bellly, e
a1 v (x,e)
Etii
(109)
T
T
C
(by Cauchy-Schwarz)
1=1
1=1 1=1
TD& Ad
$ <VTRy dln (1+
(by 101)
For the left-hand term, we have that (Et= Xi) is martingale adapted to the filtration == (TT) where 3r is the o-algebra generated by (2) 01 ,,, Thus, with probability at least - 8' /3/3, we have
aT).
with | <
Dx
vx
m ΣΣΣn
178
Dx Vī
3 8
3 8
Lxally (Et, - e1,1) S
2T
S
2T In
(110)
Where the last inequality comes from the assumption À that with probability - 28'/3, we have:
D2 k. We conclude this step by saying
3 2l 2 δ +
+ vddnm (1 TD
Σ t=1
B. 2Lar
Tk
(111)
3
Ad
Step 3: Upper bound on Et= X, using Azuma's inequality Following the same arguments as in the proof of Thm. 19, let (3:).eN) be the filtration where 3, is the o-algebra generated by az). Then (Xt)eN a martingale difference sequence adapted to 8 with [Xal S. LDk. so that Σ X. S L 3 with probability 1 - 8'/3.
(I1, 01, .i,...... :t. Gt-1.
Tt.1 11-101111111110
The final result is obtained using union bound, considering that Step 1 and Step 2 use the same confidence interval given by Lemma which is valid w.p. 2 1 - 03/3, Step 2 uses an addition Azuma inequality valid w.p. 1 8' /3, and step 3 uses additional Azuma inequality which valid with probability 2 8//3.
Theorem Under Assumptions B, C and D, for every 8' > O, every T E N., every X 2 D2Fk, with probability least 8', Algorithm 1 has sealar regret bounded by
pecal o LV CWTTv/dl(TT (VdIn(T/8) + DOVA+ (T/d)
(13)
Thus, considering only d. d.T. T. and 5 8' Alg. has regret Ro O dis (blu(T/8)
w.p. least 8.
/T
Proof. Let > 0 and use 8' = 36/4 and â = 5/4 in the bound on Hr obtained by applying Lemma 27 and Theorem 11. Notice that Using > 2 Dž.k and Dx = O(k), we have:
R ccal (T,35/4) of [oor(o) (Tdln(T//) LT TIn(1/8)
(112)
40

---

Published as a conference paper at ICLR 2023
and ar()) = DoVA).
We thus get
R scal (T,
(LTTT))O(((TT))))((//) (Van(T)))++ LLVTTIn(18))
(113)
=O(LVTTVan((/5)) (VaT://)))(((((()++++)) + V
(114)
For the smooth case, the total bound adds O(Lk/TIm(1/)) + ) A bound on the complete regret is thus
Rr R - OOLOT
DoVA+ y c In (dlm(T/0) + (
(115)
T
J ADDITIONAL TECHNICAL LEMMAS
J.1 PROOF OF LEMMA 7 (8 IS COMPACT)
Lemma 7 Under Assumption A, S is compact and VT E N., YOLT E X2, ,((())) is compuct.
Proof. We start with S(I).T). Let 21.7 E XT. We notice that S(x is the image A by the continuous mapping é (R*)7 - RRD defined by p(a1,..,, @T) = Σ (((x) Since A is compact, A is compact well. S(x1.T) is thus the image of a compact set by continuous function, and is therefore compact.
For the set S, provide proof here using Diestel's theorem (see (Yannelis, 1991)). Consider the set-valued map defined by G + {B P)
G(x) p(z) = (u(x)a TE
(116)
Then, S can be written as the Aumann integral of G over X' w.n. P. ie.
8 s= Gdp = { gdp g s
(117)
where 9 C (A, P) is the collection all P-integrable selections G, i.e. the collection of all P-integrable functions g X' -> IR. such that g(x)) E G(x)) for P-ae E X.
Now, since A is compact, convex and nonempty. the values of the set-valued function G are nonempty, convex, and compact. Moreover, since a )al|2 < +oo because Vz, a, μ(xraa a E Kc the set-valued function G P-integrably bounded in the sense of (Yannelis, 1991, Section 2.2). It then follows from Diestel's Theorem (Yannelis, 1991, Theorem 3.1) that the collection of P. P-integrable selections of is weakly compact L ('X,' P). Finally, since ト> Jx g dP a weakly continuous mapping from (XX P) to IR D and S C Rº is the image of & under this mapping (refer to the correspondence (117)), we deduce that S is weakly compact as subset of ED, and therefore compact since R is fnite-dimeesional.
J.2 PROOF LEMMA 24
Lemma 24 Let (Nt).n RT be sequence of non-negative numbers, denote Ar ΣT de and let (AT)TeN such that VT E Ar > 0 and Ar AT.
T
< 2 Ar.
(91)
Ae
41

---

Published as a conference paper at ICLR 2023
Proof. First, treat the case where Ao > 0. Then 442 [T] 0. We thus have
X
Σ
(118)
VA.
We now prove that the right-hand term is S VT. Let us observe that, for every a 2 0, > a:
1
B v
(119)
2 VB
which is proved using vB vB Ag = 0):
S ƒم-a
1 ds 2
Using the telescoping sum (with
2/8
2/B
VA. A
A d =2 S 22 AT.
(120)
=
we obtain the desired result.
More generally, if Åo = 0, there are two cases:
Vf E [T] A then the result is true;
2. otherwise, let To = min E [T] x > 0}. Using the result above, we have:
A
S 22/r..
(121)
A
V
42


Reviews:
[{"review_id": "yJDKLlupZLI", "reviewer": "Reviewer_Gk2g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers contextual bandits with multi-dimensional rewards, with a known concave function that transforms the cumulative multi-dimensional rewards to a one-dimensional value to be maximized. This paper proposes a method to reduce the CBCR problem to scalar-reward bandits which has been extensively studied, so that no restrictions necessary on the policy space. Also, a smoothing technique is provided in case of non-smooth concave function $f$. Then, the paper introduces an application using their reduction method, which focuses on contextual ranking bandits with fairness-aware objectives, and shows that their method is efficient with regret guarantee. Experimental evaluations are presented.", "summary_of_the_review": "Overall, I enjoyed reading this work, and I learnt interesting results from it. The idea of the reduction method is novel and general. Related literature is well-discussed in Introduction section.", "strength_and_weaknesses": "Strengths:\n* This paper proposes an interesting method to reduce CBCR problem to a studied problem, being the first to remove restrictions on the policy space.\n* The reduction method has some generality to cover a class of applications that can be modeled by CBCR framework, such as the fair ranking problem mentioned in the paper.\n\nWeaknesses:\n\nOverall, I believe this is a high-quality paper, which has some solid contributions that may benefit future works. Here, I have some minor suggestions and questions:\n* In the ``setting'' paragraph in Section~2, the reward is defined as a noisy multi-dimensional reward. I would suggest authors to further declare the noise, e.g., the support of the random noise; the restrictions on the distribution; is it heavy tailed? As the distribution of the noise can heavily affect the policy design, even it may have zero mean. Or, if the only requirement of the noise is zero mean in this work, please also mention that.\n* Throughout the paper, the concave function $f$ on the reward is assumed as known by the learner, and the reduction also requires the knowledge of $f$. What if $f$ is unknown so that $f(\\sum_t r_t)$ is unknown? How much difficulty will be brought to address the CBCR problem with an unknown $f$? As I think an unknown $f$ is more commonly seen in real world. Or, what will be the case if both the reward $r_t$ and $f$ are unknown and we only know $f(\\sum_t r_t)$? Nonetheless, both alternative settings can be considered in future works.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "wI18rNWwKZv", "reviewer": "Reviewer_aNts", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers contextual bandits with concave rewards where the rewards are defined by a concave objective function with stochastic reward vectors. This setting removes the restrictions on the policy space compared to prior works. Under this setting, this paper proposes an (first) algorithm with the vanishing regret. The theoretical results and techniques could be applied to fair ranking problems. Experimental results also support the derived results. \n", "summary_of_the_review": "Overall, I think that the studied model in this paper is well-motivated with more general problem setting. The proposed algorithm is sound  together with the related analysis. Therefore, I recommend “accept”.\n\n", "strength_and_weaknesses": "This paper is well written. The model (setting) in this paper is interesting, well motivated (based on the provided concrete examples) and more general compared to prior works. The geometric interpretation of CBCR (policy space spanned by a convex set) is a nice explanation and illuminates the optimization directions. This paper provides a nice and elegant reduction from CBCR regret to a scalar-reward bandit problem based on Frank-Wolfe analysis. This bypasses the core challenges in optimization in policy space. However, it is not clear  (at least to the reviewer) whether the obtained regret for CBCR (under this specific setting) is optimal or not. This paper lacks analysis and explanation in this aspect. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "A2l-5sEb12", "reviewer": "Reviewer_4Gmp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors provide the first algorithms for provably vanishing regret for Contextual Bandits with Concave Rewards.", "summary_of_the_review": "Exemplary work.\n\nConfidence is just a 3 because I didn't check the proofs.  If I get time I'll circle back to them.  \"Math/other details were not carefully checked.\"", "strength_and_weaknesses": "Strengths:\n  * Multi-objective criterion arise frequently in practice.\n  * Reduction-based algorithm design maximizes reuse of existing and novel componentry and overall utility of approach.\n     * e.g., the discussion mentions constraints (good: reduction to CB-knapsack algos might work).\n  * Figure 1 (right) is particularly persuasive.\n\nWeaknesses;\n  * FW-LinUCB will give you nice theorems, but composing with the infinite action linear version of square cb[2] will give you an algorithm people will actually want to deploy. \n    * We never use UCB algos in production here because they are not robust to reward feedback delay.\n    * You might also find interesting a composition with a smoothed regret variant of square cb for infinite action spaces [3].\n  * It's not clear how to elicit the trade-off function in practice.  \n    * For example, does the Lin et. al.[1] elicitation technique yield a concave tradeoff function (or, e.g., would preference elicitation be viable over a constrained model class like generalized gini)?\n\n[1] https://arxiv.org/abs/2203.11382\n\n[2] https://arxiv.org/abs/2207.05836\n\n[3] https://arxiv.org/abs/2207.05849", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1V0zF0Pei3p", "reviewer": "Reviewer_joWt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a contextual bandit problem with **stationary** context and **fixed** action set. At each step, the environment randomly selects a context $x$, then the player needs to choose an action $a$ that maximizes $f(\\mu(x)a)$ where $f(\\cdot)$ is a known concave function and $\\mu$ is an unknown matrix-valued function. This paper solves this problem by nesting Frank-Wolfe algorithm with standard linear/contextual bandit algorithms.\n", "summary_of_the_review": "\nThe setting does not sound interesting or important to me. Besides, I have some concerns as prescribed in \"Weakness\" section.", "strength_and_weaknesses": "\n### Strength\n\nThe paper provides a new setting, designs a new algorithm, proves its theoretical guarantee, and conducts experiments on real-world data to validate its performance. The paepr is rather complete for this problem.\n\n### Weakness\n\nBy considering only the stationary context set and fixed action set, the paper is actually more restrictive than most contextual bandit literature that considers possibly adversarial context sets. In particular, the paper shall not claim at the end of Sec. 2 that it \"subsumes classical contextual bandits.\" Also, the \"reduction\" in Sec. 3.2 is not that rigorous because LinUCB and SquareCB both work for adversarial contexts, meaning that the reduction cannot be understood as that the algorithm in the paper could replace LinUCB or SquareCB. Consequently, I am concerned on the impact of this paper over the bandits learning society.\n\nThe paper does not contain much technical novelty that could possibly inspire future work, as the proof seems to be a straightforward combination of Frank-Wolfe algorithm.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster