Diversified Recommendations for Agents with Adaptive Preferences
Authors: William Brown
Arpit Agarwal
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
bandits
convex optimization
recommender systems
fairness

Abstract: When an Agent visits a platform recommending a menu of content to select from, their choice of item depends not only on immutable preferences, but also on their prior engagements with the platform. The Recommender's primary objective is typically to encourage content consumption which optimizes some reward, such as ad revenue, but they often additionally aim to ensure that a sufficiently wide variety of content is consumed by the Agent over time. We formalize this problem as an adversarial bandit task. At each step, the Recommender presents a menu of $k$ (out of $n$) items to the Agent, who selects one item in the menu according to their unknown {\it preference model}, which maps their history of past items to relative selection probabilities. The Recommender then observes the Agent's selected item and receives bandit feedback of the item's (adversarial) reward. In addition to optimizing  reward from the selected items at each step, the Recommender must also ensure that the total distribution of chosen items has sufficiently high entropy. 

We define a class of preference models which are {\it locally learnable}, i.e.\ behavior over the entire domain can be estimated by only observing behavior in a small region; this includes models representable by bounded-degree polynomials as well as functions with a sparse Fourier basis. For this class, we give an algorithm for the Recommender which obtains $\tilde{O}(T^{3/4})$ regret against all  item distributions satisfying two conditions: they are sufficiently diversified, and they are {\it instantaneously  realizable} at any history by some distribution over menus. We show that these conditions are closely connected:  all sufficiently high-entropy distributions are instantaneously realizable at any history of selected items. We also give a set of negative results justifying our assumptions, in the form of a runtime lower bound for non-local learning and linear regret lower bounds for alternate benchmarks.

Diversified Recommendations for Agents with Adaptive Preferences
Arpit Agarwal'
William Brown
Department of Computer Science
Department of Computer Science
Columbia University
Columbia University
New York, NY 10027
New York, NY 10027
argit..ggavallccolluum edu
w. wroonnccluumbia... edu
Abstract
When an Agent visits platform recommending menu of content to select from, their choice of item depends not only on immutable preferences, but also on their prior engagements with the platform. The Recommender's primary objective is typically to encourage content consumption which optimizes some reward, such as ad revenue, but they often additionally aim to ensure that a sufficiently wide variety of content is consumed by the Agent over time. We formalize this problem as an adversarial bandit task. At each step, the Recommender presents menu of k (out of n) items to the Agent, who selects one item in the menu according to their unknown preference model, which maps their history of past items to relative selection probabilities. The Recommender then observes the Agent's selected item and receives bandit feedback of the item's 's (adversarial) reward. In addition to optimizing reward from the selected items at each step, the Recommender must also ensure that the total distribution of chosen items has sufficiently high entropy.
We define class of preference models which are locally learnable, i.e. behavior be estimated by only observing behavior in small
over the entire domain region; this includes models representable by bounded-degree polynomials as well functions with a sparse Fourier basis. For this class, we give an algorithm for the Recommender which obtains (T73/4) regret against all item distributions satisfy- ing two conditions: they are sufficiently diversified, and they are instantaneously realizable at any history by some distribution over menus. We show that these conditions are closely connected: all sufficiently high-entropy distributions are instantaneously realizable at any history of selected items. We also give a negative results justifying our assumptions, in the form of runtime lower bound for non-local learning and linear regret lower bounds for alternate benchmarks.
Introduction
Suppose you manage an online platform that repeatedly provides menus of recommended content to visitors, such as sets of videos to watch or items to purchase, aiming to display options which agents will engage favorably with and yield you high rewards (in the form ad revenue, watch time, purchases, other metrics). In many settings, the preferences of agents are not fixed priori, but rather can change as a function of their consumption patterns-thh -th deeper one goes down a content "rabbit hole". the further one might be likely to keep going. This "rabbit hole" effect can lead to (unforescen) loss of revenue for the platform, as advertisers may later decide that they are not willing to pay much for this "rabbit hole" content as they would for other content. The scope of negative
http://www.columbia.com a/4931/ cttbooowngithbb.ooo
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

effects emerging from these feedback loops is large, ranging from the emergence of "echo chambers" [15] and rapid political polarization [23] increased homogeneity which can decrease agent utility [9], amplify bias [20], or drive content providers to leave the platform [22]. These are harms which many platforms aim to avoid, both for their own sake and out of broader societal concerns.
Hence, the evolving preferences of the Agent can be directly at odds with the Recommender's objec- tives of maximizing revenue and ensuring diverse consumption patterns in this dynamic environment. Our goal is to study such tensions between the interaction of these two players: the Recommender that recommends menus based on past choices of the Agent so as to maximize its reward (subject to diversity constraints), and the Agent whose preferences evolve as a function of past recommendations.
To this end, we consider a stylized setting where the Recommender is tasked with providing a menu of & recommended items (out of n total) every round to an Agent for 7 sequential rounds. In each round, the Agent observes the menu, then selects one of the items according to their preference model M, which the Recommender does not know in advance. The preference model M takes as input the Agent's memory vector v, which is the normalized histogram of their past chosen items, and assigns relative selection probabilities to each item. The selected item at each round results in reward for the Recommender, specified by an adversarial sequence of reward vectors, which the Recommender receives as bandit feedback, in addition to observing which item was selected. The Recommender must choose sequence of menus to maximize their reward (or minimize regret), subject a diversity exppeeeeeeeeeee
constraint, expressed as a minimum entropy for the empirical item distribution.
However, any regret minimization problem is incomplete without appropriate benchmark for comparing the performance of a learner. An entropy constraint alone is insufficient to define a such benchmark. Due to intricacies of the Agent's preference model, there may be item distributions which are impossible to induce under any sequence of menus (e.g. they may strongly dislike the most profitable content). Adding to the challenge is the fact that the preference model is initially unknown and must be learned, and the set of item distributions which are instantaneously realizable by sampling a menu from some distribution can shift each round as well. Several immediate proposals are infeasible: it is impossible to obtain sublinear regret against the best fixed menu distribution, or even against the best item distribution realizable from the uniform memory vector. We propose a natural benchmark for which regret minimization becomes possible: the set of item distributions which are everywhere instantaneously realizable (the EIRD( set), i.e. item distributions such that, at any memory vector, there is always some menu distribution which induces them. We show that this set is also closely related to entropy constraints: when M is sufficiently dispersed (a condition on the minimum selection probability for each item), EIRD(M MM contains all sufficiently high-entropy distributions, and so regret minimization can occur over the entire high-entropy set.
1.1 Our Results
We give an algorithm which, for a minimum entropy set He and preference model M, allows the Recommender to obtain (773/4) regret against the best distribution in the intersection of He and (M). provided that M satisfies X-dispersion and belongs learnable. A X-dispersed preference model M assigns preference score of at least À >> 0 to every item, ensuring a minimum positive probability of selection to each item menu. Dispersion is a natural assumption, given our restriction to EIRD (T)D as items which only have positive selection probability in part of the domain cannot be induced everywhere. The local learnability condition for model class enforces that the behavior of any particular model can be predicted by observing behavior only in a small region. This is essentially necessary to have any hope of model estimation in this setting: we show that if learning class from exact queries requires making queries to many points which are pairwise well-separated, exponentially many rounds are required to implement query learning. Despite this restriction, we show that several rich classes of preference models are indeed locally learnable, including those where preference scoring functions are expressed by bounded-degree multivariate polynomials, or by univariate functions with a sparse Fourier basis.
class M which is locally
Our algorithm is explicitly separated into learning and optimization stages. The sole objective for the learning stage is to solve the outer problem: recover an accurate hypothesis for the preference model. We select sequences of menus which move the Agent's memory vector to various points near the uniform distribution, enabling us to implement local learning and produce a model hypothesis M. We then shift our focus to the inner problem for the Recommender, which is natural to view as a bandit linear optimization problem over the set of distributions in consideration, can use M to identify

---

distribution of menus which generates a particular item distribution. However, representing the EIRD(M) (M) set explicitly is impractical, as the functions which generate feasible sets from the history can be highly non-convex. Instead, we operate over the potentially larger set where intersections are taken only over the sets IR, M) of instantaneously realizable distributions we have observed thus far. This precludes us from using off-the-shelf bandit linear optimization algorithms black box, as they typically require the decision set to be specified in advance. We introduce a modification of the FKM algorithm [13], RC-FKM, which can operate over contracting decision sets, and additionally can account for the imprecision in M when generating menu distributions. This enables the Recommender to guide the Agent to minimize regret on their behalf via the sequence of menus they present.
1.2 Summary of Contributions
Briefly, our main contributions are:
1.
We formulate the dynamic interaction between a Recommender and an Agent as an adver- sarial bandit task. We show that no algorithm can obtain o(T) regret against the best menu distribution, or against the best item distribution in the IRD set of uniform vector. We then consider EIRD(M) (M) and argue that it is natural benchmark for regret as it also contains all sufficiently high entropy distributions over items.
2. We define a class of locally learnable functions, which functions that can be learned only using samples from a small neighborhood. We show number of rich classes of functions where this is possible. and further we show that any class which is not locally learnable cannot be learned quickly by any algorithm which fits a hypothesis using queries.
3.
We give an algorithm for the Recommender that achieves Ö(T3/4) regret against EIRD(M) for locally learnable classes of preference models that are X-dispersed, which implements local learning to obtain sufficiently accurate hypothesis for use in optimizing menu distributions. As component of this, we develop new algorithm for bandit linear optimization which can operate over contracting decision sets, and which can account for bounded adversarial imprecision in the played action.
Overall, by considering this stylized setting we are able to provide several insights into the dynamic interaction between Agent and Recommender. While our algorithm is useful tool for Recommender who is already committed to providing diversified recommendations, we also view our results presenting an intrinsic argument for incorporating such constraints. When preferences adapt over time, and Agents may be prone to venturing down content "rabbit holes", restricting attention to recommendation patterns which are not too concentrated on small sets of items can in fact make the regret minimization problem tractable by discouraging consumption patterns which may be difficult to draw the Agent back from. This suggests synergy between the goal of regret minimization and showing diverse content to the user.
1.3 Related Work
Feedback loops in user preferences have received significant attention in the recommender systems lit- erature, particularly for models with multiple agents which make use of collaborative filtering methods, and with explicit adaptivity models which are less flexible than those we consider [7, 9, 20, 28. 22]. Within the online learning literature, our formalization bears some resemblance to bandit problems where multiple arms can be pulled simultaneously, which have received much recent attention [30, 29, 8, 3]. Our results also share similarities with work on optimization from revealed preferences, where mapping to a nested convex problem must be learned [27, 12]; with the performative predic- tion literature, where actions induce distribution shift which impacts instantaneous reward potential [24, 18]; and more broadly, with repeated game problems against adaptive agents [5, 11, 10]. Further related work is discussed in Appendix A.
1.4 Organization
In Section 2, we introduce our setting and key definitions, analyze the local learnability of several classes of preference models, and give series of negative and structural results. In Section 3
3

---

introduce bandit linear optimization algorithm for contracting sets, which we use as a subroutine for our main algorithm Section We discuss the intuition for our proof techniques throughout, with full proofs deferred to the appendix.
2 Model and Preliminaries
The central object of setting is the preference model of the Agent, which dictates their relative item preferences based on their selection history and expresses their adaptivity over time.
Definition 1 (Preference Models), preference model is a mapping M A(n) + [0. 1|" which maps memory vectors v to a preference score vector S. M().
We assume that any imput (nn) M (such as the empty history at t 1) results in the uniform score vector where Mu); = 1 for all i. A constraint on our sequence interactions with the Agent that the resulting item distribution must have sufficiently high entropy.
Definition (Diversity Constraints), diversity constraint He C (nn) is the convex set containing all item distributions A(n) with entropy at least Lee. v is in He if and only if:
H(v) Σ log(1)) 2
We say that constraint Hg is e-satisfied by distribution if we have that min drv (zr, v) Se. where drv is the total variation distance between probability distributions.
Our algorithmic results can be extended to any convex constraint set which contains small region around the uniform distribution, but we focus on entropy constraints as they are quite natural and have interesting connections to our setting which consider in Section 2.3.
2.1 Recommendation Menus for Adaptive Agents
An instance of our problem consists of item set [ni] menu size preference model M for the Agent, a constraint H., a horizon length of T rounds, and a sequence of linear reward functions Pl...... pr for the Recommender. In each round & fl..... T):
The Recommender chooses a menu K, C N with [Kel = k:
The Agent chooses item E K2 with probability
S
Pka,ve,h
ΣjEK, Soei
and updates its memory vector to the normalized histogram
6, + t ++1
L.
e++1
++1
where e, is the ith standard unit vector.
The Recommender observes receives reward (r(e:) for the chosen item.
The goal of the Recommender is maximize their reward over T rounds subject to er satisfying He. might seem the reader that the Recommender can 'manipulate' the Agent to achieve any preference score vector over time; however, this is not true as many score vectors might not be achievable depending on the preference model.
2.2 Realizability Conditions for Item Distributions
For any memory vector we define the feasible set of item choice distributions for Agent in the current round, each generated by a distribution over menus which the Recommender samples from. Definition 3 coaittannoousy-Rcalizatttl Distributions at v). Let PK.v E (nn) be the item distribution selected by an Agent presented with menu K at memory vector v, given by:
PK.n.
ΣjEK Sv.j

---

The set of instantaaneoussy-ralliiaeel distributions at is given by:
IRD(0, M) convhullpk,..
k<()))
For any z E IRD(V, M), any menu distribution 2 E A(())) specifying a convex combination of menu score vectors F which sum to z will generate the item distribution a upon sampling.
One might hope to match the performance of the best menu distribution, or perhaps the best realizable item distribution from the uniform vector. Unfortunately, neither of these are possible.
Theorem There no algorithm which can obtain o(T') regret against the best item distribution in the IRD set for the uniform vector, against the best menu distribution in A (()). even when the preference model is known exactly and is expressible by univariate linear functions.
We give separate construction for each claim, with the full proof deferred to Appendix. The first is case where the optimal distribution from the uniform vector cannot be played every round, as it draws the the memory vector into IRD sets where the reward opportunities are suboptimal. The second considers menu distributions where obtaining their late-round performance requires committing early to irreversible course of action. Instead, our benchmark will be the set of distributions which are realizable from any memory vector.
Definition& 4 (Everywhere Instantaneouslyy set of everywhere instantoneouulyy-eallaaaa distributions is given by:
SaaireoouuslyeRRRRaaabbaal Realizable Distributions). For preference model M, the
EIRD(M) = n IRD(U, M).
vED(n)
This is the set of distributions x E (n) such that from any memory vector u, there is some menu distribution z such that sampling menus from d induces choice distribution of x for the agent.
Note that the set EI) is convex, as each IRD(U, M) is convex by construction.
2.3 Conditions for Preference Models
The algorithm we present in Section 4 requires two key conditions for a class of preference models: each model in the class must be dispersed, and the class must be locally learnable. This enforces that the Agent is always willing to select every item in the menu they see with some positive probability, and that the behavior at any memory vector can be estimated by observing behavior in a small region.
Definition 5 (Dispersion). A preference model M is X-dispersed if Su,i 2 for all (n)) and for all i, i.e. items always have score of at least at any memory vector.
The dispersion condition plays an important role in the analysis of our algorithm by enabling efficient exploration, but additionally coincides with diversity constraints in appropriate regimes.
Theorem 2 (Higg-Entropy Containment in EIRD). Consider the diversity constraint Hofor e = 1² exp(1/r)
log(n) - % and let T 2 exp(-7). Let M be a x-diispesed preference model with X 2 n For any vector H.. there a vector v' E (IRD(M) such that drv (v, v') is al most ((T).
The key step here, proved in Appendix B.2, that EIRD(M) contains the uniform distribution over any large subset of items, and taking mixtures of these can approximate any high-entropy distribution.
Next, for class of models be locally learnable, one must be able to accurately estimate a model's preference scores everywhere when only given access to samples in an arbitrarily small region. Definition (Local Learnability). Let M be a class of preference models, and let
EIRD(M) = N EIRD(M).
NEM
Let v² be point in EIRD(M), and Va be the set of points within distance from v", for such that Va C EIRD(M). M h-locally learnable if there is some v² and an algorithm A which, for any M M and any > O, given query access to normalized score estimates 8n where [|s, - M(v/MM S 3 for any u E Va (where M -E, (()a) and for some B, can produce a hypothesis model M such that M M(x)/M S for any x E a(n) and e = (13).
5

---

The local learnability condition, while covering many natural examples shown in Section 2.4, is indeed somewhat restrictive. In particular, it difficult to see that classes of piecewise functions. such as neural networks with ReL.U activations, are not locally learnable. However, this appears to be essentially a necessary assumption for efficient learning, given the cumulative nature of memory in our setting. We show a runtime lower bound for any algorithm that hopes to learn an estimate M for the preference model M via queries. Even Recommender who can force the Agent to pick particular item each round, and exactly query the preference model for free at the current memory vector, may require exponentially many rounds to learn M if the points it must query are far apart.
Theorem 3 (Query Learning Lower Bound), Suppose the Recommender can force the Agent to select any item at each step and can query M(ve) at the current memory vector vt. Let As be an algorithm which produces hypothesis M by receiving queries (v) for each S. For points v and v', let (u v') = max, U; 1. Then, any sequence of item selections and queries by the Recommender requires at least
19|-1
T
min GEn(S)
II i=1
(1+ + dm oii + 1)))
rounds to run A(S), where π (S) is the set of permutatiinn over S and oii) is the ith item in a.
We prove this in Appendix B.3. Notably, this implies that if S contains m points which, for any pair (v, v²) have both dmaa (v, v') 2 7 and dmax (v', v) 2 7, at least O ((1 + ++)") rounds are required.
2.4 Locally Learnable Preference Models
There are several interesting examples of model classes which are indeed locally learnable, which prove in Appendix C. In general, our approach is to query a grid of points inside the radius a ball around the uniform vector, estimate each function's 's parameters and show that the propagation of over the entire domain is bounded. Note that the normalizing constants for each query we observe may differ; for univariate functions, can handle this by only moving a subset of values at time, allowing for renormalization. For multivariate polynomials, we consider two distinct classes and give separate learning algorithm for each; we can estimate ratios of scores directly for multilinear functions, and if scores are already normalized we can avoid rational functions altogether. Each local learning result we prove involves algorithm which makes queries near the uniform vector. We later show in Lemma 4 that taking À 2 k²/n suffices to ensure that these queries can indeed be implemented via an appropriate sequence of menu distributions for any M in such a class.
2.4.1 Bounded-Degree Univariate Polynomials
Let MAU be the class of bounded-degree univariate polynomial preference models where:
For each i, M();, = fe,), where fs is a degree-d univariate polynomial which takes values in [A, over the range [0, 1] for some constant X >> O.
Univariateness captures cases where relative preferences for an item depend only on the weight of that item in the agent's memory, i.c. there are no substitute or complement effects between items.
Lemma 1. MBUP is Odd)-oocaly learnable by an algorithm ABUP with s O(e (.a (a))
2.4.2 Bounded- Degree Multivariate Polynomials
Let MBMLP be the class of bounded-degree multilinear polynomial preference models where:
For each M(); = f(()), where f. is a degree-d multilinear (i.e. linear in each item) polynomial which takes values in [λ, 1] over A(n) for some constant À > 0,
and let MANMP be the class of bounded-degree normalized multivariate polynomial preference models where:
For each i, M(), = fi()), where fa a degree-d polynomial which takes values in [A, 1]
over ((n) for some constant À > O, where E, f((v) C for some constant C.

---

Together, these express a large variety of adaptivity patterns for preferences which depend on frequencies of many items items simultaneously. In particular, these can capture relatively intricate "rabbit hole" effects, in which some subsets of items are mutually self-reinforcing, and where their selection can discourage future selection of other subsets.
Lemma 2. MMMLPP and MENMP both O(n Jlocalll learnable, for B I Ol poly(n(d/a)))) and B S F(n.dj respectively, where F(n, d) is independent of other parameters.
?
2.4.3 Univariate Functions with Sparse Fourier Representations
We can also allow for classes of functions where the minimum allowable depends some parameter. Functions with sparse Fourier representations are such an example, and naturally capture settings where preferences
somewhat cyclical, such when Agent goes through "phases" of preferring some type of content for a limited window. We say that a function f : R + I is
E-sparse if f() = Ex=1 E where E [-F, F] denotes the i-th frequency and &, denotes the corresponding magnitude. We say that an E-sparse function f is separabe when min (n 1 ny á. Let Msrn be the class of univariate sparse Fourier representation preference models where:
For each i, (V),,, = f((),, where f. is a univariate E-sparse and d-separable function which, over [0, is L-Lipschitz and takes values in [}, 1] for some constant À > 0.
Lemma 3. MsFR(()) is Onee)llocaly learnable by an algorithm ASFR with 3 < 0 ( and any a 2 (11/)))
3 Bandit Linear Optimization with Contracting Sets
The inner problem for the Recommender can be viewed as bandit linear optimization problem over He n EIRD(M). However, representing EIRD(M) challenging even if we know M exactly, involves an intersection over infinitely many sets (generated by a possibly non-convex function), and net approximation would involve exponential dependence on n. Instead, our approach will be to operate over the larger set He n (N, IRD(2;, M)) for the memory vectors i we have seen thus far, where representing each IRD exponential dependence only on (from enumerating all menus).
The tradeoff is that we can no longer directly use off-the-shelf bandit linear optimization algorithms for known and fixed decision set such FKM [13] or SCRIBLE [1] as subroutine, as our decision set is contracting each round. We introduce an algorithm for bandit linear optimization, a modification of the FKM algorithm we call Robust Contracting FKM (RC-FKM), which handles this issue by projecting to our estimate of the contracted decision set at each step. Additionally, RC-FKM can handle the imprecision resulting from our model estimation step, which can be represented by small adversarial perturbations to the action vector in each round; we modify the sampling rule to ensure that our target action remains in the true decision set even when perturbations are present. We prove the regret bound for RC-FKM in Appendix D.
Algorithm 1 (Robust Contracting FKM).
Input: sequence of contracting convex decision sets Kc,,... KK containing 0, perturbation vectors Eı,... Er where ||E+|] e, parameters 17-
Set 1 = 0
for t 1 do
Draw u, E S₁ uniformly at random, set yt = It + 8u, + &t Play le. observe and incur loss di E [o, 1]. where [[dr] fe(et)
Let g: 8 2
Let Ke+1.6,e f It E K+t13
Update 2441 = 1 (1t (gd))
end for
Theorem 4 (Regret Bound for Algorithm 1), For sequence of G-Lipschitz linear losses Ji..... JT and a contracting sequence of domains K1,.... Kr (with K.₃ S K2 for j > i, each with diameter at most D, and where ball of radius > 8 around 0 is contained in KT), and adversarially
7

---

chosen unobserved vectors Er with l1&ll S e which perturb the chosen action at each step, with parameters 1 n/
D and ô = T47 Algorithm I obtains the expected regret bound
GDT3/4
2GGDT
Blol min (1) s nGDD3/
Recommendations for Adaptive Agents
Our main algorithm begins with explicit learning phase, after which we conduct regret minimiza- tion, and at high level works as follows:
First, we learn an estimate of the preference model M by implementing local learning with set of points close to the uniform memory vector, which suffices ensure high accuracy of our representation with respect to M. If the number of local learning queries is independent error terms and = (c), we can complete this stage in to = O(1/c)) O(T%/4) steps.
For the remaining T - to steps, we implement RC-FKM by using the learned model M7 at each step to solve for menu distribution which generates the desired item distribution from the current memory vector, then contracting the decision set based on the memory update. Theorem (Regret Bound for Algorithm 2). Algorithm 2 obtains regret bounded by
RegIetCrEIRD(M M) (T) S 2 nGT (5 + c)T
nGT3/4
+CGT) =((T8/4)
where to is the time required for local learming, = O(k2 /n), and c, O(r T-1/4) and results in empirical distribution such that He is Oattssitiii with probability least 1 O 1/4).
4.1 Structure of (M)
The key tool which enables us to implement local learning is construction for generating any point near the uniform via an adaptive sequence of menu distributions, provided À is sufficiently large.
Lemma For any X-dispersed M where
k² n² EIRD(M (M) contains all points x E A(N) satisfying
ke 1-1
| xu ruoloo
n(n 1)
where zu is the uniform"
vector.
We give an algorithmic variant of this lemma which is used directly by Algorithm 2, well variant for uniform distributions over smaller subsets as À grows, which we use to prove Theorem 2.
4.2 Subroutines
Our algorithm makes use of number of subroutines for navigating the memory space, model learning, and implementing RC-FKM. We state their key ideas here, with full details deferred to Appendix E.
UniformPad:
In each round, include the le items with smallest counts, breaking ties randomly.
MoveTo(z):
Apply the same approach from UniformPad to the difference between the current histogram and x.
Query(x):
Play a sequence O(n/k) partially overlapping menus which cover items, holding each constant long enough for concentration, and compute relative probabilities of each item.

---

Algorithm 2 A no-regret recommendation algorithm for adaptive agents.
Input: Item set [n], menu size k. Agent with A-dispersed memory model M for A > where M belongs an S-locally learnable class M, diversity constraint H., horizon T,, G-Lipschitz linear
losses Ps.... .......P1' .P..
Let (pad (1/e²))
Let fmowe = (1/e²²
Let Equery (11/c2)
Let = 0 (
Get set of S points in the a-ball around uniform vector zy to query from AM
Let to /pad= + S( mooe + (query)
Run UniformPad for Epad rounds
for J; do
Run MoveTo(z;) for move rounds
Run (ue for Equery rounds, observe result ((x;)
Run MoveTo(zz) for muov rounds
end for
Estimate model M using AM for 3= = O(c)
Let vt, be the empirical item distribution the first items to items
Let Kro = H. (in n dimensions, with Ft,a = 1 Ei= Tt,í, and s.t. zy translates to 0)
Initialize RC-FKM to run for T =T to - rounds with r = O(k2 D(k2/n), 8, = 7-174
for t = lo to T do
Let xt, be the point chosen by RC-FKM Use PlayDist(zz) to compute menu distribution 2
Sample K, 2g. show K₃ to Agent
Observe Agent's 's chosen item i and reward (e(e..
Update RC-FKM with (e(e..) f-1 Let 1/ t 0 + Ci.
Update the decision set K++1 Kr, IRD( M)
end for
PlayDist(r):
Given an item distribution x, we solve a linear program to compute a menu distribution using (v) which induces when menu is sampled and the Agent selects an item.
The intuition behind our learning stage that each call Query(æ) can be accurately estimated by bounding the "drift" in the memory vector while sampling occurs, as the number of samples per query small compared to the history thus far. Each call MoveTo(zr) for point within the a-ball can be implemented by generating an empirical distribution corresponding to point in EIRD(M for sufficiently many rounds.
The resulting model estimate M yields score estimates which accurate for any memory vector. To run RC-FKM, we translate to an n 1 dimensional simplex representation, and construct menu distribution implement any action T, via linear program (PlayDist(r)). The robustness guarantee for RC-FKM ensures that the loss resulting from imprecision in M is bounded, and further ensures that the resulting expected distribution remains inside H. (and that H. is approximately satisfied with high probability by the empirical distribution). We contract our decision set in each step with the current space IRD( we; .M), which will always contain EIRD (M), the best point which is competitive with the best point in EIRD(M) (M).
5 Conclusion and Future Work
Our work formalizes a bandit setting for investigating online recommendation problems where agents' preferences can adapt over time and provides number of key initial results which highlight the importance diversity in recommendations, including lower bounds for more "ambitious" regret benchmarks, and no-regret algorithm for the EIRD set benchmark, which can coincide with the

---

high-entropy set under appropriate conditions. Our results showcase tradeoff between the space of strategies one considers and the ability to minimize regret. Crucially, our lower bound constructions illustrate that we cannot hope to optimize over the set of recommendation patterns which may send agents down "rabbit holes" that drastically alter their preferences, whereas is indeed feasible to optimize over the space of sufficiently diversified recommendations.
There are several interesting directions which remain open for future investigation, including ad- ditional characterizations of the EIRD set, discovering more examples or applications for local learnability, identifying the optimal rate regret dependence on other parameters, settings in- volving multiple agents with correlated preferences, and consideration of alternate models of agent behavior which circumvent the difficulties posed by uniform memory.
10

---

References
[1] Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Interior- point methods for full- information and bandit online learning. IEEE Transactions on Information Theory, 58(7):4164
4175, 2012.
[2] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 39-75. PMLR, 07-10 Jul 2017.
[3] Arpit Agarwal, Nicholas Johnson, and Shivani Agarwal. Choice bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18399-18410. Curran Associates, Inc., 2020.
[4] Jason Altschuler and Kunal Talwar. Online learning over a finite action set with limited switching. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1569-1573. PMLR, 06-09 Jul 2018.
[5] Mark Braverman, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. Selling to no-regret buyer. CoRR, abs/ 176, 2017.
[6] Sébastien Bubeck. Bo" az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing Nested Convex Bodies Nearly Optimally, pages 1496-1508. 2020.
[7] Keith Burghardt and Kristina Lerman. Emergent instabilities in algorithmic feedback loops. CoRR, 0/5/2201.072033 2022.
[8] Róbert Busa-Fekett Eyke Hüllermeier, and Adil El Mesaoudi-Paull Preference-based online learning with dueling bandits: A survey. CoRR, abs/1 Abs//807.1. 1398, 2018
[9] Allison J. B. Chaney, Brandon M. Stewart, and Barbara F. Engelhardt. How algorithmic confounding in recommendation systems increases homogeneity and decreases utility. CoRR, abs/17100 1214, 2017.
[10] Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. CoRR, al.0151 2015.
[11] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. CoRR, abs//909, 13861, 2019.
[12] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. CoRR, abs/1710.07885t 2017.
[13] Abraham Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. CoRR, cs/LG/0408007, 2004.
[14] Mariano Gasca and Thomas Sauer. Polynomial interpolation in several variables. Advances in Computational Mathematics, 12(4):377-110, Mar 2000.
(15) Yingqiang Ge, Shuya Zhao, Honglu Zhou, Changhua Pei, Fei Sun, Wenwu Ou, and Yongfeng Zhang. Understanding echo chambers in e-commerce recommender systems. CORR, abs/2007.0244 2020.
[16] Taha Hassan. Trust and trustworthiness in social recommender systems. In Companion Proceedings of The 2019 World Wide Web Conference. WWW "19 page 529-532, New York. NY, USA, 2019, Association for Computing Machinery.
[17] Elad Hazan. Introduction to online convex optimization. CoRR, abs/1909.05207, 2019.
[18] Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner. Regret minimization with performative feedback. CoRR, abs/2202.00628. 2022.
[19] O. D. Kellogg. On bounded polynomials in several variables. Mathematische Zeitschrift, 27(1):55-64, Dec 1928.
[20] Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin
Burke. Feedback loop and bias amplification recommender systems. CoRR, abs/2007. 2020.

---

[21] Celestine Mendler-Düinner. Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic opti- mization for performative prediction. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4929-4939. Curran Associates, Inc., 2020.
[22] Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard S. Zemel, and Craig Boutilier. Optimizing long-term social welfare in recommender systems: A constrained matching approach. CoRR, 0oss/2008.00104 2020.
[23] Derek O' O'Callaghan, Derek Greene, Maura Conway, Joe Carthy, and Pádraig Cunningham. Down the (white) rabbit hole: The extreme right and online recommender systems. Social Science Computer Review, 33(4):459-44) 2015.
[24] Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. CoRR, abs/2002.06673,, 2020.
[25] Eric Price and Zhao Song. A robust sparse fourier transform in the continuous setting. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 583-600. IEEE Computer Society, 2015.
[26] Anshuka Rangi, Massimo Franceschetti, and Long Tran-Thie Thanh. Sequential choice bandits with feedback for personalizing users' experience, 2021.
[27] Aaron Roth, Jonathan R. Ullman, and Zhiwei Steven Wu. Watch and learn: Optimizing from revealed preferences feedback. CoRR, 0os/1504400100 2015.
[28] Ayan Sinha, David Gleich, and Karthik Ramani. Deconvolving feedback loops in recom- mender systems. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 3251-3259, Red Hook, NY, USA, 2016. Curran Associates Inc.
[29] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 1865):153811556 2012. JCSS Special Issue: Cloud Computing 2011.
[30] Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as dueling bandits problem. In Proceedings of the 26th Annual International Conference Machine Learning, ICML '09, page 1201-1208, New York, NY, USA, 2009. Association for Computing Machinery.
[31] Xing Zhao, Ziwei Zhu, and James Caverlee. Rabbit holes and taste distortion: Distribution- aware recommendation with evolving interests. In Proceedings of the Web Conference 2021, WWW '21, page 888 899, New York, NY, USA, 2021. Association for Computing Machinery.
[32] Tijana Zmnic Eric V. Mazumdar, S. Shankar Sastry, and Michael I. Jordan. Who leads and who follows in strategic classification? In NeurlPS, 2021.
12


Reviews:
[{"review_id": "rKB3NBYIp8t", "reviewer": "Reviewer_9Hsd", "summary": "This paper studies a game in which menus of items are shown to a user.  The user has unknown preferences which influence the choice of the item from the menu (exfactly one item is chosen).\n\nThe chosen item has two consequences:\n1) it modifies the agents future behavior and makes it more likely to select the same action\n2) it gives the recommender a reward which is non-personalized and depends only on the chosen item.\n\n", "questions": "\nI think the presentation would be improved by examples / case studies and possibly simulation studies as well.", "limitations": "The authors contribution to me is a type of bandit problem rather than taylored to RecSys.  Producing a more convincing RecSys motivation would be interesting.  Although perhaps the paper will stand on its own as a \"bandit\" paper - I will leave that for others to judge.\n\nThe term \"adversarial\" is used.  I take this to mean something \"zero sum\" or game theoretic is going on.  I don't see why this would occur, usually the recommender system typically has incentives to improve the user experience.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe problem of feedback loops in recommender systems is interesting and there is a lack of good papers studying this question so it was a pleasure to see this paper address the topic.\n\nThat said this problem is not a clear analogue of a recommendation problem I know.  I expect people who work on industrial Recsys might have difficulty seeing the connection to the problem being studied and real Recsys problems, although this may not be the intent.\n\nThe complete formulation of a recommender system in a bandit framework contains user behavior interspersed with (usually) slates of recommendations and response to the recommendations.  Reward as measured at A/B test time is computed over the time line and may include clicks but also sales or engagement.  The intervention that an A/B test measures is therefore a combinatorial object and 'diversity' is measured within the slates and within time.  Reward itself is not attached to the recommendations but to the timeline.  It is entirely possible that a diverse collection of recommendations result in receiving reward, but this can only be understood if we attach the reward to the timeline not to the individual recommendations.  This paper like most of the recsys literature attaches the reward to the individual recommendations.\n\nDiversity across different user timelines is also necessary for exploration purposes.\n\nThis paper makes interesting observations in a simplified model where there are causal implications in the timeline of a recommendation.  Although it isn't to my mind diversity in any of the above senses.  Indeed if I understand correctly only the selected action gives a reward and this is a non-personalized reward although the selected reward has long term impacts on the user (which is very novel).\n\nThe writing is quite dense for a recommender systems audience right now.  I would suggest augmenting the mathematical presentation with examples to increase accessibility.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E2X15V4N2V", "reviewer": "Reviewer_e35G", "summary": "The paper discusses the problem of online recommendation for a single agent with adaptive preferences as an adversarial bandit problem. The authors show that it is necessary to consider a different benchmark, as there are no linear regret algorithms that can compete against the typical best menu/item distribution. Since the available bandit optimization algorithms do not apply to contracting decision sets, the authors provide a new algorithm for this setting that also handles imprecision from estimation. Under a class of locally learnable functions and a mild assumption on each preference model, the authors supply a local learning algorithm to learn an estimated model that achieves $\\tilde{O}(T^{3/4})$ regret. ", "questions": "- How can this model be applied to the setting with a single recommender and $N$ different agents? Could the current model handle having more agents whose preferences and behaviors are correlated?\n\n- Could there be experimental sections that show the performance of the second algorithm? While the discussions of the subroutines in section 4.2 are helpful, it could be useful seeing how the algorithm performs on some synthetic data.  ", "limitations": "- The authors sufficiently address the limitations in Section 5.\n\n- While the authors address the negative societal impact of having a small set of items recommended, more discussion on the societal effect of having diversified recommendations could be useful in section 1. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper investigates an interesting problem of recommendation with adaptive preferences and provides novel theoretical results in their lower bounds.\n\n- The theoretical contributions are significant in advancing the study of diversification in recommendation problems.\n\n- The authors provide a comprehensive set of assumptions and sufficient explanations for why they are necessary. \n\n- The first algorithm (RC-FKM) is intuitive, and the second algorithm has sufficient discussion.\n\n- The authors adequately address the current literature in their related work section and the appendix.\n\n- The paper is well-organized and easy to follow.\n\nWeaknesses:\n\n- The current model only considers a single agent, which is restrictive.\n\n- In section 2, when the authors first introduce the diversity constraint, the variable $d_{TV}$ was not defined before (line 152). \n\n- In section 3, algorithm 1 and theorem 4 lack sufficient discussion of the results. \n\n- The theoretical results could benefit from having a small proof sketch next to them.\n\n- In line 261, there is an extra \"and\" at the end.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DGq-SAz3Zy0", "reviewer": "Reviewer_DAFz", "summary": "The paper 'Diversified Recommendations for Agents with Adaptive Preferences' looks at the problem of recommending a set of items in an online setting where customer preferences adapt over time to satisfy both the diversified recommendations criteria as well as to avoid an effect of the \"rabbit hole\". The authors formulate the problem as an adversarial bandit task and demonstrate a negative result in terms of finding an algorithm that satisfies all the proposed constraints. The authors then suggest an algorithm for bandit linear optimisation. ", "questions": "* in the abstract (line 23) you mention that you give a set of negative results justifying your assumptions. Do you refer to Theorem 1?\n* It would be nice to add references to the appendix, like in the case of the Theorem 1 proof.\n* while I do not mind reading papers with unconventional structure, I found in this case that hiding the literature overview in the appendix is making it even more difficult to read. \n* there is an interesting claim that the further users go down the rabbit hole, the more likely they are to continue. While I agree, I think it would be good to substantiate this claim. (line 31)\n* (lines 60-61) you write that you propose a 'natural benchmark'. I'm not sure I understand what it means in this context. \n* (lines 108, 126) typos\n* (line 152) I couldn't find where $d_{TV}$ is introduced", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My review of strengths and weaknesses will be relatively brief. As I'm quite inexperienced with the topic, I admit that it was very difficult to read and understand. The paper poses a very interesting problem (high originality) and conducts several theoretical analyses to provide insights into the problem. As the intended audience must be much more familiar with the concepts, I can't comment on this part, but I might recommend to incorporate empirical results or clarifying simulations/visualisations based on the suggested Algorithm 2 or RC-FKM. This might help to grasp the results and the outlined concepts for the more inexperienced audience. Therefore, I will omit the quality and significance from my review and would rate clarity on a medium-to-low level. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8BPrUNLO4e0", "reviewer": "Reviewer_sqQK", "summary": "The paper formalizes the recommendation process as a bandit task. The agent recommends items based on a preference model of the user learning to maximize rewards based on a diversity constraint.  They also introduce locally learnable functions that can be learned from a small neighborhood i.e., behavior over the entire domain can be learned from a small region \n\n", "questions": "Some notations are used before being defined. What is s_(v,i)?, d_TV\n\nHow do you correlate entropy and diversity?\n", "limitations": "I was unable to find discussions on limitations", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper gives insights on the importance of diversity in recommendations\nThe paper also has proofs in formalizing a benchmark for regret\nLocally learnable functions are defined fir learning from a small neighborhood\n\n\nWeakness\nThough there are proofs showcasing the results, there is no evaluation on real data to support the claims of the paper.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept