Strategic Apple Tasting
Authors: Keegan Harris
Chara Podimata
Steven Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: strategic classification
strategic learning
apple tasting
bandit feedback
learning with incentives
TL;DR: We study the problem of online classification when data is generated by strategic agents, and the learner only receives apple tasting (or bandit) feedback.

Abstract: Algorithmic decision-making in high-stakes domains often involves assigning decisions to agents with incentives to strategically modify their input to the algorithm. In addition to dealing with incentives, in many domains of interest (e.g. lending and hiring) the decision-maker only observes feedback regarding their policy for rounds in which they assign a positive decision to the agent; this type of feedback is often referred to as apple tasting (or one-sided) feedback. We formalize this setting as an online learning problem with apple-tasting feedback where a principal makes decisions about a sequence of $T$ agents, each of which is represented by a context that may be strategically modified. Our goal is to achieve sublinear strategic regret, which compares the performance of the principal to that of the best fixed policy in hindsight, if the agents were truthful when revealing their contexts. Our main result is a learning algorithm which incurs $\tilde{\mathcal{O}}(\sqrt{T})$ strategic regret when the sequence of agents is chosen stochastically. We also give an algorithm capable of handling adversarially-chosen agents, albeit at the cost of $\tilde{\mathcal{O}}(T^{(d+1)/(d+2)})$ strategic regret (where $d$ is the dimension of the context). Our algorithms can be easily adapted to the setting where the principal receives bandit feedback---this setting generalizes both the linear contextual bandit problem (by considering agents with incentives) and the strategic classification problem (by allowing for partial feedback).

Strategic Apple Tasting
Keegan Harris
Chara Podimata
Zhiwei Steven Wu
Carnegie Mellon University Pittsburgh, PA 15213
MIT & Archimedes/ Athela RC Cambridge, MA 02142
Carnegie Mellon University Pittsburgh, PA 15213
keeganh@cmu.co edu
podimata@mit... edu
zstevenwu@cmu. edu
Abstract
Algorithmic rrcision-makingg in nigh-stakes domains often involves assigning de- cisions to agents with incentives to strategically modify their input to the algorithm. In addition dealing with incentives, in many domains interest (e-g. lending and hiring) the maaker only observes feedback regarding their policy for rounds which they assign positive decision to the agent; this type of feedback is often referred to apple tasting (or one-sided) feedback. We formalize this setting as an online learning problem with apple-tasting feedback where a principal makes decisions about sequence of I' agents, each of which is represented by context that may be strategically modified. Our goal is to achieve sublinear strategic regret, which compares the performance of the principal to that of the best fixed policy in hindsight, if the agents were trutlffu when revealing their contexts. Our main result is a learning algorithm which incurs Ó (vTT) strategic regret when the sequence of agents is chosen stochastically. We also give algorithm capable of handling addversarially-choseee
agents, albeit at the cost of ((T(d+1)/(4++) strategic regret (where is the dimension of the context). Our algorithms can be easily adapted to the setting where the principal receives bandis feedback- this setting generalizes both the linear contextual bandit problem (by considering agents with incentives) and the strategic classification problem (by allowing for partial feedback).
Introduction
Algorithmic systems have recently been used to aid in or automate decision -aaiinn in high-stakes domains (including lending and hiring) in order to, e.g., improve efficiency reduce human bias [12, 11. When subjugated to algorithmic decision- -making in high-stakes settings, individuals have an incentive to strategically modify their observable attributes to appear more qualified. Such behavior is often observed in practice. For example, credit scores are often used to predict the likelihood an individual will pay back loan time if given one. Online articles with titles like "9 Ways Build and Improve Your Credit Fast" are ubiquitous and offer advice such as "pay credit card balances strate- gically" in order to improve one's credit score with minimal effort [46]. In hiring, common advice ranges from curating list of keywords to add to one's 's resume, to using white font in order to "trick" automated resume scanning software [23, 2]. If left unaccounted for, such strategic manipulations could result in individuals being awarded opportunities for which they are not qualified for, possibly the expense of more deserving candidates. As a result, it is critical keep individuals' incentives in mind when designing algorithms for learning and decision- decision-making in high-stakes settings.
In addition to dealing with incentives, another challenge of designing learning algorithms for high- stakes settings is the possible selection bias introduced by the way decisions are made. In particular, decision-makers often only have access to feedback about the deployed policy from individuals that have received positive decisions (e.g., the applicant is given the loan, the candidate is hired the job and then we can evaluate how good our decision was). In the language of online learning, this type of feedback known as apple tasting (or oie-sided) feedback. When combined, these two complications (incentives & one-sided feedback) feedbbaa have the potential to amplify one other, as algorithms can learn
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

only when a positive decision is made, but individuals have an incentive to strategically modify their attributes in order to receive such positive decisions, which may interfere with the learning process.
1.1 Contributions
We formalize our setting as game between a principal and sequence of strategic agents, each with an associated context X, which describes the agent. At every time t E (I....,T') .T), ). the principal deploys a policy Tt, a mapping from contexts to binary decisions (e.g., whether to accept/reject loan applicant). Given policy T agent t then presents (possibly modified) context x to the algorithm. and receives decision ag = गH (x(). If a = L, the principal observes reward ra (ae) a, = 0 they receive no feedback. (0) is assumed to be known and constant across rounds." Our metric of interest is strategic regret, i.e., regret with respect to the best fixed policy hindsight, if agents were truthful when reporting their contexts.
(1);
Our main result is an algorithm which achieves Ö(VT) strategic regret (with polynomial per-round runtime) when there is sufficient randomness in the distribution over agents (Algorithm 1). At high level, our algorithm deploys a linear policy at every round which is appropriately shifted to account for the agents' strategic behavior. We identify sufficient condition under which the data received by the algorithm at a given round is "clean", i.e. has not been strategically modified. Algorithm then online- learns the relationship between contexts and rewards by only using data for which is sure clean.
In contrast to performance of algorithms which operate in the non-strategic setting, the regret of Algorithm 1 depends on an exponentially-large constant c(d, ~ (1 5) 5)-d due to the one-sided feedback available for learning. where d is the context dimension and 5 E (0. 1) is a parameter which represents the agents' ability to manipulate. While this dependence on c(d, 6) is insignificant when the number of agents T + oo (i.e. is very large), it may be problematic for the principal whenever T is either small or unknown. To mitigate this issue, we show how to obtain Ö(d- T2/33 strategic regret by playing a modified version of the well-known explore-then-comee (Algorithm 2). At a high level, Algorithm 2 "explores" by always assigning action 1 for a fixed number of rounds (during which agents do not have an incentive to strategize) in order collect sufficient information about the mata-generating process. It then "exploits" by using this data learn a strategy- aware linear policy. Finally, we show how to combine Algorithm and Algorithm 2 to achieve (miincc(d, 5) vT, d T2233) strategic regret whenever T is unknown.
algorithm
While the assumption of stochastically-chsse restrictive in some specific settings. Our next result is an algorithm which obtains ((T(4+)/((+ strategic regret when agents are chosen adversarially (Algorithm 4). Algorithm 4 uses variant of the popular Exp3 algorithm to trade off between a carefully constructed set of (exponentially-man) policies [6]. As result, it achieves sublinear strategic regret when agents are chosen adversarially, but requires an exponentially-large amount of computation at every round.
agents is well-motivated in general, may be overly
Finally, we note that while our primary setting of interest is that of one-sided feedback, all of our algorithms can be easily extended to the more general setting in which the principal receives bandit feedback at each round, i.e. rr (0) is not constant and must be learned from data. To the best of our knowledge, we are the first to consider strategic learning in the contextual bandit setting.
1.2 Related work
Strategic responses to algorithmic decision-making There is a growing line of work at the inter- section of economics and computation algorithmic docision-making with incentives, under the umbrella of strategic classification or strategic learning [27, 3, 41, 22] focusing on online learning settings [21, 19], causal learning [52, 31, 29, 34], incentivizing desirable behavior [39, 28, 11, 42], incomplete information [30, 25, 37]. In its most basic form, a principal makes either a binary or real-valued prediction about strategic agent, and receives full feedback (e.g., the agent's 's label) after the decision is made. While this setting is similar to ours, it crucially ignores the one-sided feedback structure present in many strategic settings of interest. In our running example of hiring, full feedback would correspond to company not offering an applicant a job, and yet still getting to observe whether they would have been a good employee! As result, such methods are not applicable in our setting. Concurrent work [18] studies the effects of bandit feedback in the related problem of performative prediction [47], which considers data distribution shifts at the population level in response to the deployment of machine learning model. In contrast, our focus is on strategic responses to machine
We relax this assumption later parts of the paper with virtually no impact on results.

---

learning models at the individual level under apple tasting and bandit feedback. Ahmadi et al. [4] study an online strategic learning problem in which they consider "bandit feedback" with respect to the deployed classifier. In contrast, we use the term "bandit feedback" to refer to the fact that we only see the outcome when for the action/decision taken.
Apple tasting and online learning Helmbold et al. [32] introduce the notion of apple-tasting feedback for online learning. In particular, they study a binary prediction task over "instances" (e.g., fresh/rotten apples), in which a positive prediction is interpreted as accepting the instance (i.e. "tasting the apple") and a negative prediction is interpreted as rejecting the instance (i.e., not tasting the apple). The learner only gets feedback when the instance is accepted (i.e., the apple is tasted). While we the first to consider classification under incentives with apple tasting feedback, similar feedback models have been studied in the context of algorithmic faimess [9]. martial-montorring games [5], and recidivism prediction [24]. A related model of feedback is that of contaminated controls [40], which considers learning from (1) a treated group which contains only treated members of the agent population and (2) a "contaminated" control group with samples from the entire agent population (not just those under control). Technically, our results are also related to a line of work in contextual bandits which shows that greedy algorithms without explicit exploration can achieve sublinear regret as long as the underlying context distribution is sufficiently diverse [49, 8, 38, 53, 48).
Bandits and agents A complementary line of work to ours is that of Bayesian nncentive-comparti (BIC) exploration in multi-armed bandit problems [43, 35, 50, 36, 44, 45]. Under such settings, the goal of the principal is to persuade a sequence of T agents with incentives to explore across several different actions with bandit feedback. contrast, in our setting it the principal, not the agents, who is the one taking actions with partial feedback. As result there is no need for persuasion, but the agents now have an incentive to strategically modify their behavior in order to receive a more desirable decision/action.
Other related work Finally, our work is broadly related to the literature learning in repeated Stackelberg games [7. 55), online Bayesian persuasion [16, 17, 13), and online learning in principal- agent problems [20, 33, 56). In the repeated Stackelberg game setting, the principal (leader) commits to a mixed strategy over a finite set of actions, and the agent (follower) best-responds by playing an action from a finite set of best-responses. Unlike in our setting, both the principal's 's and agent's payoffs can be represented by matrices. In contrast, in our setting the principal commits to a pure strategy from continuous set of actions, and the agent best-responds by playing an action from continuous set. In online Bayesian persuasion, the principal (sender) commits to a "signaling policy" (a random mapping from "states of the world" to receiver actions) and the agent (receiver) performs posterior update on the state based on the principal's 's signal, then takes an action from (usually finite) set. In both this setting and ours, the principal's 's action a policy. However in our setting the policy is linear decision rule, whereas in the Bayesian persuasion setting, the policy is a set of conditional probabilities which form an "incentive compatible" signaling policy. This difference in the policy space for the principal typically leads to different algorithmic ideas being used in the two settings. Strategic learning problems are, broadly speaking, instances of -aggett problems. In contract design, the principal commits to a contract (a mapping from "outcomes" to agent payoffs). The agent then takes an action, which affects the outcome. In particular, they take the action which maximizes their expected payoff, subject to some cost of taking the action. The goal of the principal is to design a contract such that their own expected payoff is maximized. While the settings are indeed similar, there are several key differences. First, in online contract design the principal always observes the outcome, whereas in our setting the principal only observes the reward if a positive decision is made. Second, the form of the agent's 's best response is different, which leads to different agent behavior and, as a result, different online algorithms for the principal.
2 Setting and background
We consider game between principal and sequence of T agents. Each agent is associated with a context x, E X' C TRd, which characterizes their attributes (e.g., a loan applicant's credit history/reportt. At time f, the principal commits to a policy ne X + 0). which maps from contexts to binary decisions (e.g., whether to accept/reject the loan application). We use a; = 1 to denote the the principal's positive decision at round č (e.g., agent f's loan application is approved), and 0 to denote a negative decision (e.g., the loan application is rejected). Given ne, agent t best-responds by strategically modifying their context within their effort budget as follows:
3

---

Definition 2.1 (Agent best response; lazy tiebreaking). Agent t best-responds to policy ne by modifying their context according to the following optimization program.
X E aag max x'EX 1 1xx((x)== =1 =
s.t. xx'l2 8
Furthermore, we assume that if an agent is indifferent between two (modified) contexts, they choose the one which requires the least amount of effort to obtain (i.e., agents are lazy when tiebreaking).
In other words, every agent wants to receive a positive decision, but has only limited ability to modify their (initial) context (represented by Eg budget 6).2 Such an effort budget may be induced by time or monetary constraints and is a ubiquitous model of agent behavior in the strategic learning literature (e.g.. [39, 28, 19, 10J. We focus on linear thresholding policies where the principal assigns action (xx) = 1. if and only if (B,x') 2 for some 3 E IR,, E RR We refer to (B, x²) = as the decision boundary. For linear thresholding policies, the agent's best-response according to Definition 2.1 is to modify their context in the direction of /3/1|/112 until the decision-boundary reached (if can indeed be reached). While we present our results for lazy liebreaking for ease of exposition, all of our results can be readily extended to the setting in which agents best-respond with a "trembling hand", i.e. trembling hand tiebreaking. Under this setting, we allow agents who strategically modify their contexts to "overshoot" the decision boundary by some bounded amount, which can be either stochastic or adversarially-chosen. See Appendix D for more details.
The principal observes x and plays action Te according to policy Tr. If 0z 0. the principal receives some known, constant reward (0) == ro E R. On the other hand, if the principal assigns action de 1, we assume that the reward the principal receives is linear in the agent's s unmodified context, i.c.,
ri(1) := (00)) +
for some unknown g(1) E R.d, where e, is i.i.d. zero-mean sub-Gaussian random noise with (known) variance g². Note that (1) is observed only when the principal assigns action a, = 1, and not when a, = O. Following Helmbold et al. [32], we refer to such feedback as apple tasting (or one-sided) feedback. Mapping to our lending example, the reward bank receives for rejecting a particular loan applicant is the same across all applicants, whereas their reward for a positive decision could be anywhere between a large. negative reward (e.g.. if a loan never repaid) to a large, positive reward (e.g., if the loan is repaid on time, with interest).
The most natural measure of performance in our setting that of Stackelberg regret, which compares the principal's 's reward over T rounds with that of the optimal policy given that agents strategize.
Definition 2.2 (Stackelberg regret). The Stackelberg regret of a sequence of policies {Tehett on agents {x, he(r) is
Regstackel (T)
Σ re (x,)) KE(T)
Σ (x(()((x))
LE(T))
where X, is the best-response from agent L policy #* and n" is the aptimal-in-hindsiiee policy, given that agents best-respond according to Definition 2.1.
A stronger measure of performance is that of strategic regret, which compares the principal's 's reward over T rounds with that of the optimal policy had agents reported their contexts truthfully.
Definition 2.3 (Strategic regret). The strategic regret of sequence of policies (meheerr agents {xthem is
Regstrat (T) Σ rx(TT((x)))
Σ (x(((()))
tE[T]
KE(T]
where x² xxxx)) = if (0(1), xx) 2 ro and ":" (xx) 0 otherwise.
Ourr results readily extend to the setting in which the agent's is effort constraint takes the form of an ellipse rather than a sphere. Under this setting, the agent effort budget constraint in Definition 2.1 would be 1|4'/(xx x.)l|2 < 8, where A E dddx is some positive definite matrix. If A is known to the principal, this may just be viewed linear change in the feature representation.

---

Classification under agent incentives with apple tasting feedback
For 1, 1...., T:
1. Principal publicly commits to a mapping Te : X + {1,0}.
2. Agent arrives with context x; E X (hidden from the principal).
3. Agent & strategically modifies context from X, to x according to Definition 2.1.
4. Principal observes (modified) context x and plays action ar (x()..
5. Principal observes rr(1) = (0()) xx) + Ec, if and only if az =
Figure 1: Summary of our model.
Proposition 2.4. Strategic regret is a stronger performance notion compared to Stackelberg regret, i.e, Regstackel (T) S Regstrat (T).
Proof. The proof follows from the corresponding regret definitions and the fact that the principal's reward is determined by the original (unmodified) agent contexts.
Rstackel (T) = Σ
re (xx))
Σ (x()) 1E
AE/T
Σ re (x()) - Σ
re( (x:)) + Σ (x())(())) - Σ re(TT((())
1E(T]
LE|T
EE(T]
1E[T]
20 + (T)
where the last line follows from the fact that the principal's 's reward from the optimal policy when the agent strategizes is at most their optimal reward when agents do not strategize.
Because of Proposition 2.4, we focus on strategic regret, and use the shorthand Regstras (T) RTg(T) for the remainder of the paper. Strategic regret is strong notion of optimality, comparing the principal's ' performance with that of the optimal policy for an easier setting, in which agents do not strategize. Moreover, the apple tasting feedback introduces additional challenges which require new algorithmic ideas to solve, since the principal needs to assign actions to both (1) learn about ((1) (which can only be done when action is assigned) and (2) maximize rewards in order to achieve sublinear strategic regret. See Figure I for a summary of the setting we consider.
We conclude this section by pointing out that our results also apply to the more challenging setting of bandit feedback, in which r1) is defined as in Equation (1), rr (0) := (o(0) x₂) + e, and only re (at) is observed at each time-step. We choose to highlight our results for apple tasting feedback
since this is the type of feedback received by the principal in our motivating examples. Finally, we
note that (-) hides polylogarithmic factors, and that all proofs can be found in the Appendix.
Strategic classification with apple tasting feedback
In this section, we present our main results: provable guarantees for online classification of strategic agents under apple tasting feedback. Our results rely on the following assumption.
Assumption 3.1 (Bounded density ratio). Let fue X - Rz0 denote the density function of the uniform distribution over the d-dimensional unit sphere. We assume that agent contexts {xt heerr are drawn i.idd from a distribution over the d-dimensional unit sphere with density function X + Rgo such that f(x) (x) 2 > 0, Vx E X.
Assumption 3.1 is condition on the initial agent contexts (xtherr) before they are strategically modified. Indeed, one would expect the distribution over modified agent contexts to be highly discon- tinuous in a way that depends on the sequence of policies deployed by the principal. Furthermore, none of our algorithms need to know the value of co. As we will see in the sequel, this assumption allows us to handle apple tasting feedback by relying on the inherent diversity the agent population
Our restriction to the wnit sphere is without loss of generality. All of our results and analysis extend readily the setting where contexts are drawn from distribution the d-dimensional sphere with radius R 0.
5

---

ALGORITHM I: Strategy- OLS with Apple Tasting Feedback (SA-014) OLS)
Assign action for the first d rounds.
Set D4+1 = {(x., 12 (1)))
)===1
for 1= = d + I..... T do
Estimate (()) as 0. (1)
using OLS and data De.
Assign action oe 1f (0, xx) 2 8- 100 (1)
1a + ro.
if (1) xi) > 8110; ||2 + ro then
Conclude that x = Xx.
D4t1 Dj {(x,, ))
else Di+1 = D.
for exploration; a growing area of interest in the online learning literature (see references in Sec- tion 1.2). Moreover, such assumptions often hold in practice. For example, in the related problem of (non-strategic) contextual bandits (we will later show how our results extend to the strategic version of this problem), Bietti et al. [14] find that a greedy algorithm with no explicit exploration achieved the second- empirical performance across a large number of datasets when compared to many popular contextual bandit algorithms. In our settings of interest (e.g. lending, hiring), such an assumption is reasonable if there is sufficient diversity in the applicant pool. In Section 4 we show how to remove this assumption, albeit at the cost of worse regret rates and exponential computational complexity.
At high level, our algorithm (formally stated in Algorithm 1) relies on three key ingredients to achieve sublinear strategic regret:
1. A running estimate of (1)) is used to compute a linear policy, which separates agents who receive action from those who receive action 0. Before deploying. we shift the decision boundary by the effort budget 8 to account for the agents strategizing.
2. We maintain an estimate of (()) (denoted by ( and only updating it when a = 1 and we can ensure that x =
=,, X,.
3. We assign actions "greedily" (i.e. using no explicit exploration) w.r.t. the shifted linear policy.
(1) Shifted linear policy If agents were not strategic, assigning action 1 if (0, xx)) 2 ro and action (1) otherwise would be a reasonable strategy to deploy, given that 0, is our "best estimate" of ( so far. Recall that the strategically modified context x² is s.t., ||x| x, S 8. Hence, in Algorithm 1,
shift the linear policy by 81.0 (1)
ll2 to account for strategically modified contexts. Now, action
1 is only assigned if (0, xx) 2 5110 ll2 + ro. This serves two purposes: (1) It makes it so that
(1)
any agent with unmodified context x such that (0, x) < Tu cannot receive action 1, no matter how
they strategize. (2) It forces some agents with contexts in the band To S (0) x) < 6l|ō" |l2 +ro to strategize in order to receive action 1. Estimating
(1) After playing action for the first d rounds, Algorithm forms an initial estimate of e via ordinary least squares (OLS). Note that since the first d agents will receive action 1 regardless of their context, they have no incentive to modify and thus x = for f < dd In future rounds, the algorithm's 's estimate of (1) is only updated whenever x lies strictly on the positive side of the linear decision boundary. We call these contexts clean, and can infer that x = x, due to the lazy tiebreaking assumption in Definition 2.1 (i.e. agents will not strategize more than is necessary to receive the positive classification).
Condition 3.2 (Sufficient condition for x' x). Given a shifted linear policy parameterized by (3(1) E IRd, we say that context x' is clean if (1(1) x') 61)3("))12 To-
Greedy action assignment By assigning actions greedily according to the current (shifted) linear policy, we are relying on the diversity in the agent population for implicit exploration (i.e., to collect more datapoints to update our estimate of ((1)). As we will show, this implicit exploration

---

is sufficient to achieve Ö(VT) strategic regret under Assumption 3.1, albeit at the cost of an exponentially-laree (in d) constant which depends on the agents' ability to manipulate (6).
We are now ready to present our main result: strategic regret guarantees for Algorithm 1 under apple tasting feedback.
Theorem 3.3 (Informal: detailed version in Theorem B.1). With probability 1 % Algorithm I achieves the following performance guarantee:
Reg(T) S δ ( (
co c1 (2) V do logTloogAA1)) (7)
where co is a lower bound on the density ratio as defined in Assumption 3.1, ci 6) =
P x- [x[]] z 8) 2 θ (1-87412) for sufficiently large d and c2(d, 6) = Ex~ud [x[2]*|x[1] 2
1 } where x[i] denotes the i-th coordinate of vector x
Proof sketch. Our analysis begins by using properties of the strategic agents and shifted linear deci- sion boundary upper-bound the per-round strategic regret for rounds >> d by term proportional
to 0 e 12, i.e., our instantaneous estimation error for (()) Next we show that
| x.C. x.
10
Amin Et xxx 1
where Amin (M) is the minimum eigenvalue of (symmetric) matrix M, and I!!1 5 5100 (1)
110 xx) >
[2 + ro is the event that Algorithm 1 assigns action a, 1 and verify that x, = x,, We upper-bound the numerator using a variant of Azuma's inequality for martingales with subgaussian tails. Next, we use properties of Hermitian matrices to show that Amin (E X,X_ (I! 2) is lower-bounded by two terms: one which may be bounded w.h.p. by using the extension of Azuma's
inequality for matrices, and one of the form =s Amin (E,-1 1 (I!") H),, where E.-1 denotes the expected value conditioned on the filtration up to time s. Note that up until this point, we have only used the fact that contexts are drawn i.i.d. from bounded distribution.
Using Assumption 3.1 on the bounded density ratio, we can lower bound Amin (x,_ by Amin tribution over the d-dimensional ball. We then use properties of the uniform distribution show that Amina (E 1 1 2 O(co c(d, 6)). Putting everything together, we get that 10 (1)
(I("))), where the expectation is taken with respect to the uniform dis-
(1)) 11 S (co o) vt)-1 with high probability. Via union bound and the fact that EierTy vi I 2T, we get that Reg(T) < ( VT). Finally, we use tools from high- dimensional geometry to lower bound the volume of spherical cap and we show that for sufficiently large d, e1 (d, 8) 2 (1-5)//2
3.1 High-dimension contexts
While we typically think of the number of agents T as growing and the context dimension d as constant in our applications of interest, there may be situations in which T is either unknown small. Under such settings, the 1/o(d.6) dependence in the regret bound (where c(d, 8) = ei (d, 8) c2 5)) may become problematic if 5 is close 1. This begs the question: "Why restrict the OLS estimator in Algorithm to use only clean contexts (as defined in Condition 3.2)?" Perhaps unsurprisingly,
we show in Appendix B that the estimate σ()) given by OLS will be inconsistent if even a constant fraction of agents strategically modify their contexts.
"While we assume that 8 is known to the principal, Algorithm is fairly robust to overestimates of 6, in the sense that (1) it will still produce a consistent estimate for (c) (albeit at a rate which depends on the over- estimate instead of the actual value of 8) and (2) it will incur constant penalty in regret which is proportional to the amount of estimationn.
7

---

ALGORITHM 2: Explore-Then Then Chen-C
Time horizon T, failure probability Set To according to Theorem B.9 Assign action for the first To rounds
Input:
Estimate ( as 0T, via OLS for f = To + 1,..., T do
Assign action a, 1 if (OTo xx) 2 20. 10%%l la and action a, 0 otherwise
20.100%
Given the above, it seems reasonable to restrict ourselves to learning procedures which only use data from agents for which the principal can be sure that x' = x. Under such a restriction, is natural to ask whether there exists some sequence of linear polices which maximizes the number of points of the form (x,, Tr (1)) for which the principal can be sure that x = X,. Again, the answer is no:
Proposition 3.4. For any sequence of linear policies {Be)s, the expected number of clean points is:
E X
Σ
1xxx,,,,) 011,81112) (d,
LE|2
when (initial) contexts are drawn uniformly from the d-dimensional unit sphere.
The proof follows from the rotational invariance of the uniform distribution over the unit sphere. Intuitively, Proposition 3.4 implies that any algorithm which wishes to learn ((1) using clean samples will only have ea (d, 5) T datapoints in expectation. Observe that this dependence on (d, 5) arises as direct result of the agents' ability to strategize. We remark that similar constant often appears in the regret analysis of BIC bandit algorithms (see Section 1.2). Much like our work, [43] find that their regret rates depend on a constant which may be arbitrarily large, depending on how hard is to persuade agents to take the principal's 's desired action in their setting. The authors conjecture that this dependence is an inevitable "price of conettve-comppaiiiitty".. While our results do not rule out better strategic regret rates in d for more complicated algorithms (e.g., those which deploy non-linear policies), it is often unclear how strategic agents would behave in such settings, both in theory (Def- inition 2.1 would require agents solve non-convex optimization with potentially closed-fone solution) and in practice, making the analysis such nonlinear policies difficult in strategic settings.
We conclude this section by showing that polynomial dependence on d possible, at the cost of Ø(T2/3) strategic regret. Specifically, we provide an algorithm (Algorithm 3) which obtains the following regret guarantee whenever 7' is small unknown, which uses Algorithm and variant of the explore-then-comiit algorithm (A (Algorithm 2) as subroutines:
Theorem 3.5 (Informal; details in Theorem B.13). Algorithmm incurs expected strategic regret
(1- VI,d VT.d- VT.d-Tres)).
d/2
[[Reg(T)) = min
where the expectation is taken with respect to the sequence of contexts {xt]ue(r) and random noise {c) (G))e(()-
The algorithm proceeds by playing "strategy-aware" variant of explore-then-comiit (Algorithm 2) with doubling trick until the switching time -* g(d, 5)) is reached. Note that g(d, 8) is function of both d and 8, not cp. If round r" is indeed reached, the algorithm switches over to Algorithm I for the remaining rounds.
Extension to bandit feedback Algorithm 1 can be extended to handle bandit feedback by explicitly (1)
keeping track of estimate 0% (0) of (0)) via OLS, assigning action or if and only if (0,
1|,, and updating the OLS estimate (0) whenever a, = (since agents will not strategize to receive action 0). Algorithm 3 may be extended to bandit feedback by "exploring"
(0) x 2 8 110, (1) (())
for twice as long in Algorithm 2, in addition using the above modifications. both cases, the
strategic regret rates are within constant factor of the rates obtained in Theorem 3.3 and Theorem 3.5.

---

ALGORITHM 3: Strategy- online classification with unknown time horizon Compute switching time r' = =((d8)
Let 7o
for = 1, 3, ... do
Let 2-
if [ د= Tj < then
Run Algorithm 2 with time horizon T; and failure probability 1/T?
clse
Break and run Algorithm for the remainder of the rounds
4 Beyond stochastic contexts
In this section, we allow the sequence of initial agent contexts to be chosen by an (oblivious) adversary. This requires new algorithmic ideas, the regression- algorithms of Section 3 suffer linear strategic regret under this adversarial setting. Our algorithm (Algorithm 4) is based on the popular EXP3 algorithm [6]. At high level, Algorithm 4 maintains a probability distribution over "experts" ie., a discretized grid & over carefully-selectee policies. In partieular, each grid point e E E S Rd represents an "estimate" of ( and corresponds to slope vector which parameterizes a (shifted) linear threshold policy, like the ones considered in Section 3. We use at,e to refer to the action played by the principal at time f. had they used the linear threshold policy parameterized by expert e. At every time-step. (1) the adversary chooses an agent X,, (2) slope vector C₁ E & selected according to the current distribution, (3) the principal commits to assigning action 1 if and only if (c),x) 2 8||eylla (4) the agent strategically modifies their context x; + X,, and (5) the principal assigns an action at according to the policy and receives the associated reward (a())) (under apple tasting feedback).
Algorithm EXP4, which maintains distribution over experts and updates the loss of all experts based on the current action taken, is not directly applicable in our setting as the strategic behavior of the agents prevents us from inferring the loss of cach expert at every time-step [ J. This is because if x o X₁ under the thresholding policy associated with expert e), it is generally not possible to "back out" x given x", which prevents us from predicting the counterfactual context the agent would have modified to had the principal been using expert e' instead. As result, we use modification of the standard importance- importance-weighted loss estimator update the loss of only the policy played by the algorithm (and therefore the distribution over policies). Our regret guarantees for Algorithm 4 are follows:
Theorem 4.1 (Informal: detailed version in Theorem C.1). Algorithm 4 incurs expected strategic regret E (Reg(T)) = (TT(+))/((++)).
We remark that Algorithm 4 may be extended to handle settings in which agents are selected by an adaptive adversary by using EXP3.P [6] in place of EXP3.
Proof sketch. The analysis is broken down into two parts. In the first part, we bound the regret w.r.t. the best policy on the grid. In the second, we bound the error incurred for playing policies on the grid, rather than the continuous space of policies. We refer to this error as the Strategic Discretization Error (T)). The analysis of the regret on the grid mostly follows similar steps to the analysis of EXP3 / EXP4. The important difference is that we shift the reward obtained by at, by a factor of 1 + X, where is a (tunable) parameter of the algorithm. This shifting (which does not affect the regret, since all the losses are shifted by the same fixed amount) guarantees that the losses at each round are non-negative and bounded with high probability. Technically, this requires bounding the tails of the subgaussian of the noise parameters éx-
We now shift our attention to bounding SDE(T). The standard analysis of the discretization error in the non-strategic setting does not go through for our setting, since an agent may strategize very differently with respect to two policies which are "close together" in lg distance, depending on the agent's 's initial context. Our analysis proceeds with a case- case-by-case by-case basis. Consider the best expert e* in the grid. If at.e- = TT'xx (xx) (i.e., the action of the best expert matches that of the optimal policy), there is no discretization error in round t. Otherwise, if or.e- * TT' (xx), we show that the per-round SDE is upper-bounded by a term which looks like twice the discretization upper-bound for the non-strategic setting, plus an additional term. We show that this additional term must always be
non-positive by considering two subcases (at,e- = 1, x (x+)) = and (r..." = 0, n =x(x)) = 1) and using properties about how agents strategize against the deployed algorithmic policies.
9

---

ALGORITHM 4: EXP3 with strategy aware experts (EXP3-SAE)
Create set of discretized policies e E [[1/e))]. where (do log (T) 2n> and À = o22log..
Set parameters 77 T Y [
Initialize probability distribution (r(e) 1/ 1/ ve E.
for E [T]
Choose policy e, from probability distribution (e(e) = (1 - 7) pi(e) + TØ1
Observe X1.
Play action er,e, if (e,, xi) 2 81|e,|12. Otherwise play action dt,e, = 0.
Observe reward ra e:
Update loss estimator for each policy E: (e) = A1+ re(ac.o))) 11++-r((aeor))) 1lfe e.)/)(())
Update probability distribution E E: (e) x pe (e(e) exp (e)):(e))
Computational complexity While both Algorithm and Algorithm 3 have (dd)) per-iteration computational complexity, Algorithm 4 must maintain and update a probability distribution over a grid of size exponential in d at every time-step, making it hard to use in practice if d is large. We view the design of computationally efficient algorithms for adversarially-ccosen contexts as an important direction for future research.
Extension to bandit feedback Algorithm 4 may be extended to the bandit feedback setting by maintaining a grid over estimates of (q)) (instead of over ()))), No further changes are required.
Conclusion
We study the problem of classification under incentives with apple tasting feedback. Such one-sided feedback is often what is observed in real-world strategic settings including lending and hiring. Our main result is "greedy" algorithm (Algorithm 1) which achieves Ö(VT) strategic regret when the initial agent contexts are generated stochastically. The regret of Algorithm depends on a constant ea (d, which scales exponentially in the context dimension, which may be problematic in settings for which the number of agents is small or unknown. To address this, we provide an algorithm (Algorithm 3) which combines Algorithm with strategy-aware version of the explore-then-commii vøT algorithm using a doubling trick to achieve O(min er d T2/33) expected strategic regret whenever T is unknown. Finally, we relax the assumption of stochastic contexts and allow for contexts to be generated adversarially. Algorithm achieves Ö(T क expected strategic regret whenever agent contexts are generated adversarially by running EXP3 over discretized grid of strategy-awarr aware policies, but has exponential-ing per-round computational complexity. All of our results also apply to the more general setting of bandit feedback, under slight modifications to the algorithms. There are several directions for future work:
Unelean data The regret of Algorithm depends on constant which is exponentially large in d, due to the fact that it only learns using clean data (Condition 3.2). While learning using unclean data will generally produce an inconsistent estimator. it would be interesting to see if the principal could leverage this data to remove the dependence on this constant. Alternatively, lower bounds which show that using unclean data will not improve regret would also be interesting.
Efficient algorithms for adversarial contexts Our algorithm for adversarially-chosse agent contexts suffers exponential-in- per-round computational complexity, which makes it unsuitable for use in settings with high-dimensional contexts. Deriving polynomial-time algorithms with sublinear strategic regret for this setting is an exciting (but challenging) direction for future research.
More than two actions Finally, it would be interesting to extend our algorithms for strategic learning under bandit feedback to the setting in which the principal has three or more actions at their disposal. While prior work [29] implies an impossibility result for strategic regret minimization with three or more actions, other (relaxed) notions of optimality (e.g., sublinear Stackelberg regret; recall Definition 2.2) may still be possible.
10

---

Acknowledgements
KH is supported in part by an NDSEG Fellowship. KH and ZSW are supported in part by the NSF FAI Award #1939606. For part of this work, CP was supported by FODSI postdoctoral fellowship from UC Berkeley. The authors would like to thank the anonymous NeurIPS reviewers for valuable feedback.
References
[1] Algorithmic hiring: Complex hiring by numbers? URL httts://hiringg monster com/ resources/recruitiin wtw.tnggstttttssss/eee wtw.aaeeeeeeeooooooeeeeeeeeeeeae wwo.torreeplanniiighhhiiigggggg- thmmrtthss
[2] Using white font on a ev to trick ats. URL https: thecvstoreeeeeeeeeeeeee nwt. wv-ats-ubitte-oot/// http::/:....aa.aaaooo/ooo/0000/0 http://p0prrrapll.0paaamma/aa/mr ofturuuee/2eeeppyyyyooo//pppppee
[3] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Compulation, pages 6-25, 2021.
[4] Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds on online strategic classifi- cation. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 22-58. ACM, 2023.
[5] András Antos, Gábor Bartók, Dávid Pál, and Csaba Szepesvári. Toward classification of finite partial-monitoring games. Theoretical Computer Science, 473:77-99, 2013.
[6] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002
[7] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelherg security games. In Proceedings of the sixteenth
ACM conference on economics and computation, pages 61-78. 2015.
[8] Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free -free algorithms for contextual bandits. Management Science, (333)1332-1144 2021. doi: 20.1227/mss.22020. 3605. URL https:tt//// orgg://o..roo////// 1287 mwsc. 2020 3605.
[9] Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, and Steven Wu. Equal opportu- nity in online classification with partial feedback. Advances in Neural Information Processing Systems, 32, 2019.
[10] Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234-1242. PMLR, 2021.
[11] Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning, pages 1691-1715. PMLR, 2022.
[12] Jillian Berman. Do ai-powered lending algorithms silently discriminate? this ini- tiative aims to find out, Nov 2021. URL https: do- Seaa--pooerrd--eednn---llggeee wtw.agorwtton--eelleee-----ee-ee -aims fottttoo-ioouuut----ooooooo -1-377724511133
com/story/ http///wwww.aakketattccc...c https://www.narreetwatdd
[13] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In International Conference on Machine Learning, pages 2164-2183. PMLR, 2023.
[14] Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. The Journal of Machine Learning Research, 22(1):5928-599 2021.
[15] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Cambridge University Press, 2020.

---

[16] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian persua- sion. Advances in Neural Information Processing Systems. 33:16188-16198, 2020.
[17] Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online bayesian persuasion. In International Conference on Machine Learning, pages 1314-1323.
PMLR, 2021.
[18] Yatong Chen, Wei Tang, Chien-Ju Ho, and Yang Liu. Performative prediction with bandit feedback: Learning through reparameterization. arXiv preprint arXiv:2305.01094, 2023.
[19] Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Ad- vances in Neural Information Processing Systems, 33:15265-15276, 2020.
[20] Vincent Conitzer and Nikesh Garera. Learning algorithms for online principal-agent problems (and selling goods online). In Proceedings of the 23rd international conference on Machine learning, pages 209-216, 2006.
[21] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 55-70, 2018.
[22] Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks. arXiv preprint 2.kiv:2205.15765. 2022.
[23] Christian Eilers. Resume keywords: List by industry [for use to pass the ats), Jan 2023. URL
https://zets wwt./ttt.coo/bbaa www/blog///cooooocccccoccc.ooooo -
[24] Danielle Ensign, Sorelle A Friedler, Scott Nevile, Carlos Scheidegger, and Suresh Venkatasub- ramanian. Decision making with limited feedback: Error bounds for predictive policing and recidivism prediction. In Proceedings of Algorithmic Learning Theory, volume 83, 2018.
[25] Ganesh Ghalme, Vineet Nair, Itay Filat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In International Conference Machine Learning, pages 3672-3681.
PMLR, 2021.
[26] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 917-918, 2022.
[27] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016.
[28] Keegan Harris, Hoda Heidari, and Steven Z Wu. Stateful strategic regression. Advances in Neural Information Processing Systems, 34:28728-28741 2021.
[29] Keegan Harris, Anish Agarwal, Chara Podimata, and Zhiwei Steven Wu. Strategyproof decision- making in panel data settings and beyond. arXiv preprint arXiv:2211.142:: 2022.
[30] Keegan Harris, Valerie Chen, Joon Kim, Ameet Talwalkar, Hoda Heidari, and Steven Wu. Bayesian persuasion for algorithmic recourse. Advances in Neural Information Processing Systems, 35:1 13111111-11144, 2022.
[31] Keegan Harris, Dung Daniel Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In International Conference on Machine Learning, pages $502-8522. PMLR, 2022.
[32] David P Helmbold, Nicholas Littlestone, and Philip M Long. Apple tasting. Information and Computation, 161(2)855-19, 2000.
[33] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 359-376.
2014.
12

---

[34] Guy Horowitz and Nir Rosenfeld. Causal strategic classification: A tale of two shifts. In International Conference on Machine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 13233-13253. PMLR, 2023.
[35] Xinyan Hu, Dung Ngo, Aleksandrs Slivkins, and Steven Wu. Incentivizing combinatorial bandit exploration. Advances in Neural Information Processing Systems, 35:37173-371833 2022.
[36] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Bayesian exploration with heterogeneous agents. In The world wide web conference, pages 751-761, 2019.
[37] Meena Jagadcesan, Celestine Mendler-Dünner, and Moritz Hardt. Alternative microfoundations for strategic classification. In International Conference on Machine Learning, pages 4687-4697, PMLR, 2021.
[38] Sampath Kannan, Jamie Morgenstem, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2018. Curran Associates Inc.
NIPS' 18, page
[39] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategi- cally? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
[40] Tony Lancaster and Guido Imbens. Case-control studies with contaminated controls. Journal of Econometrics, 71(1-2):145-166) 1996.
[41] Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In International Conference on Machine Learning, pages 6243 62533. PMLR, 2021.
[42] Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incentives. In International Conference Machine Learning, pages 12593-12618. PMLR, 2022.
[43] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatible bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 565-582, 2015.
[44] Daniel Ngo, Logan Stapleton, Vasilis Syrgkanis, and Zhiwei Steven Wu. Incentivizing bandit exploration: Recommendations as instruments. In Proceedings of the 2021 International Conference on Machine Learning (ICML'21), 2021.
[45] Daniel Ngo, Keegan Harris, Anish Agarwal, Vasilis Syrgkanis, and Zhiwei Steven Wu. Incentive- aware synthetic control: Accurate counterfactual estimation via incentivized exploration. 2023. URL /top:://///egaaaarriiess github. io/IE_SC IE_SC.pde pdf.
[46] Bev O'Shea. 9 ways to build and improve your credit fast, Nov 2022. URL attps://wwe nerdwallet com/ arrticlef wwweeefiinnce/eeeeeeeeee wawnnceerraieeeeeeeeeeeee ceeeeerreeittttee score-scooeeeeee fast.
[47] Juan Perdomo, Tijana Zmnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020.
[48] Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. The externalities of exploration and how data diversity helps exploitation. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1724-1738. PMLR, 2018. URL. http: http:///rooeedn....... mlr. wtwpiiinsn.......ssseeeeeeeeeeee press/v75 raghavan18a. html.
[49] Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal Comput- ing, 52(2):487-524 2023. doi: 10. 10.113779M12247115 URL https://doi. .or./orrg0.. 10. 1137/ 19M1247115.
13

---

[50] Mark Sellke and Aleksandrs Slivkins. The price of incentivizing exploration: A characterization via thompson sampling and sample complexity. Proceedings of the 22nd ACM Conference oi Economics and Computation, pages 795-796, 2021.
[51] Ohad Shamir. A variant of azuma's inequality for martingales with subgaussian tails. arXiv preprint 1rxiv:1110.2392, 2011.
[52] Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference Machine Learning, pages 8676-8686. PMLR, 2020.
[53] Vidyashankar Sivakumar, Zhiwei Steven Wu, and Arindam Banerjee. Structured linear con- textual bandits: A sharp and geometric smoothed analysis. In Proceedings of the 37th Interna- tional Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 9026-9033 PMLR, 2020. URL http:/ htttp://prrocedings.. mlr. wttpps/eeeeesieieeeeeteeeeeseees wtw.1///raiaaaaaaa.a....mm html.
[54] Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computa- tional mathematics, 12:389-434, 2012.
[55] Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackelberg games with an omniscient follower. In International Conference on Machine Learning, pages 42304 6.. PMLR, 2023.
[56] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page
1 188. ACM, 2023.
14

---

A Useful concentration inequalities
Theorem A.1 (Matrix Azuma, Tropp [54]). Consider a self-adjoint matrix martingale (Y, = ,.) in dimension d, and let (Xs)sett) be the associated difference sequence satisfy- ing - X, Oaxd and X² 3 A for some fixed sequence (Es) of self-adjoint matrices. Then for all a > 0,
P (Amaz (Y, EY) 2 a) d exppxp(=a2 /800)))
where o² = - A2
Theorem A.2 (A variant of Azuma's inequality for martingales with subgaussian tails, Shamir [51]). Let Z1, Z2....... Ze be martingale difference sequence with respect to a sequence W,. W,,..., W. and suppose there are constants > 1, c > 0 such that for any and any O, it holds that
max ( (Z, a o|X1,.....
(,,1),P(Z,, < _x, X.-1)} S cxp()caa))
Then for any Y > O, it holds with probability - y that
28b log (1/7)
Σ 2. S 8=1
eT
B Proofs for Section 3
B.1 Proof of Theorem 3.3
Theorem B.1. Let Sua X -+ RR20 denote the density function of the uniform distribution over the d-dimensional unit sphere. agent contexts are drawn from a distribution over the d-dimensional unit
sphere with density function f f X - Rzo such that f(x) 2 co
> O, Vx E X, then Algorithm I
Tea(x)
achieves the following performance guarantee:
Reg(T) S 4d +
co (6, c2(6, d) logodT)
with probability % where 0 (6, [x]ua(((1] Ex [x x[1] 2 6).
8) and 0 c2(6,
Proof. We start from the definition of strategic regret. Note that under apple tasting feedback, (())= 0.
Reg(T) =
(lai) ((ax) -0(a))x))
0 (0)) (/0)) .xx) (0
-0(1)) ,xx -0(0))
(0) - xx
(0())
0.0 xxx + < 0 (v) 0, x1
Σ
|0000
||x1||2
(0))
0
(0)
||x:|] l|
T
S 2d
+
Σ
0200
+
10) 0
0001
2=24+1
where the first inequality follows from Lemma B.2, the second inequality follows from the Cauchy- Schwarz, and the third inequality follows from the fact that the instantaneous regret at each time-step most 2 and we use the first d rounds bootstrap our OLS. The result follows by Lemma B.3, union bound, and the fact that ΣJ V < 2VT..
Lemma B.2.
(0
0 (as) xx) S
15

---

Proof. If 0, = di, the condition is satisfied trivially. If a, # az. then either (1) (0,
0 x()
(0)
5 610 (1)
0, 1l2 2 0 and (0(1) - ) < or (2) O ) 02 xx) 6 -600,
(0)
(0)
(2)
(0)
0. 1l2 0 and
(0()) 0 2 0.
Case 1: (0.") 0 x 8110 (1)
0. 0
112 2 0 and (0 ) 0. (aj 0. a = 1)
By Definition 2.1, we can rewrite
0 0, xx) 010, 0, 1|2 00
0 (1) (0)
0, x1) + (8' - - (1) (0)
0, 12 2 0
for some 8' S Since (8' 8)| 0, 0, 122 S 0, (0 (1)
0, x1) 2 must hold.
Case 2: (0, 0, x
8 0100
or 1 < 0 and (0 0 (0)) 2 0. (aj 1, ar 100=00 0)
(2) (0)
Since modification did not help agent t receive action a 1, we can conclude that (0, -0, xxx) < 0.
Lemma B.3. Let fua X - E2o denote the density function of the uniform distribution over the d-dimensional unit sphere. If Z d and agent contexts are drawn from a distribution over
the d-dimensional unit sphere with density function J X - R2o such that _(xx) 2 Co E Rxo-
Txa(x)
Vx E X, then the following guarantee holds under apple tasting feedback.
(1e()) - -0:00:4112 co ca (2
2
2 2 log(2d/7))
with probability 1 Ye.
Proof. Let I (10 xx) 2 8110==1 (1)
112 + ro]- Then, from the definition of ( we have:
0 041
=
Σ X2 (I
Σ Ex,((1))1(T1))
(closed form solution of OL.))
Σ x
(7!1])
Σ xx, 1 + (
(plug in r, (1)
0 +
Σ x,x
xxxx)
Σ (
Re-arranging the above and taking the fg norm on both sides we get:
[0(0 - -00 000)
Σ x,x
Σ 12
<
Σ x,X, 11
Σ X Ex
(Cauchy-Schwarz
El XsC, 1 (I!-)
=
Dim x.X (I!! (1))))
Mmin
XxCo (I! /
Ei X. 1 (IS")))
Amin
16

---

where for matrix M. min is the smallest singular value mii (M) := min ||||=| || and Amin
is the smallest eigenvalue. Note that the two are equal since the matrix > x.x! 1172") is PSD the of PSD matrices (outer products induce PSD matrices). The final bound is obtained by applying Lemma B,4, Lemma B.5, and a union bound.
Lemma B.4. The following bound holds on the E--norm of Ex= xxe, with probability 76
Σ e I
2 1 (lgg(//r)
Proof. Let x[i] denote the i-th coordinate of vector x. Observe that E.= ex (i) is sum of martingale differences with Z, == c, [1] X, Ed= Xx [1] (I! }. and
X, max (P(2. a , Xa-1), P(z.
-a|Xi, X.-1)3 exp(-a² /20
By Theorem A.2,
+xx,|||(I!!!! s 2 1400
with probability 1 1- The desired result follows via union bound and algebraic manipulation.
Lemma B.S. The following bound holds on the minimum eigenvalue of E. x,x (I x with probability Te:
Σ x ((T [xxxI1(I!11) s=1
1
Amin
2 ca(,dd) c2(ō,)) + 4 21 2oggdd//1))
Proof.
1 Σ x 1(2(111
Aminn
1
2 Amin
Σ x.x, 1xx]]((111) (1 - E. 1x,x, 1(2!1131
+ Amin
E 1
[x.x] 11 ((!
2 Amin
Σ X,x, -
E.- xx,x,
11
+ Amin (E.1[xxx, 14I("
(2)
where the inequalities follow from the fact that Amin (A B) 2 Amin (A) Amin (B) for two Hermitian matrices A, B. Note that the outer products form Hermitian matrices. Let
Y, E x,x_ ((I E,-1(x,x,] (I("")) }1. Note that by the tower rule, EY, EY, 0.
Let -X, = E. x 1(I!") (1) H. then 1.-1l-X,, = O, and (-x.)² = 4la. By Theorem A.I.
P(Amau ( (-Y) 2 a) < exppppppp a² /32t).
Since -X -Amox (-Y)) = Amin (Y)).
P(Amau (V:) S a) S d exp(- /
Therefore, Aman (Yi) 2 4 2t log with probability Tt. We now turn our attention lower bounding Amin (Ea-1 [X,x] 1 (I). H).
17

---

(Esnn X,X, ([I == min
THE, EE-1 F[
wEg
( X,Xx 1 f(xx)
min wES
( x 1 M(x))
[ua(Xo) dx,
min wESU-1
[(xx)
2 <o
min WESd
1 [x.x 1 (T
c min
E, 1 x.) 3 x.) 2 5113,1|2 P 2 8113
wes
e2(6,e)
cu ((, min
E0-1,0- x, 3 x,) 2 8113,112] wES
(3)
Throughout the remainder of the proof, we surpress the dependence on U and note that unless stated otherwise, all expectations are taken with respect to U Let B, E Ra be the orthonormal matrix such that the first column is / //13.11..... l12.. Note that B,e = / ||| .112 and B,x ~ Ud.
E, Ex_1x 1B,, Xx) 6||3,111 IIl = EE,I B,x,) T (33 B,x,) 2 6] x B. || 2 2 111111]
=B,E,-1xx,x _
= -,,,,-1xxx x. [1] 2 R]
Observe that for j + 1 1, j. (0
0. Therefore,
E [x,x, 1(3 x 2 5|] [,x 6
+ (E|x,[1|3x,,11 2 5] - 12xx/2|%1x,11 2 81 )B
E|x, 2 8]/4
B.
B
+ (E[x,[1] x 2 5] |2x,12|
x
2 8))
133 l2
||3 1l
and
X Amin (F,-11E2220- (Ex (I!")
2 co cá d)
min wESH-1
(E[x.[2)3 xx 2 0|||
3_
+ (B|x, [1, [1] 8] E[x, 2 [1] 2x d))
w,
|/3 ll
z co (b. (8
Lemma B.6. For sufficiently large values of d.
a ( d) 2 θ (1 (1-2)
d
Proof. Lemma B.6 is obtained via similar argument Theorem 2.7 in Blum al. [15]. As in Blum et al. [15], we are interested in the volume of a hyperspherical cap. However, we are interested in lower-bound, not upper-bound (as is the case in [15]). Let denote the portion of the and let H denote the upper hemisphere.
d-dimensional hypersphere with x[1] 2 d-1
vol(A) vol(H)
e (ō, :0:d):=:2 = Px- 2
In order lower-bound (6, d), suffices to lower bound vol( and upper-bound vol (F). In what follows, let (dd denote the volume of the d-dimensional hypersphere with radius 1.
18

---

Lower-bounding (o): As in [15], to calculate the volume of A, we integrate an incremental volume that is disk of width dx[1] and whose face is ball of dimension d- and radius vI - x[1]² The surface area of the disk is (1 x " Vid - 1) and the volume above the slice x(1] 2 is
vol( f (1 V(dd))vvdd-)
To get a lower bound on the integral, we use the fact that 1 1 x²² シ - x for x E [0, 1]. The integral now takes the form
(A) 2 ( (1- (1-x1pg x(1]) (1-x V V(d-
v(d- 1)dx(1]
V(d-
2(1 6) -
d+1
Upper-bounding (H): We can obtain an exact expression for vol(H) terms of V -01 1) using the recursive relationship between Vdd) and V(d - 1):
vol(H)) = v(d)= v r + v(d-1) 1) 2 r +1)
Plugging in our bounds for vol(A), vol (H) and simplifying, we see that
11- r +1)
d (
(1-0)
[1
5) d+1
(i d)
θ
VT r( +
where the equality follows from Stirling's approximation.
Lemma B.7. The following bound holds on e2 (2(6,,) d):
3
1
1 3
(2
8
-
3d
2
Proof. We begin by computing [[x[2]*|x[1] 8*), for 8' (0, 1). xf 8. then x[2]² + x[d] 1 - ( Using this fact, we see that
Ex E[x[2) 87 d R Br--Un///0.11199999
(8))2)3
3d
Since [[x[2][[x[1] 2 5) [[x[2] =
5 + 1-61,
E| > E x 8 8+1
3
1
1
3d
4
2
4
B.2 Proof of Proposition 3.4
Proposition B.8. For any sequence of linear threshold policies BI....,
.......,y Br.
Exp (id
(( 3₂) 2 21113,1121 12 = Pxxxo (x[]] 2 8)
19

---

Proof. Let Br E Rdxd be the orthonormal matrix such that the first column is B,/118.12.. Note that
Bix ~ U if x ~ U and B,e1 = 3./113.112-
E XT= 1(x,, 3,) 2 811
x ~ ((x,, Bb) 2 6111.122)
P xu u (1 (3) 2 011131112)
P -x (x4 B, 113 2 (11
T
Σ Px - (x Iue1 2 ö112)
1=1
= T P Px (x[1] 2 2112)
B.3 Explore-Thes Then-Commit Analysis
Theorem B.9. Let fua : X + Rzu denote the density function of the uniform distribution over the d- d-dimensional unit sphere. If agent contexts are drawn from a distribution over the d-dimensional unit sphere with density function ; achieves the following performance guarantee
X + Rzo such that [(x). Tu(x) 2 Co > 0, Vx E X. then Algorithmm
8 633
RegETC S
do 2/3 log" (/dd/7)
co
with probability 1 7 = 4 6631/3 2/3 2/ log Proof.
1/3 (Ad/7)
Regete Σ (0(07) r(oe) Xx)
T
$ To +
(0(a))
-(aa)) xi)
t=1
T
(at)
0 xx) + (((()))
(ax))
-0//72 xx) + (0(me) -a())) xx)
= To
+
Tn/2
T=
$ To
(0(1)
Tn/2, xx) + ((0
(1)
0 -100 0T./2 xx)
+=
T
<T
+
(1((1)
0
1T/2212/1 1|2 + (0)00)
0 001/2112/|x1l/
T=+++
To + T (1
0 l/2 + T 11 0
24d
7
log(4d/7)
To +
Co
To
with probability - 7. where the last inequality follows from Lemma 1.10 and a union bound. The 1/3
result follows from picking To 4 63 do 2/3 log1/3 (Ad/7).
Lemma B.10. Let fua= : R2o denote the density function of the uniform distribution over the
d-dimensional unit sphere. T > 2d and agent contexts are drawn from distribution over the
20

---

d-dimensional unit sphere with function f: X then the following guarantee holds for {0, 13.
: + R20 such that f(x)
2
0. vx E X.
(x(x)
110|a) -0(4 l2
12d
7 log (2)
co V
Tu
with probability YY--
Proof. Observe that
To/2
To/2
Ta/2 =
(()
Σ
Xs+hX
Σ ==1
xx+xT (a) etk
==1
Tol2
To/2
Σ
X
2
x
(x (x (110(0)) + coth)
==1
T2/2
T2/2
(()) + Xs+1x stb
Xo+k60+b
where k = 0f a = and h: = To if = 1. Therefore,
To/2
To/2
[10(a) - -
Σ
Σ
X X
x kotk
To/2
To/2
Σ
Σ x x Eath
X Xs+
2
To/2 Σ
1=
X Xo+hCoth
12/2
mmin
x g
T26/2
To/2
To/2 E2al
Amin
X s4tk
The desired result is obtained by applying Lemma B.1 Lemma B.12, and a union bound.
L
Lemma B.11. The following bound holds on the E--norm of ETer Ta/2
X.+ACo4k with probability 1 1-y:
To/2
Σ
Xathes+k
<2/7dooTolog(u))
Proof. Observe that To/2
Ek Sxtal1 a sum martingale differences with Zets =
Ek+eXi+oli) [i], Xxte = Ei=t Cbts Xx+e [i], and max ZZ+o al a|Xe+1, X 1) Piztto < -a|X Xx+e-1) S exp((a?/2or
By Theorem A.2,
To T2/2
Σ
EktoXH+old] < 2 To 22/To log(1/>;)
with probability 1 1-7 The desired result follows via union bound and algebraic manipulation.
21

---

Lemma B.12. The following bound holds the minimum eigenvalue of Exe XstEX with probability 7.
'oof2
To
Xmin
Σ x x
2
T log(d/7)
6d
Proof.
To/2
To/2
To/2
Amin Σ
X X
Amin
x
xx s+h
E|x F+e) Amin ②
x3 2 xxxx)
To/2
To/2
Amin
xX 8+h
Exxx+ J+el) Amin xxx
where the inequalities follow from the fact that Amin (A + B3) Amin (A) Amin (B) for two Hermitian matrices A, B. Let VTO/2 = Exn X,+1x s+ - -E|x++xx5411 Note that IEY = EY, = 0, -X.tk = E[x, rl 18|-Xs442
0, and (-X++R)² 4la. By Theorem A.I,
P(Amaz ( - -Yro/2) 2 a) S d. exp(-at axp(-a2/16To)
Since ->mar(-Yro/2 (-Yro/2)
Amin (oinnYYo//)) (To/22)
P Coaaur(yr (YTo /2) & a) < d.
Therefore, Amin (Yro/2) 2 4 To (d/r) with probability 1 y. We now turn our attention to lower bounding Amin (B[x++*X,+41))
Amin (E [Xx+xx+XXX [++))) min w E E[xx+xxJI1Ll
WESt
min w 1
Tow
wESK-1 3d
3d
B.4 Proof of Theorem 3.5
Theorem B.13.
Regots (T) be the strutegic regret of Algorithm 1 and (T) be the sirategic regret of Algorithm 2. The expected strategic regret of Algorithm 3 is
[[Reg(T)) < 4 (iieee(Reeosss())).. E[ (T))}
Proof. Case 1: T < 7* From Theorem B.9, we know that
8 634/3
RogETO(T)) =
do 2/3 2/ 2/3
log 1/3
with probability 1 - 1/7/3 Therefore,
E|Regere (T:)]
8 1/33//3
do 2/3
2/3
log 1/3
2 T
Co
Observe that Σ B[ReKrTO(T)) such a scenario,
< [[eegr Suppose T-1 < T S for some i. Under
E Reg(
< 2E Reggre
< 2E Regerc (2T)
< 41E (Regere (T)]
22

---

Case 2: T r" Let t* denote the actual switching time of Algorithm 3.
RTg(T) Σ (0 ((())
x1)
Σ
(0 @(1x), xx))
E= +1
E [T) $ 2- E. EIREETE
El Regors (T - [*)]
2 E Regons (t" } E Regors (T)
$ 2 E RegoLs (T )] + E RegoLs((T)
3- E[Regon. (T)
where the first line follows from case 1, the second line follows from the fact that t* I T* (and so E|Regrre(t") & E[Regor.s( )), the third line follows from the fact that t* S r", and the fourth line follows from the fact that 2 T"
B.5 Inconsistency of OLS when using all data
Theorem B.14. lim 0 = 0 if and only if lime-soo Ex=1 x xxx = 13 =
lim E' 1(,, 1].
Proof.
1 xxxx,1100 1ia, =13
lim 0 000 lim
Ex =
6000
1000
lim 1-00
Σ x
T (ax =1] 1aa==1)
Ex((x 0.00 + (a,) =1)
lim 1-30
Σ
=1 T 11lll 11a==1) x,X,
Σ Xxx 0 10 = =1}
s=1
s=1
1
-1 1
+ lim 1000
Σ X 1 1fas =1}
Ex,1las =
[=1
s=1
lim [-000
Σ x
T [ax =1 1
Σ xxx110 1xxx1(aa = =1] o0e
C Proofs for Section
C.1 Proof of Theorem 4.1
da log 1/ld=2)
Theorem C.1. Algorithm with 17 V
log((E)) TX 7 = 211/(E), and E =
incurs
T
expected strategic regret:
E(Reg(T) s (4++))/(4+2) (do
log log 1(d()))) = =ō (T(4A1/(412))
Proof. Let ar.e correspond to the action chosen by a grid point E E. We simplify notation to a, = at,e, be the action chosen by the sampled grid point e, round L. For the purposes of the analysis, also define f((e) 1 + X Ti (.t.e.).
23

---

We first analyze the difference between the loss of the algorithm and the best-fixed point on the grid e", i.c.
E Rog (T) = max 3
Σ
re(at,e))
Σ
re(at)
AE|2]
LE|T
E
(((e))
min E
Σ l((e") [E(T]
(E(T]
where the equivalence between working with l((-) opposed rT(-) holds because &-)) are just shift from re(-) that is the same across all rounds and experts. For the regret of the algorithm, we show that:
T (0)
(.) ( log
2d
E[Reg (T)
(4)
We define the "good" event as the event that the reward is in [0. 1] for every round t: C = frr [0, 1]. Vt E [T]}. Note that this depends on the noise of the round Et. We will call the complement
of the "good" event, the "bad" event -C. The regret of the algorithm depends both and -C as follows:
E[Reg (T) = Rieg
+ E(Reg (T))-C]-Pr(-C
< E[Reg (T) (-T-Pr(-)) (5)
where the inequality is due the fact that Pr[C] < and that in the worst case, the algorithm must pick up loss of at each round.
We now upper bound the probability with which the bad event happens.
Pr|-C] Pr[at: Te
[0, 1]] S Σ
Pr(ra [0. 1]]
(union bound)
1E(T)
Σ
Pr[led 2 Al S 2 exp( - 22/00) T T
(substituting A)
(E[T]
Plugging Pr[-C] to Equation get:
E E[Reg (T) S B[Reg (T))c) +
(6)
So for the remainder of the proof we will condition on the clean event C and compute ERReg (T) Conditioning on C means that + (a) E [0, A], where a /log"
We first compute the first and the second moments of estimator (-). For the first moment:
E [Tiee) Σ ((e') 4(() llce = ee} (((e)
ge(e)
3'EE
For the second moment:
(e))
G((e) X2
E
(G(ee
Σ (el)
(8)
(c))
(c(c)
(c(c)
3'E3
where for the first inequality, we have used the fact that 4((e) S À (since we conditioned on C) and the last one is due the fact that ge(e) 2 7/|E).
We define the weight assigned grid point E & at round wr(e) w)-i(e) expppexxpppe
and wp (e) = 1, Ve E E. Let W₁ = -E wr(e) be the potential function. Then.
Wo Σ wo(e) 1
(9)
339
Using e* to denote the best-fixed policy in hindsight, we have:
Wr = Σ wr(e) 2 wr(e") )= = exp
-17 Σ E,(e") tE(T]
(10)
6EE
24

---

We next analyze how much the potential changes per-round:
EeEr exp (-nê((e)
log
W4+1
log
-log
Σ
Pe(e) (e()))xx exp (-nRi(e))
Wr
W,
leEE
Σ P((()) (1-ne((e)) +
s log
11
leEE
log
- 11 I- (e(e)(((e)) + 1/ Σ [m(e))((e)
CceePile) =
CEE
CEE
1) Σ P((e) r² (p(())((())
S
339
6EE
(e()) -7/181 Ee(c) + n1² Σ
[r(e)) - 7/181 (2(
(1 7)
(1-?)
33
338
(e(e) 7/181 (1 (1-7)
Ee(e) 2 +1²
Σ
(((e)
(2(e)
(11)
(1 7)
333
338
where the second inequality is due to the fact that log S 1 for 2 0. In order for this inequality to hold we need to verify that:
Σ P((e) + + Σ 2((e)) 2 0,
17
3EE
aEE
or equivalently, that:
1 Σ (e) 20
(12)
337
We do after explain how to tune 7 and y.
We return to Equation (II); summing up for all rounds t E [2]] in Equation (1I) we get:
W T Wo
(e - 7/18|
q((e)
log
S -
Ee (e( + n72
Σ> +E[T] CEE
(e(
(13)
(1 (1-7)
(1
tE|T BEE
Using Equation (9) and Equation (10) have that: (og(W//W)) > -n Eieryy Ee((e) - log [
Combining this with the upper bound on Log(Wr/Wo) from Equation (13) and multiplying both sides by (1 7)/n we get:
ΣΣ EEE
(e)))
) - (1-
7 [E
Ee(e)
Σ (E))S))))))
ΣΣ (()) (1 (1-7) log((E))
"
tE[T
tE(T]
We can slightly relax the right hand side using the fact that < and get: get:
E((e) (1 (1- 7) Σ (((e)s Sn Σ Σ (e)) + log((E))
ΣΣ 4E[2"] REE
(e(e)
? El
"
KE[2]
LE|2"] BEE
Taking expectations (wrt the draw of the algorithm) on both sides of the above expression and using our derivations for the first and second moment (Equation (7) and Equation (8) respectively) we get:
ΣΣ (E(T] 3EE 3EE
? l((e) (1-7) ge(e)
Σ Ee(e') In Σ
(((e) (E(T] 3EE
Σ
X²
log(lE))
[
(((e)
n
[E(T]
Using the fact that (.()) E [0 the above becomes:
log(lE)
E. [Reg"(T)]C)
Σ Σ (e))((())- - Ee(e" 11x
+ TT
7
(E|T cEE BEC
1E/T
25

---

log((E) TXPEI and 7 = 2n,/E1, we get that:
Tuning 17 = V
E Reg (T) < 3 / log(E))) 3 // log log(lE))
(14)
Before we proceed bounding the discretization error that we incur by playing policies only on the grid, we verify that Equation (12) holds for the chosen 17 and 7 parameters. Note that when (e(e)
then Equation (12) holds. So we focus on the case where Ex(e) = (<(e)/u(e))
(() Le(e) qi(e)
<n> EnEnle) L((e) (((e).18)
181
X X.1E1
A/1k 1
I 7 Σ (r(e)
Y
?
7 2
EEE
3EE
3E
where the first inequality is due to the fact that (e(e) > 7/181, Ve E, the second is because
fe(e) I X, the first equality is because Leer Pi(e) = 1, and the last equality is because of the values that we chose for parameters 17 and
The final step in proving the theorem to bound the strategic discretization error that we incur because our algorithm only chooses policies on the grid, while (0)) (00) (and hence, the actual optimal policy) may not correspond to any grid point. Let oz correspond to the action chosen by the optimal policy.
SDE(T) = Σ Bra(a))) - Σ (ri((ar,
)1 Σ (olai) E(plo)) , x11
LE|T
LE[2]
BETT]
We separate the T rounds into 3 groups: in group G1, we have rounds E [T] such that aj = at,e". In group G2. we have rounds t E [T'] such that a: = 0 but at,e. = 1. In group G3. we have rounds t E [T]. such that of = but or.e* = O. With these groups in mind, one can rewrite the above equation as:
SDE(T) = Σ ((llt) glar.et) xx xx)+ Σ ag(a)) xx xx)+ Σ (g -gla)) p(o xi
E(plo)
-
LEG
rEGs
LEGs
For all the rounds in G1, the strategic discretization error equal to Hence the strategic discretiza- tion error becomes:
(o(a)) - g/ar.o)) xx xx)) +
Σ (ola)) ) - glanee), Xt)
SDE(T)
(15)
EGG2
LEGs
SDE(G2)
SDE(Gs)
We first analyze SDE(G2):
SDE = Σ (D(O)
((1) x1
rEGs
(0) Let us denote by 00)) and the points such that e" in the above, we get:
- -00)
Adding and subtracting (e", xx)
SDE(G2)
Σ LEG2
(
(00))
000 xx +
())
0(1)
(11) Xx
+
(0)
0
xx,
S
(0)
0
(0)
X2 )
+
0 ((1) Xx )
+ 0
(0)
(1)
xx
(x S |x))
LEG2
(0)
(1)
$ 2cT
0
0
X2
(Cauchy-Schward
IEG2
Q+
Finally, we show that Q+ S 0. For the rounds where atee- 1 but a 0, it can be the case that
X A X (as the agents only strategize in order to get assigned action 1. But since Ut,e = 1, then from the algorithm:
11)
(0)
0 (0)
0 xx 5 15lle-'l
0 -
x
2
81 +
(16)
26

---

Adding and subtracting x from quantity Q₁ we have:
(
(1)
0 (0)
0 x
Q
X
x
+
0 00)
0
(1)
x,)
-01le"11
(Equation (16)
0 (0)
000
||x; x;1l - 811c111
(Cauchy-Schwarzz)
K |e'|| 6 8||e"||
As result:
SDE(G2) S 22T
(17)
Moving on to the analysis of (D)((Ga)
SDE(G3)
Σ tEGs
( -0(1, xx
Again, use 0" (1)
and 0 (0)
the points that e (1)
0 (0)
Adding and subtracting (e", xx) and
following the same derivations as SDF(Ga), we have that:
SDE(Gs) s 2 - Σ
X
(18)
tEGs
Since or.e = 0, then it must have been the case that X Xe: this is because the agent would not spend effort strategize if they would still be assigned action O. For this reason, it must be that Q 5.
Combining the upper bounds for SDE(G2) and SDE(G;) in Equation (15), have that SDE(T) < 4=T.
Putting everything together, we have that the regret is comprised by the regret incurred on the discretized grid and the strategic discretization error, i.e.,
E Reeg (T)) s 33 T log( (8)) + 4eT 31 Td (1) Ilgg(T) log(1/e) 4sT
[og 1/(d+2)
Tuning s
we get that the regret is:
E Regg()) < 6T((+1)(4422) (do (do T) 1(0+2)) = (T(4-118(412))
D Extension to trembling hand best-response
Observe that when lazy tiebreaking (Definition 2),,, if agent / modifies their context they modify it by an amount &r such that
8L, = min 77 0Snšá
s.t. 7 (x() =
|X - xxl12 = 17.
We define 7-trembling hand ticbreaking as ôTH, = ôg, + as where a; E [0, min(6 òτ, 7 may be chosen arbitrarily. Our results in Section 3 may be extended to trembling hand tiebreaking by considering the following redefinition of a clean point:
Condition D.1 (Sufficient condition for x' = x). Given shifted linear policy parameterized by ((4) E IRd say that context x' is clean if (1)) x²) (6 (1) + To-
27

---

No further changes are required. This will result in a slightly worse constant in Theorem 3.3 (i.e. all instances of 6 will be replaced by 7). Our algorithms and results in Section 4 do not change. Our definition of trembling hand best-response is similar in spirit to the e-best-response in Haghtalab al. [26]. Specifically, Haghtalab et al. [26] study a Stackelberg game setting in which the follower best-responds c-optimally. In our trembling hand setting, the strategic agent can also be thought of as e-best responding (using the language of [26]), although it important to note that an e-best response for the agent in our setting will cause the agent to only strategize more than necessary.
28


Reviews:
[{"review_id": "srYMZc6gMS", "reviewer": "Reviewer_qhsL", "summary": "This paper studies an online learning problem with one-sided (apple-tasting) feedback. At each round $t\\in[T]$, an agent with a $d$-dimensional context vector $x_t$ arrives. The principal chooses a policy $\\pi_t$ to map the context to binary decisions. Given $\\pi_t$, the agent best responds strategically by modifying their context to $x'_t$ where $||x'_t-x_t||\\leq \\delta$. Then, the principal receives a one-sided, linear feedback in $x_t$. The goal is to design a policy with sub-linear strategic regret that compares the principal's reward with that of the optimal policy had agents reported their contexts truthfully. The authors propose algorithms for stochastic and adversarial settings.", "questions": "- What is the reasoning behind a bounded $\\ell_2$ norm perturbation of size $\\delta$ (instead of a different norm or a packing-type constraint) as the effort budget? Could you explain this in the context of a motivating application? \n- Why is $r_0$ missing in the linear thresholding policy of Algorithm 3?\n- Instead of considering each $d$-dimensional vector in $[0,1]^d$ (or a discretized grid of such vectors) as experts in Algorithm 3, is it possible to assume a structure on the policies and solve the resulting online structured learning problem (as it's done in the following papers)?\n\nKoolen, Wouter M., Manfred K. Warmuth, and Jyrki Kivinen. \"Hedging Structured Concepts.\" COLT. 2010.\nCohen, Alon, and Tamir Hazan. \"Following the perturbed leader for online structured learning.\" International Conference on Machine Learning. PMLR, 2015.\n\n- Algorithm 4 is mentioned multiple times in the paper, but it's not provided in the main text. It'd be great to either have the algorithm or a short description of it in the paper.\n- Is it possible to relax the assumption that the variance $\\sigma^2$ is known? How would such a relaxation affect the results?\n\n\n--------------------------------\nI've read the authors' rebuttal, thanks for addressing my questions and concerns.", "limitations": "The limitations are clearly discussed in the conclusion. This is a theoretical work and a discussion of potential negative societal impacts is not necessary.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Online learning with strategic agents has many real-world applications and the results of this work could be applied to automatic decision-making processes such as lending and hiring. Therefore, the problem is very well-motivated.\n- The paper is very well-written, in particular, the proof sketches provided in the paper give a very clear high-level picture of the techniques and ideas used to analyze the performance of the algorithms.\n- The authors have done an excellent job comparing and contrasting their paper with prior works, it is clear how this paper contributes to this literature.", "weaknesses": "- While the proposed algorithms are a great first step towards solving this problem, they are sub-optimal from different aspects. First, Algorithm 1 does not make any use of unclean data and it simply discards them. While the authors have shown that using unclean data for estimation is not useful, they could be used with some confidence level to rule out some of the underperforming policies. Moreover, Algorithm 3 for the adversarial setting is practically not useful because of its exponential computational complexity.\n- Based on the motivating examples that are provided in the introduction, I don't see why agents strategically modifying their context vector is necessarily a bad thing. For instance, paying bills on time and maintaining low credit utilization to increase credit scores (which is used for lending) should be incentivized (rather than discouraged).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. Please find our answers to your questions below.\n\n[*What is the reasoning behind a bounded ℓ2 norm perturbation of size $\\delta$ (instead of a different norm or a packing-type constraint) as the effort budget? Could you explain this in the context of a motivating application?*]\n\nWe chose to model the agent’s effort budget with respect to the l2 norm in order to allow for an easier comparison to both (1) the existing literature on strategic learning (e.g., “Learning strategy-aware linear classifiers” by Chen et al., 2020) and (2) the adversarial robustness literature (see, e.g. “Certified Adversarial Robustness via Randomized Smoothing” by Cohen et al., 2019), in which an adversary is allowed to perturb the input to a machine learning algorithm such that the perturbed input is within an l2 ball of the original input. We conjecture that our results are generalizable to the setting under which the agent’s modification is constrained by an arbitrary (known) p-norm. However, this is non-trivial because the naive reduction from the l2 norm to an arbitrary p-norm is not tight (indeed, we only know of not matching upper and lower bounds), and so just substituting the appropriate upper/lower bound may result in false positives/negatives. Finally, packing-type constraints have not been studied in the literature on strategic learning to the best of our knowledge, but we believe that this would be an interesting direction for future research.\n\n[*Why is $r_0$ missing in the linear thresholding policy of Algorithm 3?*]\n\n $r_t(a_{t,e_t} ) = r_0$ whenever the principal takes action 0. Note that according to our apple tasting feedback whenever the principal takes action 0, they do not observe feedback. In Lines 339-340 we explain how the linear thresholding policy would change if the principal were to observe feedback whenever they chose action 0 too (i.e., bandit feedback).\n\n[*Instead of considering each $d$-dimensional vector in $[0,1]^d$ (or a discretized grid of such vectors) as experts in Algorithm 3, is it possible to assume a structure on the policies and solve the resulting online structured learning problem (as it's done in the following papers)?*]\n\nWe view structured learning in strategic settings as an important direction for future work as, to the best of our knowledge, it has not yet been considered even in the full feedback setting. It may be possible to adapt Algorithm 1 to a structured policy class, if we are given access to an optimization oracle for that class. This is because Algorithm 1 computes a greedy estimate of the optimal policy class in the non-strategic setting, then shifts it to account for the strategic behavior of the agents. Using an optimization oracle, one could do something similar by first estimating the optimal policy using the optimization oracle, then modify the estimated policy to account for strategic behavior. \n\n[*Algorithm 4 is mentioned multiple times in the paper, but it's not provided in the main text. It'd be great to either have the algorithm or a short description of it in the paper.*]\n\nThank you for this suggestion, which was brought up by other reviewers as well. We will add Algorithm 4 to the main body of the paper..\n\n[*Is it possible to relax the assumption that the variance $\\sigma^2$ is known? How would such a relaxation affect the results?*]\n\nYes, thanks for pointing this out. An upper bound on the variance should suffice, as we only require knowledge of $\\sigma^2$ when setting algorithm hyperparamters. In this case the same bounds will hold, but with the upper-bound on $\\sigma^2$ in place of $\\sigma^2$.\n\n"}, {"review_id": "8qV3j4CfWs", "reviewer": "Reviewer_vd1A", "summary": "They consider the problem of online learning with apple tasting feedback where the sequence of arriving agents may strategically modify their features (contexts). They show how to achieve sublinear strategic regret compared to the best policy in the hindsight if agents were reporting truthfully.\n\nTheir main result is $\\tilde{O}(\\sqrt{T})$ strategic regret when the sequence of agents arriving is stochastic. Their regret bound depends exponentially on d the context dimension. They show how to mitigiate this dependency and achieve a regret bound that depends polynomially on d but with a worse dependence on T. The main idea to to use a modified version of explore-then-commit algorithm that was introduced in the prior work.\n\nFinally, they extend their results to a sequence of agents chosen by an oblivious adversary that achieves sublinear regret however it requires an exponentially large amount of computation at each round.\n", "questions": "It might be helpful to add a paragraph on how your bounds differ from the non-strategic case.\n\nProp 2.4. last line, it might be helpful for the reader to argue why the first term is at most 0.\n\nLine 218, you can ensure the data is clean since it is strictly above the threshold?\n\nThm 3.3. it might be helpful to also remind the reader what c_0 is.\n\nAnother open question is to get regret bounds when the agents are picked by an adaptive adversary.\n\nAre there any connections between the trembling hand model that you are describing and the \\eps-best response model considered by [Haghtalab, Lykouris, Nietert, Wei' EC22]?\n\nAnother piece of work related to your bandit feedback could be the work by [Ahmadi, Blum, Yang' EC23] where in one of their models they propose a modification of EXP3 algorithm in the strategic setting. \n", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I think the paper is written nicely and the results are nice. The algorithms seem to be a natural extension of the non-strategic setting. The model is interesting and the presentation is great.\n", "weaknesses": "I think the paper is written nicely and the results are nice. The algorithms seem to be a natural extension of the non-strategic setting. Since they are using the linear thresholds model, they need to shift the decision boundary to account for strategic behavior and a similar set of ideas have been studied in the previous work.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. Please find our responses to your questions below.\n\n[*It might be helpful to add a paragraph on how your bounds differ from the non-strategic case.*]\n\nWe would be happy to add such a paragraph in Section 1.1 where we discuss our contributions. At a high level, our main bound (i.e., the one for stochastic contexts) has a worse dependence on the context dimension, which arises as a direct result of the agents’ ability to strategize. \n\n[*Prop 2.4. last line, it might be helpful for the reader to argue why the first term is at most 0.*]\n\nThe first term is at most zero since the principal’s reward from the optimal policy when the agent strategizes is at most their optimal reward when agents do not strategize. We will add a sentence saying this in our next revision.\n\n[*Line 218, you can ensure the data is clean since it is strictly above the threshold?*]\n\nYes, we will clarify this in the revision.\n\n[*Thm 3.3. it might be helpful to also remind the reader what c_0 is.*]\n\n$c_0$ is a lower bound on the bounded density ratio and is defined in Assumption 3.1. We will clarify this in our theorem statement.\n\n[*Another open question is to get regret bounds when the agents are picked by an adaptive adversary.*]\n\nModifying Algorithm 3 to be based on EXP3.P instead of EXP3 would allow us to handle this setting, and we will add a comment on that after the discussion on Algorithm 3. \n\n[*Are there any connections between the trembling hand model that you are describing and the \\eps-best response model considered by [Haghtalab, Lykouris, Nietert, Wei' EC22]?*]\n\nYes, the two models are similar at a high level. In particular, HLNW22 study a Stackelberg game setting in which the follower best-responds $\\epsilon$-optimally. In our trembling hand setting, the strategic agent can also be thought of as $\\epsilon$-best responding, although it is important to note that an $\\epsilon$-best response for the agent in our setting will cause them to only strategize more than necessary (at least for sufficiently small epsilon). We will add a discussion about this connection (and a reference to HLNW22) in the revision.\n\n[*Another piece of work related to your bandit feedback could be the work by [Ahmadi, Blum, Yang' EC23] where in one of their models they propose a modification of EXP3 algorithm in the strategic setting.*]\n\nThanks for sharing this reference. While related in the sense that they study an online strategic learning problem, ABY23 focus on the full feedback setting, whereas our primary focus is strategic learning under apple tasting and bandit feedback. Note that when ABY23 refer to ‘bandit feedback’ in Sec. 6.1, they mean that they only see the outcome under the deployed classifier (vs all possible classifiers), while we use `bandit feedback’ to refer to the fact that we only see feedback when a positive decision is made.\n"}, {"review_id": "Jl0D3DWy2z", "reviewer": "Reviewer_6Gq7", "summary": "The paper considers contextual bandit problem in which the users can strategically modify their context for its own sake.\nIt provides sublinear regret algorithms by exploiting the budgeted strategic structure of the agents, against stochastically chosen agents.\nIt further obtains sublinear regret algorithms against adversarially chosen agents by considering a variant of EXP3.", "questions": "- What happens if the principal can also optimize over the choice of decision policy, i.e., not just using thresholded rule?\n- In L254, even though a small fraction of agents may strategically modify their contexts, it seems fairly intuitive that the estimates would be inconsistent, so wonder why the authors think this to be a surprising fact - is it meant to be \"far\" from being consistent, not just inconsistent?\n- L82 consists a lot of citations. It looks bad to me, at least parsing them/giving more contexts to each reference/removing part of them would be helpful. It's a bit distracting in its current form and gave me no information.\n- It seems that the algorithm essentially needs to know the budget $\\delta$ in advance. What happens if the algorithm has misspecified budget? Is the algorithm fairly robust?\n- In L170, bandit feedback setting is said to be more challenging - why is it more challenging than the one-sided feedback? Also, the authors argue that all their algorithms can be made to be applicable to the bandit setting - yes it's good to know that, but I wonder if there's more general results, e.g., any reduction from one setting to the other, or if the authors have thought about any black-box reduction from one algorithm to another.\n- I also wonder why the standard adversarial contextual bandit algorithm does not work, instead of Algorithm 1, possibly with some slight modifications.\n- I'd like to ask on how the authors think about the case if the agents observe some noisy context about themselves.\n\nMinor comments\n- I found the presentation of Stackelberg regret and Proposition 2.4 a bit redundant, as it does not appear in the main paper but there.\n- In Algorithm 1, what is data $S_t$ - it seems it's not updated at all?\n- L290, typo: withing\n- L298, duplicated threshold\n", "limitations": "Detailed comments are in Questions.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies interesting problem setting and makes reasonable contribution.", "weaknesses": "Although the analysis seems technically thorough, intuition behind the solution is pretty straightforward: incentivize truthful action for certain amount of times, estimate $\\theta$, strictly separate strategically modified context by conservatively setting decision boundary based on the effort budget.\nAlso, the algorithm seems to heavily depend on the information on the agents' budget.\nDetailed comments are in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. Please find out responses to your comments and questions below.\n\n[*What happens if the principal can also optimize over the choice of decision policy, i.e., not just using thresholded rule?*]\n\nThis is an interesting question. While we are able to obtain no-strategic-regret by only considering linear decision policies, it may be possible in theory to obtain better rates if non-linear decision policies are deployed. However this appears challenging, as we point out in Section 3.1 “While our results do not rule out better strategic regret rates in d for more complicated algorithms (e.g., those which deploy non-linear policies), it is often unclear how strategic agents would behave in such settings, both in theory (Definition 2.1 would require agents to solve a non-convex optimization with potentially no closed-form solution) and in practice, making the analysis of such nonlinear policies difficult in strategic settings.”\n\n[*In L254, even though a small fraction of agents may strategically modify their contexts, it seems fairly intuitive that the estimates would be inconsistent, so wonder why the authors think this to be a surprising fact - is it meant to be \"far\" from being consistent, not just inconsistent?*]\n\nOn line 253 we say that this phenomenon is unsurprising (not “surprising” as the reviewer mentions) - we include it because it motivates the study of “strategy-aware” algorithms. \n\n[*L82 consists a lot of citations. It looks bad to me, at least parsing them/giving more contexts to each reference/removing part of them would be helpful. It's a bit distracting in its current form and gave me no information.*]\n\nWe chose to include the citations to show that there is a lot of work in this area which does not consider one-sided feedback. However we see your point, and will give more context to these references in an appendix. \n\n[*It seems that the algorithm essentially needs to know the budget $\\delta$ in advance. What happens if the algorithm has misspecified budget? Is the algorithm fairly robust?*]\n\nAlgorithm 1 is fairly robust to overestimates of the budget $\\delta$, in the sense that (1) it will still produce a consistent estimate for $\\theta^{(1)}$ (albeit at a rate which depends on the over-estimate instead of the actual value of $\\delta$) and (2) it will incur a constant penalty in regret which is proportional to the amount of over-estimation. Algorithm 4 will also incur a constant penalty in regret which is proportional to the amount of misspecification (either over- or under-estimation). We will add a short discussion on this in the revision after the presentation of our bounds. \n\n[*In L170, bandit feedback setting is said to be more challenging - why is it more challenging than the one-sided feedback? Also, the authors argue that all their algorithms can be made to be applicable to the bandit setting - yes it's good to know that, but I wonder if there's more general results, e.g., any reduction from one setting to the other, or if the authors have thought about any black-box reduction from one algorithm to another.*]\n\nBandit feedback is (slightly) more challenging in our setting, since an additional parameter ($\\theta^{(0)}$) needs to be estimated. The algorithms for both feedback settings are more-or-less the same: the only difference is to estimate and use this additional parameter in the bandit feedback setting. We chose to present our results in terms of apple tasting feedback since that is the type of feedback present in our motivating examples.\n\n[*I also wonder why the standard adversarial contextual bandit algorithm does not work, instead of Algorithm 1, possibly with some slight modifications.*]\n\nWe are not sure which algorithm you are referring to when you say “standard adversarial contextual bandit algorithm”. If you mean EXP4, this requires a set of (strategy-aware) experts for which we know the action they would recommend at each round. But note that the action per expert depends on the agent’s context, which is strategically changed as a response to the chosen expert. In other words, unless all agents are truthful with their contexts, we cannot infer the actions that all the experts would recommend per round (which is required for the EXP4 update).  \n\nIf you are referring to the more recent line of work on “adversarial contextual learning” (e.g., “Efficient Algorithms for Adversarial Contextual Learning” by Syrgkanis et al., “Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits” by Syrgkanis et al., “BISTRO” by Rakhlin & Sidharan), they require advanced knowledge of the distribution over contexts to give as input to their algorithms (an assumption we do not require). Moreover in the strategic setting, the distribution over contexts changes as a function of the algorithm deployed by a learner, since different algorithms will cause agents to strategize in different ways. Finally note that Algorithm 1 enjoys a better dependence on $T$ in the regret bound when compared to algorithms in this line of work ($T^{1/2}$ versus $T^{2/3}$ and $T^{3/4}$).\n\n[*I'd like to ask on how the authors think about the case if the agents observe some noisy context about themselves.*]\n\nIf agents observe a noisy version of their context (instead of their true context), then a best-response similar to our “trembling hand tiebreaking” assumption (see Line 133 in the main body and Appendix D for more details) may be reasonable since in this case, an individual who strategizes may want to “play it safe” and “overshoot” the decision boundary by a bit to account for the fact that they do not have perfect knowledge of their context.\n\nFinally, thank you for pointing out the typos and suggestions. In particular, data $S_t$ is a typo - this should be data $D_t$. We will correct this and all others mentioned.\n"}, {"review_id": "gHbO7hvmJO", "reviewer": "Reviewer_Mu3N", "summary": "The paper studies strategic apple tasting settings. This setting involves decision making that assigns decisions to agents who have incentives to strategically modify their input (context), and the decision maker only receives apple tasting (one-sided) feedback, where it only receives feedback for positively assigned decisions. The authors formulate this setting as an online learning problem with apple-tasting feedback, where a principal makes decisions about a sequence of T agents, with the goal of achieving sublinear strategic regret. Under this problem formulation, the authors proposed a learning algorithm (Algorithm 1) based on greedy, shifted linear policy, and parameter updates based on clean contexts. The author shows that the algorithm achieves O(\\sqrt{T}) strategic regret when the sequence when the agent contexts are generated stochastically. Then, the authors extendes to the situation where T is small or unknown and proposed another algorithm (Algorithm 2) under this scenario. Finally, the authors relax the assumption and provide an algorithm (Algorithm 3) under adversarially generated agents. These results apply to the more general setting of bandit feedback, under slight modifications to the algorithms.", "questions": "- As in the above section, can the authors shed some light on the strategic modification effort budget?\n- Line 212: The authors mentioned \"This is the type of strategizing we want to incentivize.\" I didn't understand why the decision maker would like to incentivize this behavior?\n- Algorithm 1 line 4, \"... and data S_t\", do you mean \"data D_t\"?\n- Can the authors move algorithm 4 (which is part of algorithm 2) into the main text?", "limitations": "I see that the authors listed a few related future directions in the conclusion. No negative societal impact observed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I like that the paper is very well written and easy to follow\n- The studied one-sided feedback settings with strategic agents are interesting and often occurs in real-world situations.\n- The problem is clearly formulated. For all proposed algorithms, the authors provided performance guarantees which are clearly explained and supported by proofs.\n", "weaknesses": "It is slightly hard for me to make a connection between assumption of the agent's strategic modification to their context (with effort budget \\delta mentioned in definition 2.1), and the motivated examples such as hiring and lending. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. Please find our responses to your questions and comments below. \n\n[*As in the above section, can the authors shed some light on the strategic modification effort budget?*]\n\nConsider a lending setting in which an applicant (strategic agent) wishes to obtain a loan from a bank (principal). Each agent is described by some context (e.g., number of lines of existing credit, credit history, current income, etc.), which may be strategically modified by the agent. Using the (possibly modified) context, the goal of the bank is to decide whether or not to give the applicant a loan. If the loan is given to the applicant, the bank observes some reward (e.g. whether or not the loan was paid back on time, amount of interest accrued, etc.). Otherwise if they reject the applicant, they receive no signal about their decision.  \n\nSpecifically regarding the effort budget, it may be viewed as a hard constraint on the amount an individual is able to strategically modify their original context. In settings such as lending, this budget is analogous to “hard”/”strict” time or monetary constraints that agents may have when modifying their context. For a more concrete example, a loan applicant may only have several hours every day during which he/she may prepare for their loan application (due to other responsibilities). In this case, the amount they can strategize is limited by this time constraint. \n\n[*Line 212: The authors mentioned \"This is the type of strategizing we want to incentivize.\" I didn't understand why the decision maker would like to incentivize this behavior?*]\n\nBy “this is the type of strategizing we want to incentivize”, we just meant that we want these particular agents to strategize so that we can assign the positive action to them (since this is what maximizes the principal’s utility), as we shifted the decision boundary to account for the strategic behavior of the agents who should not receive the positive action. We will add a clarifying sentence in our revision.\n\n[*Algorithm 1 line 4, \"... and data S_t\", do you mean \"data D_t\"?*]\n\nYes, thank you for pointing this out.\n\n[*Can the authors move algorithm 4 (which is part of algorithm 2) into the main text?*]\n\nYes – we will do so in the revision.\n"}, {"review_id": "hXYto7SsPj", "reviewer": "Reviewer_qFGe", "summary": "The paper studies an online learning problem with incentives. In particular, in the model studied in the paper there is a principal who has to take decisions on a sequence of $T$ (different) agents. Each agent has a context and they can strategically disclose it (truthfully or untruthfully) to the principal in order to induce them to take favorable decisions. The key feature of the model studied in the paper is that the feedback is one-sided, meaning that the principal only observes a feedback when they take a positive decision on the agent. The paper first proposes an algorithm that achieves $\\tilde O(\\sqrt{T})$ strategic regret (a stronger notion than Stackelberg regret), when the the contexts are selected stochastically. Then, the paper shows how to deal with adversarially-chosen contexts, by providing an algorithm with $\\tilde O(T^{(d+1)/(d+2)})$ strategic regret.", "questions": "1) I believe that the model studied in the paper is closely connected with one introduced in a very recent preprint (Bernasconi, Martino, et al. \"Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion.\" arXiv preprint arXiv:2303.01296 (2023).). In that paper, the authors study a model with type reporting that looks very similar to the one in the present paper. Am I right?\n2) The regret bound in Theorem 4.1 is very similar to a regret bound in (Zhu, Banghua, et al. \"The Sample Complexity of Online Contract Design.\" arXiv preprint arXiv:2211.05732 (2022).). Can you discuss the differences between the approach in that paper and your approach?\n3) Algorithm 3 requires exponential running time in the worst case. Are there any computational hardness results that can be applied to your problem?", "limitations": "No limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "ORIGINALITY\n\nThe paper studies, for the first time to the best of my knowledge, an online learning problem in which both incentives and one-sided feedback are involved. This is a relevant combination present in may application domains.\n\nQUALITY\n\nThe paper does a good job in addressing several aspects of the online learning problem under study. In particular, the paper studies both the case in which contexts are selected stochastically and the one in which they are chosen adversarially. \n\nCLARITY\n\nThe paper is well written and easy to follow.\n\nSIGNIFICANCE\n\nI believe that the problem studied in the paper is of interest several people spanning different communities, from online learning to algorithmic game theory.", "weaknesses": "ORIGINALITY\n\nThe techniques used in the paper are not groundbreaking, but they are rather adaptations of well-known and widely-used techniques in online learning.\n\nQUALITY\n\nWhile the literature revised in the paper is quite extensive as far as work on online learning with incentives are concerned, I think the paper is missing some very related works in the literature at the interface between algorithmic game theory and online learning. In particular, the following lines of research seem strongly related to the paper:\n- Repeated Stackelberg games: Balcan, Maria-Florina, et al. \"Commitment without regrets: Online learning in stackelberg security games.\" Proceedings of the sixteenth ACM conference on economics and computation. 2015. (see also some subsequent works extending the paper)\n- Online Bayesian persuasion: Castiglioni, Matteo, et al. \"Online bayesian persuasion.\" Advances in Neural Information Processing Systems 33 (2020): 16188-16198. + Castiglioni, Matteo, et al. \"Multi-receiver online bayesian persuasion.\" International Conference on Machine Learning. PMLR, 2021. (these works extend those on repeated Stackelberg games to the Bayesian persuasion framework)\n- Online learning in principal-agent problems: Zhu, Banghua, et al. \"The Sample Complexity of Online Contract Design.\" arXiv preprint arXiv:2211.05732 (2022). (a recent preprint that indeed seems very related to the present paper)\nI would have expected a discussion on these works in the paper. Of course, the papers that I cited above are only some representative of such a line of research, and I am happy to provide more references if the authors need them.\n\nCLARITY\n\nNo weaknesses to report.\n\nSIGNIFICANCE\n\nNo weaknesses to report.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. Please find our answers to your comments/questions below.\n\n[*While the literature revised in the paper is quite extensive as far as work on online learning with incentives are concerned, I think the paper is missing some very related works in the literature at the interface between algorithmic game theory and online learning. In particular, the following lines of research seem strongly related to the paper…*]\n\nWhile we agree that the settings you mention are related in the sense that all of these settings (including ours) are various instantiations of Stackelberg games, we did not originally include them as we believe that they are not as strongly related to our work as the literature we already cited. However, we are happy to include them in an expanded related work section and we highlight below the major differences and similarities with our paper.\n\nRepeated Stackelberg games: In this literature, the principal (leader) commits to a mixed strategy over a finite set of actions, and the agent (follower) best-responds by playing an action from a finite set of best-responses. Note that unlike in our setting, both the principal’s and agent’s payoffs can be represented by matrices. In contrast, in our setting the principal commits to a pure strategy from a continuous set of actions, and the agent best-responds by playing an action from a continuous set.\n\nOnline Bayesian persuasion: In this literature, the principal (sender) commits to a “signaling policy” (a random mapping from “states of the world” to receiver actions) and the agent (receiver) performs a posterior update on the state based on the principal’s signal, then takes an action from a (usually finite) set. In both this setting and ours, the principal’s action is a policy. However in our setting the policy is a linear decision rule, whereas in the Bayesian persuasion setting, the policy is a set of conditional probabilities which form an “incentive compatible” signaling policy. This difference in the policy space for the principal typically leads to different algorithmic ideas being used in the two settings. \n\nOnline learning in principal-agent problems: Strategic learning problems are indeed an instance of online learning in principal-agent problems. Since you mention online contract design as a particular example, we will highlight how our work differs from this area. In contract design, the principal commits to a contract (a mapping from “outcomes” to agent payoffs). The agent then takes an action, which affects the outcome. In particular, they take the action which maximizes their expected payoff, subject to some cost of taking the action. The goal of the principal is to design a contract such that their own expected payoff is maximized. While the settings are indeed similar, there are several key differences. First, in online contract design the principal always observes the outcome, whereas in our setting the principal only observes the reward if a positive decision is made. Second, the form of the agent’s best response is different, which leads to different agent behavior and, as a result, different online algorithms for the principal (see below for more details). \n\n\n[*I believe that the model studied in the paper is closely connected with one introduced in a very recent preprint (Bernasconi, Martino, et al. \"Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion.\" arXiv preprint arXiv:2303.01296 (2023).). In that paper, the authors study a model with type reporting that looks very similar to the one in the present paper. Am I right?*]\n\nIn type reporting, the sender (principal) asks each receiver (agent) to select a signaling scheme, and the signaling schemes are designed in a way such that each receiver is incentivized to select the signaling scheme corresponding to their (true) type. In our setting, the agent’s “type” may be thought of as their context. However unlike the online Bayesian persuasion setting, in our setting the agent has an incentive to strategically misreport their type. Another (less important) difference between our setting and this one is that in our setting the agent’s type is from a continuous space, but the type space is discrete in the setting of Bernasconi et al. We will add these connections in a revision.\n\n[*The regret bound in Theorem 4.1 is very similar to a regret bound in (Zhu, Banghua, et al. \"The Sample Complexity of Online Contract Design.\" arXiv preprint arXiv:2211.05732 (2022).). Can you discuss the differences between the approach in that paper and your approach?*]\n\nThe two algorithms are similar, as both are running multi-armed bandit algorithms (in our case EXP3, in their case UCB) over a discretization of a continuous action space. As a result, our novelty in this section is the analysis of the algorithm in the strategic setting we consider. (Note that the analysis of our algorithm differs significantly from theirs; ours relies on bounding the “strategic discretization error”, whereas theirs uses a covering argument to bound discretization error.)\n\n[*Algorithm 3 requires exponential running time in the worst case. Are there any computational hardness results that can be applied to your problem?*]\n\nWe are not aware of any such hardness results. As we mention in the conclusion, an exciting direction for future research is to design polynomial-time algorithms (or prove hardness results) for the adversarially-chosen context setting. \n"}]

Author rebuttal:

Meta-review: Overall, reviewers are all leaning towards acceptance. They think the paper studies an interesting and well-motivated problem, and the paper is well-written.

The reviewers also mentioned concerns on some assumptions and the disconnection between the paper's setting and motivating examples. It might be good add more discussions for these concerns.
Decision: Accept (poster)