Strategic Apple Tasting

Keegan Harris 1 Chara Podimata 2 Zhiwei Steven Wu 1

Abstract
Algorithmic decision-making in high-stakes
domains often involves assigning decisions toagents 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 forrounds in which they assign a positive decision to
the agent; this type of feedback is often referred toas 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 theperformance 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 Õ( T )strategic regret when the sequence of agents ischosen stochastically. We also give an algorithm
capable of handling adversarially-chosen agents,
albeit at the cost of Õ(T (d+1)/(d+2) ) strategic
regret (where d is the dimension of the context).
Our algorithms can be easily adapted to thesetting where the principal receives bandit
feedback—this setting generalizes both the linear
contextual bandit problem (by considering agentswith incentives) and the strategic classification
problem (by allowing for partial feedback).

1. Introduction
Algorithmic systems have recently been used to aid inor automate decision-making in high-stakes domains(including lending and hiring) in order to, e.g., improve
efficiency or reduce human bias (Berman, 2021; mon).
*
Equal contribution 1 School of Computer Science, Carnegie
Mellon University, Pittsburgh, USA 2 Sloan School of Management, Massachusetts Institute of Technology, Cambridge, USA.
Correspondence to: Keegan Harris <keeganh@cs.cmu.edu>.

ICML (International Conference on Machine Learning) Workshop
on The Many Facets of Preference-based Learning, Honolulu,
Hawaii, USA. Copyright 2023 by the author(s).

When subjugated to algorithmic decision-making in highstakes settings, individuals have an incentive to strategicallymodify 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 anindividual will pay back a loan on time if given one. Online
articles with titles like “9 Ways to Build and Improve Your
Credit Fast” are ubiquitous and offer advice such as “paycredit card balances strategically” in order to improve one’s
credit score with minimal effort (O’Shea, 2022). In hiring,common advice ranges from curating a list of keywords
to add to one’s resume, to using white font in order to“trick” automated resume scanning software (Eilers, 2023;
the). If left unaccounted for, such strategic manipulations
could result in individuals being awarded opportunities forwhich they are not qualified for, possibly at the expense of
more deserving candidates. As a result, it is critical to keep
individuals’ incentives in mind when designing algorithms
for learning and decision-making in high-stakes settings.
In addition to dealing with incentives, another challenge ofdesigning learning algorithms for high-stakes settings is thepossible selection bias introduced by the way decisions are
made. In particular, decision-makers often only have accessto feedback about the deployed policy from individuals thathave received positive decisions (e.g., the applicant is given
the loan, the candidate is hired to the job and then we canevaluate how good our decision was). In the language of
online learning, this type of feedback is known as apple
tasting (or one-sided) feedback. When combined, these twocomplications (incentives & one-sided feedback) have thepotential to amplify one other, as algorithms can learn only
when a positive decision is made, but individuals have an
incentive to strategically modify their attributes in order toreceive such positive decisions, which may interfere withthe learning process.
1.1. Contributions
We formalize our setting as a game between a principal anda sequence of T strategic agents, each with an associatedcontext xt which describes the agent. At every timet ∈ {1, . . . , T }, the principal deploys a policy πt , amapping from contexts to binary decisions (e.g., whether toaccept/reject a loan applicant). Given policy πt , agent t thenpresents a (possibly modified) context x′t to the algorithm,
and receives a decision at = πt (x′t ). If at = 1, the principal

Strategic Apple Tastingobserves reward rt (at ) = rt (1); if at = 0 they receive
no feedback. (rt (0) is assumed to be known and constantacross rounds.) Our metric of interest is strategic regret,i.e., regret with respect to the best fixed policy in hindsight,
if agents were truthful when reporting their contexts.
√
Our main result is an algorithm which achieves Õ( T )strategic regret (with polynomial per-round runtime) when
there is sufficient randomness in the distribution over agents(Algorithm 1). At a high level, our algorithm deploys alinear policy at every round which is appropriately shiftedto account for the agents’ strategic behavior. We identify
a sufficient condition under which the data received by thealgorithm at a given round is “clean”, i.e. has not been strategically modified. Algorithm 1 then online-learns the relationship between contexts and rewards by only using data forwhich it is sure is clean.The regret of Algorithm 1 depends
on an exponentially-large constant c(d, δ) ≈ (1 − δ)−d dueto the one-sided feedback available for learning, where d isthe context dimension and δ ∈ (0, 1) is a parameter which
represents the agents’ ability to manipulate. While thisdependence on c(d, δ) is insignificant when the number of
agents T → ∞ (i.e. is very large), it may be problematicfor the principal whenever T is either small or unknown.
To mitigate this issue, we show how to obtain Õ(d · T 2/3 )strategic regret by playing a modified version of thewell-known explore-then-commit algorithm (Algorithm 4).
At a high level, Algorithm 4 “explores” by always assigning
action 1 for a fixed number of rounds (during which agents
do not have an incentive to strategize) in order to collectsufficient information about the data-generating process.
It then “exploits” by using this data learn a strategy-aware
linear policy. Finally, we show how to combine√ Algorithm 1
and Algorithm 4 to achieve Õ(min{c(d, δ) · T , d · T 2/3 })strategic regret whenever T is unknown.
While the assumption of stochastically-chosen agents iswell-motivated in general, it may be overly restrictive insome specific settings. Our next result is an algorithm whichobtains Õ(T (d+1)/(d+2) ) strategic regret when agents arechosen adversarially (Algorithm 3). Algorithm 3 uses avariant of the popular Exp3 algorithm to trade off between
a carefully constructed set of (exponentially-many) policies (Auer et al., 2002a). As a result, it achieves sublinear
strategic regret when agents are chosen adversarially, but
requires an exponentially-large amount of computation at
every round. Finally, we note that while our primary settingof interest is that of one-sided feedback, all of our algorithms can be easily extended to the more general setting inwhich the principal receives bandit feedback at each round,i.e. rt (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 intersection of economics and computation on algorithmic decision-making
with incentives, under the umbrella of strategic classification or strategic learning (Hardt et al., 2016; Dong et al.,2018; Chen et al., 2020; Kleinberg and Raghavan, 2020;
Shavit et al., 2020; Ahmadi et al., 2021; Bechavod et al.,2019; 2022; Harris et al., 2021b; 2022b; 2021a; Ghalme
et al., 2021; Jagadeesan et al., 2021; Levanon and Rosenfeld, 2021; 2022; Harris et al., 2022a; Eilat et al., 2022;
Horowitz and Rosenfeld, 2023). In its most basic form, aprincipal makes either a binary or real-valued prediction
about a strategic agent, and receives full feedback (e.g., theagent’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 ourrunning example of hiring, full feedback would correspondto a company not offering an applicant a job, and yet still
getting to observe whether they would have been a good employee! As a result, such methods are not applicable in our
setting. Concurrent work (Chen et al., 2023) studies the effects of bandit feedback in the related problem of performative prediction (Perdomo et al., 2020), which considers data
distribution shifts at the population level in response to thedeployment of a machine learning model. In contrast, our focus is on strategic responses to machine learning models at
the individual level under apple tasting and bandit feedback.
Apple tasting and online learning Helmbold et al. (2000)
introduce the notion of apple-tasting feedback for online
learning. In particular, they study a binary prediction taskover “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., theapple is tasted). While we are the first to consider classification under incentives with apple tasting feedback, similar
feedback models have been studied in the context of algorithmic fairness (Bechavod et al., 2019), partial-monitoring
games (Antos et al., 2013), and recidivism prediction(Ensign et al., 2018). A related model of feedback is thatof contaminated controls (Lancaster and Imbens, 1996),
which considers learning from (1) a treated group whichcontains only treated members of the agent populationand (2) a “contaminated” control group with samples fromthe entire agent population (not just those under control).
Technically, our results are also related to a line of workin contextual bandits which shows that greedy algorithms
without explicit exploration can achieve sublinear regret
as long as the underlying context distribution is sufficiently
diverse (Raghavan et al., 2023; Bastani et al., 2021; Kannan
et al., 2018; Sivakumar et al., 2020; Raghavan et al., 2018).

Strategic Apple Tasting

Bandits and agents Finally, a complementary line of workto ours is that of Bayesian incentive-compatible (BIC) exploration in multi-armed bandit problems (Mansour et al.,2015; Hu et al., 2022; Sellke and Slivkins, 2021; Immorlica
et al., 2019; Ngo et al., 2021). Under such settings, the goalof the principal is to persuade a sequence of T agents withincentives to explore across several different actions withbandit feedback. In contrast, in our setting it is the principal,
not the agents, who is the one taking actions with partial
feedback. As a result there is no need for persuasion, but theagents now have an incentive to strategically modify their
behavior in order to receive a more desirable decision/action.

2. Setting and backgroundreadily extended to the setting in which agents best-respondwith a “trembling hand”, i.e. trembling hand tiebreaking.
Under this setting, we allow agents who strategicallymodify their contexts to “overshoot” the decision boundaryby some bounded amount, which can be either stochastic
or adversarially-chosen. See Appendix D for more details.
The principal observes x′t and plays action at = πt (x′t )according to policy πt . If at = 0, the principal receives
some known, constant reward rt (0) := r0 ∈ R. On theother hand, if the principal assigns action at = 1, we assume
that the reward the principal receives is linear in the agent’s
unmodified context, i.e.,rt (1) := ⟨θ (1) , xt ⟩ + ϵt(1)

We consider a game between a principal and a sequenceof T agents. Each agent is associated with a context
xt ∈ X ⊆ Rd , which characterizes their attributes (e.g.,a loan applicant’s credit history/report). At time t, theprincipal commits to a policy πt : X → {1, 0}, whichmaps from contexts to binary decisions (e.g., whether toaccept/reject the loan application). We use at = 1 to denotethe the principal’s positive decision at round t (e.g., agent
t’s loan application is approved), and at = 0 to denote anegative decision (e.g., the loan application is rejected).
Given πt , agent t best-responds by strategically modifying
their context within their effort budget as follows:

for some unknown θ (1) ∈ Rd , where ϵt is i.i.d. zero-mean
sub-Gaussian random noise with (known) variance σ 2 . Notethat rt (1) is observed only when the principal assigns action
at = 1, and not when at = 0. Following Helmbold et al.
(2000), we refer to such feedback as apple tasting (or onesided) feedback. Mapping to our lending example, the reward a bank receives for rejecting a particular loan applicant
is the same across all applicants, whereas their reward for apositive decision could be anywhere between a large, negative reward (e.g., if a loan is never repaid) to a large, positive
reward (e.g., if the loan is repaid on time, with interest).

Definition 2.1 (Agent best response; lazy tiebreaking).
Agent t best-responds to policy πt by modifying their context
according to the following optimization program.

The most natural measure of performance in our setting isthat of Stackelberg regret, which compares the principal’s
reward over T rounds with that of the optimal policy giventhat agents strategize.

x′t ∈ arg max
1{πt (x′ ) = 1}
′
x ∈X

′

s.t. ∥x − xt ∥2 ≤ δ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 arelazy when tiebreaking).
In other words, every agent wants to receive a positive
decision, but has only a limited ability to modify their(initial) context (represented by ℓ2 budget δ). Suchan 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., (Kleinberg andRaghavan, 2020; Harris et al., 2021b; Chen et al., 2020;
Bechavod et al., 2021)). We focus on linear thresholding
policies where the principal assigns action π(x′ ) = 1, if
and only if ⟨β, x′ ⟩ ≥ γ for some β ∈ Rd , γ ∈ R. We
refer to ⟨β, x′t ⟩ = γ 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 directionof β/∥β∥2 until the decision-boundary is reached (if it canindeed be reached). While we present our results for lazytiebreaking for ease of exposition, all of our results can be

Definition 2.2 (Stackelberg regret). The Stackelberg regretof a sequence of policies {πt }t∈[T ] on agents {xt }t∈[T ] is
X
XRegStackel (T ) :=rt (π̃ ∗ (x̃t )) −rt (πt (x′t ))t∈[T ]t∈[T ]

where x̃t is the best-response from agent t to policy π̃ ∗and π̃ ∗ is the optimal-in-hindsight 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 reward over T rounds withthat of the optimal policy had agents reported their contexts
truthfully.
Definition 2.3 (Strategic regret). The strategic regret of asequence of policies {πt }t∈[T ] on agents {xt }t∈[T ] is
X
X
Regstrat (T ) :=rt (π ∗ (xt )) −rt (πt (x′t ))t∈[T ]t∈[T ]

where π ∗ (xt ) = 1 if ⟨θ (1) , xt ⟩ ≥ r0 and π ∗ (xt ) = 0 o.w.
Proposition 2.4. Strategic regret is a stronger performance notion compared to Stackelberg regret, i.e.,
RegStackel (T ) ≤ Regstrat (T ).

Strategic Apple Tasting

Classification under agent incentives with apple tasting feedback
For t = 1, . . . , T :1. Principal publicly commits to a mapping πt : X → {1, 0}.
2. Agent t arrives with context xt ∈ X (hidden from the principal).
3. Agent t strategically modifies context from xt to x′t according to Definition 2.1.
4. Principal observes (modified) context x′t and plays action at = πt (x′t ).
5. Principal observes rt (1) := ⟨θ (1) , xt ⟩ + ϵt , if and only if at = 1.
Figure 1: Summary of our model.
Proof. The proof follows from the corresponding regret definitions and the fact that the principal’s reward is determinedby the original (unmodified) agent contexts.
X
X
RStackel (T ) :=rt (π̃ ∗ (x̃t )) −rt (πt (x′t ))t∈[T ]=

Xt∈[T ]∗rt (π̃ (x̃t )) −t∈[T ]+X

X

rt (π ∗ (xt ))t∈[T ]∗rt (π (xt )) −t∈[T ]Xrt (πt (x′t ))t∈[T ]≤ 0 + Rstrat (T )Because of Proposition 2.4, we focus on strategic regret,and use the shorthand Regstrat (T ) = Reg(T ) for the remainder of the paper. Strategic regret is a strong notion of
optimality, as we are comparing the principal’s performancewith 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 newalgorithmic ideas to solve, since the principal needs to assign actions to both (1) learn about θ (1) (which can only bedone when action 1 is assigned) and (2) maximize rewards
in order to achieve sublinear strategic regret. See Figure 1
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 rt (1) is defined as in Equation (1),rt (0) := ⟨θ (0) , xt ⟩ + ϵt and only rt (at ) is observed at eachtime-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, wee hides polylogarithmic factors, and that allnote that O(·)
proofs can be found in the Appendix.

3. Strategic classification with apple tasting
feedback
We now present our main results: provable guarantees foronline classification of strategic agents under apple tasting
feedback. Our results rely on the following assumption.

Assumption 3.1 (Bounded density ratio). Let fU d : X →R≥0 denote the density function of the uniform distribution over the d-dimensional unit sphere. We assume thatagent contexts {xt }t∈[T ] are drawn i.i.d. from a distribution
over the d-dimensional unit sphere with density function
f : X → R≥0 such that f f d(x)(x) ≥ c0 > 0, ∀x ∈ X .
UAssumption 3.1 is a condition on the initial agent contexts{xt }t∈[T ] , before they are strategically modified. Indeed,
one would expect the distribution over modified agent contexts to be highly discontinuous in a way that depends on
the sequence of policies deployed by the principal. Furthermore, none of our algorithms need to know the value ofc0 . As we will see in the sequel, this assumption allows us
to handle apple tasting feedback by relying on the inherent
diversity in the agent population for exploration; a growing
area of interest in the online learning literature (see references in Section 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. (2021) find that a greedy algorithm with no
explicit exploration achieved the second-best empirical performance across a large number of datasets when comparedto 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 a high level, our algorithm (formally stated in Algorithm 1) relies on three key ingredients:
1. A running estimate of θ (1) is used to compute a linear
policy, which separates agents who receive action 1
from those who receive action 0. Before deploying,
we shift the decision boundary by the effort budget δ
to account for the agents strategizing.
(1)b ) and
2. We maintain an estimate of θ (1) (denoted by θ
only updating it when at = 1 and we can ensure thatx′t = xt .

Strategic Apple Tasting

Algorithm 1 Strategy-Aware OLS with Apple Tastig Feedback (SA-OLS)
Assign action 1 for the first d rounds.
(1)
Set Dd+1 = {(xs , rs )}ds=1 .
For t = d + 1, . . . , T :b(1) using OLS and data Dt .
Estimate θ (1) as θ
t

(1)

(1)

b , x′ ⟩ ≥ δ · ∥θb ∥2 + r0 .
Assign action at = 1 if ⟨θ
t
t
t
(1)
(1)
′
b , x ⟩ > δ∥θb ∥2 + r0 :
If ⟨θ
t
t
t
Conclude that x′t = xt .
(1)
Dt+1 = Dt ∪ {(xt , rt )}Else:
Dt+1 = Dt

3. We assign actions “greedily” (i.e. using no explicit
exploration) w.r.t. the shifted linear policy.
Shifted linear policy If agents were not strategic, assigningb(1) , xt ⟩ ≥ r0 and action 0 otherwise would
action 1 if ⟨θtb(1) is ourbe a reasonable strategy to deploy, given that θt“best estimate” of θ (1) so far. Recall that the strategicallymodified context x′t is s.t., ∥x′t − xt ∥ ≤ δ. Hence, in Alb(1) ∥2 to accountgorithm 1, we shift the linear policy by δ∥θfor strategically modified contexts. Now, action 1 is onlyb(1) , xt ⟩ ≥ δ∥θb(1) ∥2 + r0 . This serves two
assigned if ⟨θtpurposes: (1) It makes it so that any agent with unmodifiedb(1) , x⟩ < r0 cannot receive action
context x such that ⟨θt
1, no matter how they strategize. (2) It forces some agentsb(1) , x⟩ < δ∥θb(1) ∥2 + r0
with contexts in the band r0 ≤ ⟨θtto strategize in order to receive action 1. This is the type ofstrategizing we want to incentivize. Estimating θ (1) After
playing action 1 for the first d rounds, Algorithm 1 forms
an initial estimate of θ (1) 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 andthus x′t = xt for t ≤ d. In future rounds, the algorithm’s
estimate of θ (1) is only updated whenever x′t lies strictlyon the positive side of the linear decision boundary. We callthese contexts clean, and can infer that x′t = xt due to thelazy tiebreaking assumption in Definition 2.1.
Condition 3.2 (Sufficient condition for x′ = x). Given ashifted linear policy parameterized by β (1) ∈ Rd , we saythat a context x′ is clean if ⟨β (1) , x′ ⟩ > δ∥β (1) ∥2 + r0 .
Greedy action assignment By assigning actions greedily
according to the current (shifted) linear policy, we arerelying 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
e T ) strategic
exploration is sufficient to achieve O(

regret under Assumption 3.1, albeit at the cost of an
exponentially-large (in d) constant which depends on theagents’ ability to manipulate (δ).
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 1 achieves the following
performance guarantee:


p
1
e
dσ 2 T log(4dT /γ)Reg(T ) ≤ O
c0 · c1 (d, δ) · c2 (d, δ)d/2
where c1 (d, δ) := Px∼U d (x[1] ≥ δ) ≥ Θ (1−δ)
ford2
sufficiently large d and c2 (d, δ) := Ex∼U d [x[2]2 |x[1] ≥3δ] ≥ 34 − 21 δ − 14 δ 2 , where x[i] denotes the i-th coordinate of a vector x.
Proof sketch. Our analysis begins by using properties ofthe strategic agents and shifted linear decision boundary
to upper-bound the per-round strategic regret for roundsb(1) − θ (1) ∥2 , i.e., ourt > d by a term proportional to ∥θtinstantaneous estimation error for θ (1) . Next we show thatPt
(1)
s=1 xs ϵs 1{Is }
(1)
(1)
2
b − θ ∥2 ≤
∥θ
Pt
t
(1)
⊤
λmin ( s=1 xs xs 1{Is })where λmin (M ) is the minimum eigenvalue of (symmetric)(1)b(1) , xs ⟩ ≥ δ∥θb(1) ∥2 + r0 } is thematrix M , and Is = {⟨θssevent that Algorithm 1 assigns action as = 1 and can verify
that x′s = xs . 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
Pt
(1)
that λmin ( s=1 xs x⊤
s 1{Is }) 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 formPt
(1)⊤
s=1 λmin (Es−1 [xs xs 1{Is }]), where Es−1 denotes
the expected value conditioned on the filtration up to times. Note that up until this point, we have only used the factthat contexts are drawn i.i.d. from a bounded distribution.
Using Assumption 3.1 on the bounded density ratio,(1)
we can lower bound λmin (Es−1 [xs x⊤
s 1{Is }]) by(1)
λmin (EU d ,s−1 [xs x⊤
s 1{Is }]), where the expectation istaken with respect to the uniform distribution over thed-dimensional ball. We then use properties of the uniform(1)
distribution to show that λmin (EU d ,s−1 [xs x⊤
s 1{Is }]) ≥O(c0 · c(d, δ)). Putting everything together, we get that√b(1) − θ (1) ∥2 ≤ (c0 · c(d, δ) · t)−1 with high probability.
∥θtP
Via a union bound and the fact that t∈[T ] √1t ≤ 2T ,√1ewe get that Reg(T ) ≤ O(
c0 ·c(d,δ) T ). Finally, we use
tools from high-dimensional geometry to lower bound theStrategic Apple Tasting

volume of a spherical cap and we show that for sufficiently
d/2
large d, c1 (d, δ) ≥ Θ (1−δ).
d2
3.1. High-dimensional contexts
While we typically think of the number of agents T as
growing and the context dimension d as constant in ourapplications of interest, there may be situations in which
T is either unknown or small. Under such settings, the1/c(d,δ) dependence in the regret bound (where c(d, δ) =c1 (d, δ) · c2 (d, δ)) may become problematic if δ is close to
1. This begs the question: “Why restrict the OLS estimator in Algorithm 1 to use only clean contexts (as definedin Condition 3.2)?” Perhaps unsurprisingly, we show in Apb(1) given by OLS will be inpendix B that the estimate θ
consistent if even a constant fraction of agents strategicallymodify their contexts. Given the above, it seems reasonable to restrict ourselves to learning procedures which onlyuse data from agents for which the principal can be surethat x′ = x. Under such a restriction, it is natural to ask
whether there exists some sequence of linear polices which
maximizes the number of points of the form (x′t , rt (1)) for
which the principal can be sure that x′t = xt . Again, theanswer is no:
Proposition 3.4. For any sequence of linear policies {β t }t ,the expected number of clean points is:X
Ex1 ,...,xT ∼U d 1{⟨xt , βt ⟩ > δ∥βt ∥2 } = c1 (d, δ)·Tt∈[T ]

when (initial) contexts are drawn uniformly from the ddimensional 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 c1 (d, δ) · T datapoints in expectation. Observe that this dependence on
c1 (d, δ) arises as a direct result of the agents’ ability to strategize. We remark that a similar constant often appears in the
regret analysis of BIC bandit algorithms (see Section 1.2).
Much like our work, (Mansour et al., 2015) find that theirregret rates depend on a constant which may be arbitrarily
large, depending on how hard it is to persuade agents to takethe principal’s desired action in their setting. The authors
conjecture that this dependence is an inevitable “price of
incentive-compatibility”. 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 isoften unclear how strategic agents would behave in such settings, both in theory (Definition 2.1 would require agents tosolve a non-convex optimization with potentially no closedform solution) and in practice, making the analysis of such
nonlinear policies difficult in strategic settings.We conclude

Algorithm 2 Strategy-aware online classification with unknown time horizon
Compute switching time τ ∗ = g(d, δ)Let τ0 = 1
For i = 1, 2, 3, . . .
LetPτi = 2 · τi−1
i
If j=1 τj < τ ∗ : Run Algorithm 4 with time horizon τiand failure probability 1/τi2
Else: Break and run Algorithm 1 for the remaining rounds
this section by showing that polynomial dependence on d is
e 2/3 ) strategic regret. Specifically,
possible, at the cost of O(Twe provide an algorithm (Algorithm 2) which obtains thefollowing regret guarantee whenever T is small or unknown,
which uses Algorithm 1 and a variant of the explore-thencommit algorithm (Algorithm 4) as subroutines:
Theorem 3.5 (Informal; details in Theorem B.13). Algorithm 2 incurs expected strategic regret



√
d5/2
2/3
e
E[Reg(T )] = O min· T,d · T,
(1 − δ)d/2
where the expectation is taken with respect to the sequenceof contexts {xt }t∈[T ] and random noise {ϵt }t∈[T ] .
The algorithm proceeds by playing a “strategy-aware”
variant of explore-then-commit (Algorithm 4) with adoubling trick until the switching time τ ∗ = g(d, δ) isreached. Note that g(d, δ) is a function of both d and δ, not
c0 . If round τ ∗ is indeed reached, the algorithm switches
over to Algorithm 1 for the remaining rounds.
Extension to bandit feedback Algorithm 1 can be extended
to handle bandit feedback by explicitly keeping track of anb(0) of θ (0) via OLS, assigning action at = 1 if
estimate θb(1) − θb(0) , x′ ⟩ ≥ δ · ∥θb(1) − θb(0) ∥2 , and updatand only if ⟨θ
t
t
t
t
t
b(0) whenever at = 0 (since agents
ing the OLS estimate of θ
will not strategize to receive action 0). Algorithm 2 may be
extended to bandit feedback by “exploring” for twice as longin Algorithm 4, in addition to using the above modifications.
In both cases, the strategic regret rates are withing a constantfactor of the rates obtained in Theorem 3.3 and Theorem 3.5.

4. Beyond stochastic contexts
In this section, we allow the sequence of initial agent
contexts to be chosen by an (oblivious) adversary. Thisrequires new algorithmic ideas, as the regression-based algorithms of Section 3 suffer linear strategic regret under thisadversarial setting. Our algorithm (Algorithm 3) is based on
the popular EXP3 algorithm (Auer et al., 2002b). At a highlevel, Algorithm 3 maintains a probability distribution over“experts”, i.e., a discretized grid E over carefully-selected
policies. In particular, each grid point e ∈ E ⊆ Rd

Strategic Apple Tasting

Algorithm 3 EXP3 with strategy-aware experts (EXP3SAE)
Create set of discretized policies e ∈ E = [(1/ε)d ], where
ε = (dσ log(T )/T )1/(d+2)
q .

log(|E|)Set parameters η =T λ2 |E| , γ = 2ηλ|E|, and λ =√σ 2 log T .
Initialize probability distribution pt (e) = 1/|E|, ∀e ∈ E.
For t ∈ [T ] :Choose policy et from probability distribution qt (e) =γ(1 − γ) · pt (e) + |E|.
Observe x′t .
Play action at,et = 1 if ⟨et , x′t ⟩ ≥ δ∥et ∥2 . Otherwise play
action at,et = 0.
Observe reward rt (at,et ).
Update loss estimator for each policy e ∈ E: ℓbt (e) =(1 + λ − rt (at,et )) · 1{e = et }/qt (e).
Updatedistribution ∀e ∈ E: pt+1 (e) ∝ pt (e) · probabilitybexp −η ℓt (e) .

represents an “estimate” of θ (1) , and corresponds to a slope
vector which parameterizes a (shifted) linear threshold
threshold policy, like the ones considered in Section 3. We
use at,e to refer to the action played by the principal at timet, had they used the linear threshold policy parameterized
by expert e. At every time-step, (1) the adversary chooses
an agent xt , (2) a slope vector et ∈ E is selected according
to the current distribution, (3) the principal commits toassigning action 1 if and only if ⟨et , x′t ⟩ ≥ δ∥et ∥2 , (4) theagent strategically modifies their context xt → x′t , and (5)the principal assigns an action at according to the policy andreceives the associated reward rt (at ) (under apple tasting
feedback). Algorithm EXP4, which maintains a distribution
over experts and updates the loss of all experts based on thecurrent action taken, is not directly applicable in our setting
as the strategic behavior of the agents prevents us from inferring the loss of each expert at every time-step (Auer et al.,2002a). This is because if x′t ̸= xt under the thresholding
policy associated with expert e), it is generally not possible
to “back out” xt given x′t , which prevents us from predicting
the counterfactual context the agent would have modified to
had the principal been using expert e′ instead. As a result,
we use a modification of the standard importance-weighted
loss estimator to update the loss of only the policy played by
the algorithm (and therefore the distribution over policies).
Our regret guarantees for Algorithm 3 are as follows:
Theorem 4.1 (Informal; detailed version in Theorem C.1).
Algorithm 3 incurs expected strategic regret E[Reg(T )] =e (d+1)/(d+2) ).
O(TProof sketch. The analysis is broken down into two parts. In
the first part, we bound the regret w.r.t. the best policy on thegrid. In the second, we bound the error incurred for playing
policies on the grid, rather than the continuous space ofpolicies. We refer to this error as the Strategic Discretization
Error (SDE(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 obtainedby at, by a factor of 1 + λ, where λ is a (tunable) parameterof the algorithm. This shifting (which does not affect the
regret, since all the losses are shifted by the same fixedamount) guarantees that the losses at each round are nonnegative and bounded with high probability. Technically,
this requires bounding the tails of the subgaussian of thenoise parameters ϵt .
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 ℓ2 distance, depending on theagent’s initial context. Our analysis proceeds with a caseby-case basis. Consider the best expert e∗ in the grid. If
at,e∗ = π ∗ (xt ) (i.e., the action of the best expert matches
that of the optimal policy), there is no discretization error inround t. Otherwise, if at,e∗ ̸= π ∗ (xt ), we show that the perround SDE is upper-bounded by a term which looks liketwice the discretization upper-bound for the non-strategic
setting, plus an additional term. We show that this additionalterm must always be non-positive by considering two subcases (at,e∗ = 1, π ∗ (xt ) = 0 and at,e∗ = 0, π ∗ (xt ) = 1)
and using properties about how agents strategize against the
deployed algorithmic policies.
Computational complexity While both Algorithm 1 and Algorithm 2 have O(d3 ) per-iteration computational complexity, Algorithm 3 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. Weview the design of computationally efficient algorithms foradversarially-chosen contexts as an important direction for
future research.
Extension to bandit feedback Algorithm 3 may be extended to the bandit feedback setting by maintaining a grid
over estimates of θ (1) − θ (0) (instead of over θ (1) ).

5. Conclusion
We study the problem of classification under incentives withapple tasting feedback. Such one-sided feedback is often
what is observed in real-world strategic settings including
lending and hiring. Our main result√ is a “greedy” algorithme T ) strategic regret when
(Algorithm 1) which achieves O(
the initial agent contexts are generated stochastically. The
regret of Algorithm 1 depends on a constant c1 (d, δ) whichscales exponentially in the context dimension, which may

Strategic Apple Tasting

be problematic in settings for which the number of agents issmall or unknown. To address this, we provide an algorithm(Algorithm 2) which combines Algorithm 1 with a strategyaware version of the explore-then-commit√ algorithm usingdT
2/3
ea doubling trick to achieve O(min{})
c1 (d,δ) , d · T
expected strategic regret whenever T is unknown. Finally,
we relax the assumption of stochastic contexts and allow
for contexts to be generated adversarially. Algorithm 3
e d+1d+2 ) expected strategic regret wheneverachieves O(Tagent contexts are generated adversarially by running
EXP3 over a discretized grid of strategy-aware policies, but
has exponential-in-d per-round computational complexity.
All of our results also apply to the more general settingof bandit feedback, under slight modifications to thealgorithms. There are several directions for future work:
Unclean data The regret of Algorithm 1 depends on a 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 inconsistentestimator, 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-chosen agent contexts suffers exponential-in-d per-round computational complexity,
which makes it unsuitable for use in settings with highdimensional 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 toextend our algorithms for strategic learning under bandit
feedback to the setting in which the principal has three ormore actions at their disposal. While prior work (Harris
et al., 2022a) 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.

References
Algorithmic hiring: Complex hiring by numbers?
URL
https://hiring.monster.com/
resources/recruiting-strategies/
workforce-planning/
hiring-algorithms/.
Using white font on a cv to trick ats.
URL
https://www.thecvstore.net/blog/
cv-ats-white-font/#:~:text=Even%
20if%20you%20get%20past,harm%20your%20future%20employment%20prospects.
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah
Naggita. The strategic perceptron. In Proceedings of the
22nd ACM Conference on Economics and Computation,
pages 6–25, 2021.
András Antos, Gábor Bartók, Dávid Pál, and Csaba
Szepesvári. Toward a classification of finite partialmonitoring games. Theoretical Computer Science, 473:
77–99, 2013.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, andRobert E. Schapire. The nonstochastic multiarmed bandit
problem. SIAM Journal of Computing, 32:48–77, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, andRobert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77,
2002b.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi.
Mostly exploration-free algorithms for contextual bandits.
Management Science, 67(3):1329–1349, 2021. doi: 10.
1287/mnsc.2020.3605. URL https://doi.org/10.
1287/mnsc.2020.3605.
Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, and Steven Z Wu. Equal opportunity in online
classification with partial feedback. Advances in Neural
Information Processing Systems, 32, 2019.
Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani.
Gaming helps! learning from strategic interactions innatural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234–1242. PMLR,
2021.
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.
Jillian Berman. Do ai-powered lending algorithms silently
discriminate? this initiative aims to find out, Nov 2021.
URL https://www.marketwatch.com/story/

Strategic Apple Tasting

do-ai-powered-lending-algorithms-silently-discriminate-this-initiative\
Keegan Harris, Anish Agarwal, Chara Podimata, and-aims-to-find-out-11637246524.
Zhiwei Steven Wu. Strategyproof decision-making
in panel data settings and beyond. arXiv preprint
Alberto Bietti, Alekh Agarwal, and John Langford. A conarXiv:2211.14236, 2022a.
textual bandit bake-off. The Journal of Machine Learning
Keegan Harris, Dung Daniel T Ngo, Logan Stapleton, Hoda
Research, 22(1):5928–5976, 2021.
Heidari, and Steven Wu. Strategic instrumental variable
Avrim Blum, John Hopcroft, and Ravindran Kannan. Founregression: Recovering causal relationships from stratedations of data science. Cambridge University Press,
gic responses. In International Conference on Machine
2020.
Learning, pages 8502–8522. PMLR, 2022b.
Yatong Chen, Wei Tang, Chien-Ju Ho, and Yang Liu. Performative prediction with bandit feedback: Learning throughreparameterization. arXiv preprint arXiv:2305.01094,
2023.
Yiling Chen, Yang Liu, and Chara Podimata. Learning
strategy-aware linear classifiers. Advances in Neural
Information Processing Systems, 33:15265–15276, 2020.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classificationfrom revealed preferences. In Proceedings of the 2018
ACM Conference on Economics and Computation, pages
55–70, 2018.
Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks.
arXiv preprint arXiv:2205.15765, 2022.
Christian Eilers. Resume keywords: List by industry [foruse to pass the ats], Jan 2023. URL https://zety.
com/blog/resume-keywords.
Danielle Ensign, Sorelle A Friedler, Scott Nevlle, Carlos
Scheidegger, and Suresh Venkatasubramanian. Decision
making with limited feedback: Error bounds for predictive policing and recidivism prediction. In Proceedingsof Algorithmic Learning Theory,, volume 83, 2018.
Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal TalgamCohen, and Nir Rosenfeld. Strategic classification in thedark. In International Conference on Machine Learning,
pages 3672–3681. PMLR, 2021.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou,
and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations intheoretical computer science, pages 111–122, 2016.
Keegan Harris, Valerie Chen, Joon Sik Kim, Ameet Talwalkar, Hoda Heidari, and Zhiwei Steven Wu. Bayesian
persuasion for algorithmic recourse. arXiv preprint
arXiv:2112.06283, 2021a.
Keegan Harris, Hoda Heidari, and Steven Z Wu. Statefulstrategic regression. Advances in Neural Information
Processing Systems, 34:28728–28741, 2021b.

David P Helmbold, Nicholas Littlestone, and Philip M Long.
Apple tasting. Information and Computation, 161(2):85–
139, 2000.
Guy Horowitz and Nir Rosenfeld. Causal strategic
classification: A tale of two shifts. arXiv preprint
arXiv:2302.06280, 2023.
Xinyan Hu, Dung Ngo, Aleksandrs Slivkins, and Steven Z
Wu. Incentivizing combinatorial bandit exploration. Advances in Neural Information Processing Systems, 35:37173–37183, 2022.
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, andZhiwei Steven Wu. Bayesian exploration with heterogeneous agents. In The world wide web conference, pages
751–761, 2019.
Meena Jagadeesan, Celestine Mendler-Dünner, and Moritz
Hardt. Alternative microfoundations for strategic classification. In International Conference on Machine Learning,
pages 4687–4697. PMLR, 2021.
Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of thegreedy algorithm for the linear contextual bandit problem.
In Proceedings of the 32nd International Conference on
Neural Information Processing Systems, NIPS’18, page
2231–2241, Red Hook, NY, USA, 2018. Curran Associates Inc.
Jon Kleinberg and Manish Raghavan. How do classifiers
induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1–23, 2020.
Tony Lancaster and Guido Imbens. Case-control studies
with contaminated controls. Journal of Econometrics, 71(1-2):145–160, 1996.
Sagi Levanon and Nir Rosenfeld. Strategic classification
made practical. In International Conference on Machine
Learning, pages 6243–6253. PMLR, 2021.
Sagi Levanon and Nir Rosenfeld. Generalized strategic
classification and the case of aligned incentives. In International Conference on Machine Learning, pages 12593–
12618. PMLR, 2022.

Strategic Apple Tasting

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.
Daniel Ngo, Logan Stapleton, Vasilis Syrgkanis, and Zhiwei Steven Wu. Incentivizing bandit exploration: Recommendations as instruments. In forthcoming) Proceedingsof the 2021 International Conference on Machine Learning (ICML’21), 2021.
Bev O’Shea.
9 ways to build and improveyour credit fast, Nov 2022.
URL https://www.nerdwallet.com/article/finance/
raise-credit-score-fast.
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner,and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599–
7609. PMLR, 2020.
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://proceedings.
mlr.press/v75/raghavan18a.html.
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits.
SIAM Journal on Computing, 52(2):487–524, 2023. doi:
10.1137/19M1247115. URL https://doi.org/10.
1137/19M1247115.
Mark Sellke and Aleksandrs Slivkins. The price of incentivizing exploration: A characterization via thompson
sampling and sample complexity. In Proceedings of the
22nd ACM Conference on Economics and Computation,
pages 795–796, 2021.
Ohad Shamir.
A variant of azuma’s inequality formartingales with subgaussian tails. arXiv preprint
arXiv:1110.2392, 2011.
Yonadav Shavit, Benjamin Edelman, and Brian Axelrod.
Causal strategic linear regression. In International Conference on Machine Learning, pages 8676–8686. PMLR,
2020.
Vidyashankar Sivakumar, Zhiwei Steven Wu, and Arindam
Banerjee. Structured linear contextual bandits: A

sharp and geometric smoothed analysis. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine
Learning Research, pages 9026–9035. PMLR, 2020.
URL http://proceedings.mlr.press/v119/
sivakumar20a.html.
Joel A Tropp. User-friendly tail bounds for sums of randommatrices. Foundations of computational mathematics, 12:
389–434, 2012.

Strategic Apple Tasting

A. Useful concentration inequalities
Theorem A.1 (Matrix Azuma, Tropp (2012)). Consider a self-adjoint matrix martingale {Ys : s = 1, . . . , t} in dimension d,and let {Xs }s∈[t] be the associated difference sequence satisfying Es−1 Xs = 0d×d and Xs2 ⪯ A2s for some fixed sequence{As }s∈[t] of self-adjoint matrices. Then for all α > 0,
P (λmax (Yt − EYt ) ≥ α) ≤ d · exp(−α2 /8σ 2 ),where σ 2 :=Pt

2
s=1 As.
2

Theorem A.2 (A variant of Azuma’s inequality for martingales with subgaussian tails, Shamir (2011)). Let Z1 , Z2 , . . . Zt
be a martingale difference sequence with respect to a sequence W1 , W2 , . . . , Wt , and suppose there are constants b > 1,
c > 0 such that for any s and any α > 0, it holds thatmax{P(Zs > α|X1 , . . . , Xs−1 ), P(Zs < −α|X1 , . . . , Xs−1 )} ≤ b · exp(−cα2 ).
Then for any γ > 0, it holds with probability 1 − γ that
t
X

r
Zs ≤

s=1

28b log(1/γ).
cT

B. Proofs for Section 3
B.1. Proof of Theorem 3.3
Theorem B.1. Let fU d : X → R≥0 denote the density function of the uniform distribution over the d-dimensional
unit sphere. If agent contexts are drawn from a distribution over the d-dimensional unit sphere with density function
f : X → R≥0 such that f f d(x)(x) ≥ c0 > 0, ∀x ∈ X , then Algorithm 1 achieves the following performance guarantee:
U

Reg(T ) ≤ 4d +p
814dσ 2 T log(4dT /γ)
c0 · c1 (δ, d) · c2 (δ, d)with probability 1 − γ, where 0 < c1 (δ, d) := Px∼U d (x[1] ≥ δ) and 0 < c2 (δ, d) := Ex∼U d [x[2]2 |x[1] ≥ δ].
Proof. We start from the definition of strategic regret. Note that under apple tasting feedback, θ (0) = 0.
Reg(T ) :=

T D
X

∗

θ (at ) − θ (at ) , xt

E

t=1

=

T D
E D ∗
E D (at )
E
X
(a∗
(at )
(a∗
t)
t)
θ̂ t − θ̂ t , xt + θ (at ) − θ̂ t , xt + θ̂ t − θ (at ) , xt
t=1

T D
E
D
E
X
(1)
(0)
≤
θ (1) − θ̂ t , xt + θ (0) − θ̂ t , xt
t=1

≤

T
X

(1)

θ (1) − θ̂ t

t=1

≤ 2d +

T
X

(0)

2

∥xt ∥2 + θ (0) − θ̂ t(1)

θ (1) − θ̂ t

t=2d+12∥xt ∥2(0)

2+ θ (0) − θ̂ t2where 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 is at most 2 andq
we use the first d rounds to√PTbootstrap our OLS. The result follows by Lemma B.3, a union bound, and the fact that d+1 1t ≤ 2 T .
Lemma B.2.

(a∗
t)

b
⟨θ
t

(at )

b
−θ
t

, xt ⟩ ≤ 0

Strategic Apple Tastingb(1) − θb(0) , x′ ⟩ − δ∥θb(1) − θb(0) ∥2 ≥ 0
Proof. If at = a∗t , the condition is satisfied trivially. If at ̸= a∗t , then either (1) ⟨θ
t
t
t
t
t
b(1) − θb(0) , x′ ⟩ − δ∥θb(1) − θb(0) ∥2 < 0 and ⟨θ (1) − θ (0) ⟩ ≥ 0.
and ⟨θ (1) − θ (0) ⟩ < 0 or (2) ⟨θ
t

t

t

t

t

b(1) − θb(0) , x′ ⟩ − δ∥θb(1) − θb(0) ∥2 ≥ 0 and ⟨θ (1) − θ (0) ⟩ < 0. (a∗ = 0, at = 1)
Case 1: ⟨θ
t
t
t
t
t
t
By Definition 2.1, we can rewriteb(1) − θb(0) , x′ ⟩ − δ∥θb(1) − θb(0) ∥2 ≥ 0
⟨θ
t
t
t
t
t
as

(1)

(0)

(1)

(0)

b −θ
b , xt ⟩ + (δ ′ − δ)∥θb −θb ∥2 ≥ 0⟨θttttb(1) − θb(0) ∥2 ≤ 0, ⟨θb(1) − θb(0) , xt ⟩ ≥ 0 must hold.
for some δ ′ ≤ δ. Since (δ ′ − δ)∥θttttb(1) − θb(0) , x′ ⟩ − δ∥θb(1) − θb(0) ∥2 < 0 and ⟨θ (1) − θ (0) ⟩ ≥ 0. (a∗ = 1, at = 0)Case 2: ⟨θ
t
t
t
t
t
t
b(1) − θb(0) , xt ⟩ < 0.
Since modification did not help agent t receive action at = 1, we can conclude that ⟨θtt

Lemma B.3. Let fU d : X → R≥0 denote the density function of the uniform distribution over the d-dimensional unit
sphere. If T ≥ d and agent contexts are drawn from a distribution over the d-dimensional unit sphere with density function
f : X → R≥0 such that f f d(x)(x) ≥ c0 ∈ R>0 , ∀x ∈ X , then the following guarantee holds under apple tasting feedback.
U

∥θ

(1)

(1)
− θ̂ t+1 ∥2 ≤2c0 · c1 (δ, d) · c2 (δ, d)r

14dσ 2 log(2d/γt )twith probability 1 − γt .
(1)

(1)

(1)

(1)

= {⟨θ̂ s , xs ⟩ ≥ δ∥θ̂ s ∥2 + r0 }. Then, from the definition of θ t+1 we have:
!−1 t
t
X
X
(1)
⊤
(1)
xs rs (1)1{Is(1) }(closed form solution of OLS)θ̂ t+1 :=xs xs 1{Is }Proof. Let Is

s=1

s=1

=

t
X

!−1

(1)
xs x⊤
s 1{Is }=θ

(1)
xs (x⊤+ ϵs )1{Is(1) }s θ(plug in rs (1))

s=1

s=1
(1)

t
X

+

t
X

xs x⊤
s

1

!−1
{Is(1) }t
Xxs ϵs 1{Is(1) }

s=1

s=1

Re-arranging the above and taking the ℓ2 norm on both sides we get:
!−1 t
t
X
X
(1)
(1)
⊤
(1)
θ − θ̂ t+1 =xs xs 1{Is }xs ϵs 1{Is(1) }
2

s=1

≤

t
X

s=1

!−1

(1)
xs x⊤
s 1{Is }

s=1

2

1

(1)
s=1 xs ϵs {Is }

Pt
=

P

σmin
Pt

t
⊤
s=1 xs xs

s=1 xs ϵs

=
λmin

P

2
t
X
s=1

xs ϵs 1{Is(1) }(Cauchy-Schwarz)
22

1{Is(1) }1{Is(1) }t⊤
s=1 xs xs

1

2 
(1)
{Is }

where for a matrix M , σmin is the smallest singular value σmin (M ) := min∥x∥=1 ∥M x∥ and λmin is the smallest eigenvalue.
Pt(1)Note that the two are equal since the matrix s=1 xs x⊤
s 1{Is } is PSD as the sum 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.

Strategic Apple Tasting

Lemma B.4. The following bound holds on the ℓ2 -norm oftX

xs ϵs 1{Is(1) }

s=1

Pt

s=1 xs ϵs1{Is(1) } with probability 1 − γt :p
≤ 2 14dσ 2 t log(d/γt )
2

Pt
(1)
Proof. Let x[i] denote the i-th coordinate of a vector x. Observe that s=1 ϵs xs [i]1{Is } is a sum of martingale
Ps
(1)
(1)
differences with Zs := ϵs xs [i]1{Is }, Xs := s′ =1 ϵs′ xs′ [i]1{Is′ }, andmax{P(Zs > α|X1 , . . . , Xs−1 ), P(Zs < −α|X1 , . . . , Xs−1 )} ≤ exp(−α2 /2σ 2 ).
By Theorem A.2,tX

ϵs xs [i]1{Is(1) } ≤ 2

p
14σ 2 t log(1/γi )s=1with probability 1 − γi . The desired result follows via a union bound and algebraic manipulation.

Lemma B.5. The following bound holds on the minimum eigenvalue of

λmin

t
X

xs x⊤
s

1

s=1

!
{Is(1) }≥Pt⊤
s=1 xs xs1{Is(1) } with probability 1 − γt :pt
+ 4 2t log(d/γt )c0 · c1 (δ, d) · c2 (δ, d)

Proof.

λmin

t
X

xs x⊤
s

1

!
{Is(1) }s=1≥ λmin≥ λmin

t
X
s=1
t
X

xs x⊤
s

1

{Is(1) } − Es−1 [xs x⊤s1!
{Is(1) }]+ λmintX

Es−1 [xs x⊤s1!
{Is(1) }]

s=1

xs x⊤
s

s=1

1

{Is(1) } − Es−1 [xs x⊤s1!
{Is(1) }]

+

t
X



(1)
λmin Es−1 [xs x⊤
s 1{Is }]

(2)

s=1

where the inequalities follow from the fact that λmin (A + B) ≥ λmin (A) + λmin (B) for two Hermitian matrices A,
Pt
(1)
(1)
⊤
B. Note that the outer products form Hermitian matrices. Let Yt := s=1 xs x⊤
s 1{Is } − Es−1 [xs xs 1{Is }]. Note(1)2that by the tower rule, EYt = EY0 = 0. Let −Xs := Es−1 [xs x⊤
s 1{Is }], then Es−1 [−Xs ] = 0, and (−Xs ) ⪯ 4Id .
By Theorem A.1,
P(λmax (−Yt ) ≥ α) ≤ d · exp(−α2 /32t).
Since −λmax (−Yt ) = λmin (Yt ),P(λmax (Yt ) ≤ α) ≤ d · exp(−α2 /32t).
p
Therefore, λmin (Yt ) ≥ 4 2t log(d/γt ) with probability 1 − γt . We now turn our attention to lower bounding(1)
λmin (Es−1 [xs x⊤
s 1{Is }]).

Strategic Apple Tasting(1)(1)
ω ⊤ Es−1 [xs x⊤
λmin (Es−1 [xs x⊤
s 1{Is }]ω
s 1{Is }]) := minω∈S d−1Z(1)= min ω ⊤
xs x⊤
1
{I
}f
(x
)dx
ω
s
s
s
s
ω∈S d−1ZfU d (xs )
(1)
xs x⊤
1
{I
}f
(x
)
·
= min ω ⊤
dx
ω
s
s
s
s
f (xs )
ω∈S d−1(1)≥ c0 · min ω ⊤ Es−1,U d [xs x⊤
s 1{Is }]ω
ω∈S d−1b , xs ⟩ ≥ δ∥βb ∥2 )
b , xs ⟩ ≥ δ∥βb ∥2 ] · Ps−1,U d (⟨β= c0 min Es−1,U d [⟨ω, xs ⟩2 |⟨βssssω∈S d−1|{z}c1 (δ,d)b , xs ⟩ ≥ δ∥βb ∥2 ]= c0 · c1 (δ, d) min Es−1,U d [⟨ω, xs ⟩2 |⟨β
s
s

(3)

ω∈S d−1

Throughout the remainder of the proof, we surpress the dependence on U d and note that unless stated otherwise, allb /∥βb ∥2 .
expectations are taken with respect to U d . Let Bs ∈ Rd×d be the orthonormal matrix such that the first column is β
s
s
d
b
b
Note that Bs e1 = β s /∥β s ∥2 and Bs x ∼ U .
⊤ bbb
Es−1 [xs x⊤s |⟨β s , xs ⟩ ≥ δ∥β s ∥] = Es−1 [(Bs xs )(Bs xs ) |⟨β s , Bs xs ⟩ ≥ δ]b ∥2 Bs e1 ≥ δ · ∥βb ∥2 ]B ⊤= Bs Es−1 [xs x⊤ |x⊤ B ⊤ ∥β
s

s

s

s

s

s

⊤
= Bs Es−1 [xs x⊤
s |xs [1] ≥ δ]Bs

Observe that for j ̸= 1, i ̸= j, E[xs [j]xs [i]|xs [1] ≥ δ] = 0. Therefore,2bbEs−1 [xs x⊤s |⟨β s , xs ⟩ ≥ δ∥β s ] = Bs (E[xs [2] |xs [1] ≥ δ]Id⊤
+ (E[xs [1]2 |xs [1] ≥ δ] − E[xs [2]2 |xs [1] ≥ δ])e1 e⊤1 )Bs= E[xs [2]2 |xs [1] ≥ δ]Idbβs
+ (E[xs [1]2 |xs [1] ≥ δ] − E[xs [2]2 |xs [1] ≥ δ])
b ∥2
∥β
s

and

(1)
λmin (Es−1 [xs x⊤
s 1{Is }]) ≥ c0 · c1 (δ, d) minω∈S d−1

b
β
s
b ∥2
∥β

!⊤

s

E[xs [2]2 |xs [1] ≥ δ]∥ω∥2*bβs+ (E[xs [1] |xs [1] ≥ δ] − E[xs [2] |xs [1] ≥ δ]) ω,
b
∥β ∥2
2

2

+2
)

s

≥ c0 · c1 (δ, d) · c2 (δ, d)Lemma B.6. For sufficiently large values of d,
c1 (δ, d) ≥ Θ(1 − δ)d/2d
.

Proof. Lemma B.6 is obtained via a similar argument to Theorem 2.7 in Blum et al. (2020). As in Blum et al. (2020), weare interested in the volume of a hyperspherical cap. However, we are interested in a lower-bound, not an upper-bound(as√cis the case in (Blum et al., 2020)). Let A denote the portion of the d-dimensional hypersphere with x[1] ≥ d−1 and let H
denote the upper hemisphere.
vol(A)c1 (δ, d) := Px∼U d (x[1] ≥ δ) =vol(H)

Strategic Apple Tasting

In order to lower-bound c1 (δ, d), it suffices to lower bound vol(A) and upper-bound vol(H). In what follows, let V (d)denote the volume of the d-dimensional hypersphere with radius 1.
Lower-bounding vol(A): As in (Blum et al., 2020), to calculate the volume of pA, we integrate an incremental volume thatis a disk of width dx[1] and whose face is a ball of dimension d − 1 and radius 1 − x[1]2 . The surface area of the disk isd−1(1 − x[1]2 ) 2 V (d − 1) and the volume above the slice x[1] ≥ δ is
Z 1
vol(A) =d−1(1 − x[1]2 ) 2 V (d − 1)dx[1]δTo get a lower bound on the integral, we use the fact that 1 − x2 ≥ 1 − x for x ∈ [0, 1]. The integral now takes the form
Z 1

d−1

(1 − x[1]) 2 V (d − 1)dx[1] =vol(A) ≥δd+1
V (d − 1)· 2(1 − δ) 2
d+1

Upper-bounding vol(H): We can obtain an exact expression for vol(H) in terms of V (d − 1) using the recursive
relationship between V (d) and V (d − 1):√1
π Γ( d2 + 12 )vol(H) = V (d) =V (d − 1)22 Γ( d2 + 1)
Plugging in our bounds for vol(A), vol(H) and simplifying, we see thatd+1

(1 − δ) 2 Γ( d2 + 1)
c1 (δ, d) ≥ √=Θπ(d + 1) Γ( d2 + 21 )d+1

(1 − δ) 2
d+1!

where the equality follows from Stirling’s approximation.
Lemma B.7. The following bound holds on c2 (δ, d):c2 (δ, d) ≥

1
3d



3 1
1
− δ − δ2
4 2
4

3
.

Proof. We begin by computing E[x[2]2 |x[1] = δ ′ ], for δ ′ ∈ (0, 1). If x[1] = δ ′ , then x[2]2 + . . . + x[d]2 ≤ 1 − (δ ′ )2 .
Using this fact, we see thatE[x[2]2 |x[1] = δ ′ ] =1
1Er∼U nif [0,1−(δ′ )2 ] [r2 ] =(1 − (δ ′ )2 )3 .
d
3dSince E[x[2]2 |x[1] ≥ δ] ≥ E[x[2]2 |x[1] = δ + 1−δ
2 ],



3
1 3 1
1
δ+1
=
− δ − δ2
E[x[2]2 |x[1] ≥ δ] ≥ E x[2]2 |x[1] =2
3d 4 24

B.2. Proof of Proposition 3.4
Proposition B.8. For any sequence of linear threshold policies β 1 , . . . , β T ,Ex1 ,...,xT ∼U d

" T
X
t=1

#

1{⟨xt , βt ⟩ ≥ δ∥βt ∥2 } = T · Px∼U d (x[1] ≥ δ)Strategic Apple Tasting

Algorithm 4 Explore-Then-Commit
Input: Time horizon T , failure probability γ
Set T0 according to Theorem B.9
Assign action 1 for the first T0 rounds(1)

Estimate θ (1) as θ̂ T0 via OLS
For t = T0 + 1, . . . , T :
(1)

(1)

Assign action at = 1 if ⟨θ̂ T0 , xt ⟩ ≥ δ · ∥θ̂ T0 ∥2 and action at = 0 otherwise

Proof. Let Bt ∈ Rd×d be the orthonormal matrix such that the first column is β t /∥β t ∥2 . Note that Bt x ∼ U d if x ∼ U d
and Bt e1 = β t /∥β t ∥2 .

Ex1 ,...,xT ∼U d [TX1{⟨xt , βt ⟩ ≥ δ∥βt ∥2 }] =

t=1

T
X

Pxt ∼U d (⟨xt , β t ⟩ ≥ δ∥β t ∥2 )

t=1

=

T
X

Pxt ∼U d (⟨Bt xt , β t ⟩ ≥ δ∥β t ∥2 )

t=1

=

T
X

⊤
Pxt ∼U d (x⊤t Bt ∥β t ∥2 Bt e1 ≥ δ∥β t ∥2 )

t=1

=

T
X

Pxt ∼U d (x⊤t Id e1 ≥ δ∥2 )t=1= T · Px∼U d (x[1] ≥ δ∥2 )B.3. Explore-Then-Commit Analysis
Theorem B.9. Let fU d : X → R≥0 denote the density function of the uniform distribution over the d-dimensional
unit sphere. If agent contexts are drawn from a distribution over the d-dimensional unit sphere with density function
f : X → R≥0 such that ffU(x)(x) ≥ c0 > 0, ∀x ∈ X , then Algorithm 4 achieves the following performance guarantee

RegETC (T ) ≤8 · 631/3 2/3 2/3dσ T
log1/3 (4d/γ)
c0with probability 1 − γ if T0 := 4 · 631/3 σ 2/3 dT 2/3 log1/3 (4d/γ).

Strategic Apple Tasting

Proof.

RegETC (T ) :=TX∗

⟨θ (at ) − θ (at ) , xt ⟩t=1

≤ T0 +TX∗⟨θ (at ) − θ (at ) , xt ⟩t=1

= T0 +

T
X

(a∗
t)

(at )

(a∗
t)

∗

(at )

⟨θ̂ T0 /2 − θ̂ T0 /2 , xt ⟩ + ⟨θ (at ) − θ̂ T0 /2 , xt ⟩ + ⟨θ̂ T0 /2 − θ (at ) , xt ⟩t=T0 +1≤ T0 +

T
X

(1)

(0)

|⟨θ (1) − θ̂ T0 /2 , xt ⟩| + |⟨θ (0) − θ̂ T0 /2 , xt ⟩|t=T0 +1≤ T0 +

T
X

(1)

(0)

∥θ (1) − θ̂ T0 /2 ∥2 ∥xt ∥2 + ∥θ (0) − θ̂ T0 /2 ∥2 ∥xt ∥2

t=T0 +1(1)(0)≤ T0 + T · ∥θ (1) − θ̂ T0 /2 ∥2 + T · ∥θ (0) − θ̂ T0 /2 ∥2s
24d 7dσ 2 log(4d/γ)≤ T0 + T ·c0T0with probability 1 − γ, where the last inequality follows from Lemma B.10 and a union bound. The result follows frompicking T0 = 4 · 631/3 dσ 2/3 T 2/3 log1/3 (4d/γ).

Lemma B.10. Let fU d : X → R≥0 denote the density function of the uniform distribution over the d-dimensional unit
sphere. If T ≥ 2d and agent contexts are drawn from a distribution over the d-dimensional unit sphere with density function
f : X → R≥0 such that ffU(x)(x) ≥ c0 > 0, ∀x ∈ X , then the following guarantee holds for a ∈ {0, 1}.

∥θ

(a)

(a)
12d
− θ̂ t+1 ∥2 ≤c0s

7dσ 2 log(2d/γt )T0with probability 1 − γt .

Proof. Observe that

−1
T0 /2
T0 /2
X
X
(a)
(a)
⊤ 

θ̂ T0 /2 :=xs+k xs+k
xs+k rs+k
s=1
s=1


T0 /2

=

X

−1

xs+k x⊤
s+k

s=1
T0 /2

=θ

X

(a)
xs+k (x⊤+ ϵs+k )
s+k θ

s=1


(a)

T0 /2

+

X
s=1

−1

xs+k x⊤
s+k

T0 /2

X
s=1

xs+k ϵs+k

Strategic Apple Tasting

where k = 0 if a = 0 and k = T0 if a = 1. Therefore,(a)∥θ (a) − θ̂ T0 /2 ∥2 =

−1

T0 /2

X



xs+k x⊤
s+k

s=1

T0 /2

X

xs+k ϵs+k

s=1
2

−1



T0 /2

≤ 

X

T0 /2

X


xs+k x⊤s+k

xs+k ϵs+k

s=1

s=1

2

2

PT0 /2xs+k ϵs+k2
PT0 /2σmin ( s=1 xs+k x⊤
s+k )PT0 /2s=1 xs+k ϵs+k2=
PT0 /2λmin ( s=1
xs+k x⊤
s+k )
s=1

=

The desired result is obtained by applying Lemma B.11, Lemma B.12, and a union bound.
Lemma B.11. The following bound holds on the ℓ2 -norm of

PT0 /2s=1xs+k ϵs+k with probability 1 − γ:

T0 /2

X

p
≤ 2 7dσ 2 T0 log(d/γ)

xs+k ϵs+ks=12

PT0 /2
Observe that
Proof.
s=1 ϵk+s xk+s [i] is a sum of martingale differences with Zk+s := ϵk+s xk+s [i], Xk+s :=Ps′′s′ =1 ϵk+s xk+s [i], andmax{P(Zk+s > α|Xk+1 , . . . , Xk+s−1 ), P(Zk+s < −α|Xk+1 , . . . , Xk+s−1 )} ≤ · exp(−α2 /2σ 2 ).
By Theorem A.2,
T0 /2

X

p
ϵk+s xk+s [i] ≤ 2 7σ 2 T0 log(1/γi )s=1with probability 1 − γi . The desired result follows via a union bound and algebraic manipulation.
Lemma B.12. The following bound holds on the minimum eigenvalue ofT0 /2

λmin 

s=1

xs+k x⊤s+k with probability 1 − γ:





X

PT0 /2≥
xs+k x⊤
s+k

s=1

p
T0
+ 4 T0 log(d/γ)
6dProof.
T0 /2

λmin (

X

T0 /2

xs+k x⊤s+k ) ≥ λmin (

s=1

X

T0 /2
⊤
xs+k x⊤s+k − E[xs+k xs+k ]) + λmin (

s=1

X
s=1

E[xs+k x⊤s+k ])

s=1

T0 /2≥ λmin (

X

T0 /2
⊤
xs+k x⊤s+k − E[xs+k xs+k ]) +X

λmin (E[xs+k x⊤
s+k ])

s=1

where the inequalities follow from the fact that λmin (A + B) ≥ λmin (A) + λmin (B) for two Hermitian matrices A, B.
PT0 /2⊤⊤
Let YT0 /2 := s=1
xs+k x⊤s+k − E[xs+k xs+k ]. Note that EYT0 /2 = EY0 = 0, −Xs+k := E[xs+k xs+k ], E[−Xs+k ] = 0,2
and (−Xs+k ) ⪯ 4Id . By Theorem A.1,
P(λmax (−YT0 /2 ) ≥ α) ≤ d · exp(−α2 /16T0 ).

Strategic Apple Tasting

Since −λmax (−YT0 /2 ) = λmin (YT0 /2 ),P(λmax (YT0 /2 ) ≤ α) ≤ d · exp(−α2 /16T0 ).
Therefore, λmin (YT0 /2 ) ≥ 4
λmin (E[xs+k x⊤
s+k ]).

p
T0 log(d/γ) with probability 1 − γ. We now turn our attention to lower bounding⊤⊤
λmin (E[xs+k x⊤
s+k ]) := min ω E[xs+k xs+k ]ω
ω∈S d−1= min ω ⊤ω∈S d−1

=

1
Id ω
3d

1
3d

B.4. Proof of Theorem 3.5
Theorem B.13. Let RegOLS (T ) be the strategic regret of Algorithm 1 and RegETC (T ) be the strategic regret of Algorithm 4.
The expected strategic regret of Algorithm 2 isE[Reg(T )] ≤ 4 · min{E[RegOLS (T )], E[RegETC (T )]}Proof. Case 1: T < τ ∗ From Theorem B.9, we know thatRegETC (τi ) ≤8 · 631/3 2/3 2/3dσ τi log1/3 (4dτi2 )c0with probability 1 − 1/τi2 . Therefore,
E[RegETC (τi )] ≤Observe that

8 · 631/3 2/3 2/32
dσ τi log1/3 (4dτi2 ) +
c0
τi

Pi−1

j=1 E[RegETC (τj )] ≤ E[RegETC (τi )]. Suppose τi−1 ≤ T ≤ τi for some i. Under such a scenario,

E[Reg(T )] ≤ 2E[RegETC (τi )]≤ 2E[RegETC (2T )]≤ 4E[RegETC (T )]Case 2: T ≥ τ ∗ Let t∗ denote the actual switching time of Algorithm 2.
∗

t
T
X
X
∗
∗
Reg(T ) :=⟨θ (at ) − θ (at ) , xt ⟩ +⟨θ (at ) − θ (at ) , xt ⟩t=1

t=t∗ +1

E[Reg(T )] ≤ 2 · E[RegETC (t∗ )] + E[RegOLS (T − t∗ )]≤ 2 · E[RegOLS (t∗ )] + E[RegOLS (T )]≤ 2 · E[RegOLS (τ ∗ )] + E[RegOLS (T )]≤ 3 · E[RegOLS (T )]where the first line follows from case 1, the second line follows from the fact that t∗ ≤ τ ∗ (and so E[RegETC (t∗ )] ≤E[RegOLS (t∗ )]), the third line follows from the fact that t∗ ≤ τ ∗ , and the fourth line follows from the fact that T ≥ τ ∗ .

Strategic Apple Tasting

B.5. Inconsistency of OLS when using all data
(1)

Theorem B.14. limt→∞ θ̂ t+1 = θ (1)∗ if and only if limt→∞′ ′⊤s=1 xs xs

Pt1{as = 1} = limt→∞

Pt′ ⊤s=1 xs xs

1{as = 1}.

Proof.
(1)lim θ̂ t+1 := lim
t→∞
t→∞

= lim

t→∞

= lim

t→∞

+ lim

t→∞

= lim

t→∞

t
X

!−1

′
x′s xs⊤1{as = 1}s=1tXx′s xs⊤ 1{as = 1}′x′s xs⊤ 1{as = 1}′(1)
x′s (x⊤s θ ∗ + ϵs )1{as = 1}

t
X

(1)
x′s x⊤s θ ∗ 1{as = 1}

s=1

!−1

x′s xs⊤ 1{as = 1}
′

s=1
t
X

t
X
s=1

!−1

s=1
t
X

x′s rs(1) 1{as = 1}

s=1

!−1

s=1
t
X

t
X

t
X

x′s ϵs 1{as = 1}s=1′x′s xs⊤1{as = 1}

!−1

t
X

s=1

s=1

log(|E|)T λ2 |E| , γ = 2ηλ|E|, and ε =

!

x′s x⊤s1{as = 1} θ(1)∗C. Proofs for Section 4
C.1. Proof of Theorem 4.1
Theorem C.1. Algorithm 3 with η =qdσ log TT1/(d+2)

incurs expected strategic regret:e T (d+1)/(d+2) .
E[Reg(T )] ≤ 6T (d+1)/(d+2) (dσ log T )1/(d+2) = O
Proof. Let at,e correspond to the action chosen by a grid point e ∈ E. We simplify notation to at = at,et to be the action
chosen by the sampled grid point et at round t. For the purposes of the analysis, we also define ℓt (e) = 1 + λ − rt (at,et ).
We first analyze the difference between the loss of the algorithm and the best-fixed point on the grid e∗ , i.e.,




X
X
E[Regε (T )] = max E 
rt (at,e∗ ) − E 
rt (at )
e∗ ∈E


= E

t∈[T ]t∈[T ]

X

t∈[T ]

ℓt (et ) − min
E
∗
e ∈E


X

ℓt (e∗ )

t∈[T ]

where the equivalence between working with ℓt (·) as opposed to rt (·) holds because ℓt (·) are just a common shift from rt (·)
across all rounds and experts. For the regret of the algorithm, we show that:
 2d
 !
1
1
E[Regε (T )] = O T · d ·
· log
(4)
ε
ε
We define the “good” event as the event that the reward is in [0, 1] for every round t: C = {rt ∈ [0, 1], ∀t ∈ [T ]}. Note that
this depends on the noise of the round εt . We will call the complement of the “good” event, the “bad” event ¬C. The regretof the algorithm depends on both C and ¬C as follows:
E[Regε (T )] = E[Regε (T )|C] · Pr[C] + E[Regε (T )|¬C] · Pr[¬C] ≤ E[Regε (T )|C] + T · Pr[¬C](5)where the inequality is due to the fact that Pr[C] ≤ 1 and that in the worst case, the algorithm must pick up a loss of 1 ateach round.

Strategic Apple Tasting

We now upper bound the probability with which the bad event happens.
X
Pr[¬C] = Pr[∃t : rt ∈/ [0, 1]] ≤Pr[rt ∈
/ [0, 1]]

(union bound)t∈[T ]≤

X

Pr[|εt | ≥ λ] ≤ 2 exp(−λ2 /σ 2 ) · T ≤t∈[T ]

2T(substituting λ)Plugging Pr[¬C] to Equation (5) we get:
E[Regε (T )] ≤ E[Regε (T )|C] + 2(6)

εSo for the remainder of the proof we will condition√ on the clean event C and compute E[Reg (T )|C]. Conditioning on C
means that 1 + λ − rt (a) ∈ [0, λ], where λ = σ log T .

We first compute the first and the second moments of estimator ℓbt (·). For the first moment:hi Xℓt (e) · 1{e = e′ }E ℓbt (e) =qt (e′ ) ·= ℓt (e)qt (e)
′

(7)

h
i X
ℓ2t (e)λ2ℓ2 (e) · 1{e = e′ }E ℓb2t (e) ==≤qt (e′ ) t
qt2 (e)qt (e)
qt (e)
′

(8)

e ∈E

For the second moment:e ∈E

where for the first inequality, we have used the fact that ℓt (e) ≤ λ (since we conditioned on C) and the last one is due to thefact that qt (e) ≥ γ/|E|.
We define P
the weight assigned to grid point e ∈ E at round t as: wt (e) = wt−1 (e) · exp(−η ℓbt (e)) and w0 (e) = 1, ∀e ∈ E.
Let Wt = e∈E wt (e) be the potential function. Then,X
W0 =
w0 (e) = |E|
(9)
e∈E
∗

Using e to denote the best-fixed policy in hindsight, we have:

WT =

X


X

wT (e) ≥ wT (e∗ ) = exp −ηe∈Eℓbt (e∗ )

(10)t∈[T ]

We next analyze how much the potential changes per-round:


P
!


bt (e)


w
(e)
exp
−η
ℓ
X
t
e∈E
Wt+1
 = logpt (e) exp −η ℓbt (e)log= log 
Wt
Wt
e∈E
!


X
2
2
≤ log
pt (e) · 1 − η ℓbt (e) + η ℓb (e)(e−x ≤ 1 − x + x2 , x > 0)
t

e∈E

!
= log 1 − ηXpt (e)ℓbt (e) + η 2

e∈E

≤ −η

X

= −η
≤ −η

(1 − γ)X qt (e) − γ/|E|
e∈E

(

P

e∈E pt (e) = 1)X

pt (e)ℓb2t (e)e∈E

X qt (e) − γ/|E|e∈Ept (e)ℓb2t (e)e∈E

pt (e)ℓbt (e) + η 2e∈EX(1 − γ)ℓbt (e) + η 2

X qt (e) − γ/|E|e∈E(1 − γ)X qt (e)ℓbt (e) + η 2ℓb2 (e)(1 − γ) te∈Eℓb2t (e)(11)

Strategic Apple Tasting

where the second inequality is due to the fact that log x ≤ x − 1 for x ≥ 0. In order for this inequality to hold we need toverify that:XX
pt (e)ℓbt (e) + η 2
pt (e)ℓb2t (e) ≥ 0,
1−η
e∈E

e∈E

or equivalently, that:1−ηX

pt (e)ℓbt (e) ≥ 0

(12)

e∈E

We do so after we explain how to tune η and γ.
We return to Equation (11); summing up for all rounds t ∈ [T ] in Equation (11) we get:
X X qt (e) − γ/|E|
X X qt (e)
WT
log
≤ −η
ℓbt (e) + η 2ℓb2 (e)W0(1 − γ)(1 − γ) tt∈[T ] e∈E(13)t∈[T ] e∈E

PUsing Equation (9) and Equation (10) we have that: log(WT /W0 ) ≥ −η t∈[T ] ℓbt (e∗ ) − log |E|. Combining this with theupper bound on log(WT /W0 ) from Equation (13) and multiplying both sides by (1 − γ)/η we get:

X
XX
X X
log(|E|)γ bℓbt (e∗ ) ≤ η
qt (e)ℓb2t (e) + (1 − γ)ℓt (e) − (1 − γ)qt (e) −|E|
ηt∈[T ] e∈Et∈[T ] e∈Et∈[T ]

We can slightly relax the right hand side using the fact that γ < 1 and get:

X X
X
XX
log(|E|)γ bqt (e) −ℓt (e) − (1 − γ)ℓbt (e∗ ) ≤ η
qt (e)ℓb2t (e) +|E|
ηt∈[T ] e∈Et∈[T ] e∈Et∈[T ]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:

X X
X
XX
γ
log(|E|)λ2
qt (e) −+ℓt (e) − (1 − γ)ℓt (e∗ ) ≤ η
qt (e)|E|qt (e)
ηt∈[T ] e∈Et∈[T ] e∈Et∈[T ]

Using the fact that ℓt (·) ∈ [0, λ] the above becomes:
E [Regε (T )|C] =XX

qt (e)ℓt (e) −t∈[T ] e∈E

Tuning η =qXℓt (e∗ ) ≤ ηT λ2 |E| +t∈[T ]

log(|E|)+ γT
ηlog(|E|)T λ2 |E| and γ = 2ηλ|E|, we get that:

E [Regε (T )|C] ≤ 3

pp
T |E|λ2 log(|E|) = 3 T |E|σ log(T ) log(|E|)(14)

Before we proceed to bounding the discretization error that we incur by playing policies only on the grid, we verify that
Equation (12) holds for the chosen η and γ parameters. Note that when ℓbt (e) = 0, then Equation (12) holds. So we focus on
the case where ℓbt (e) = ℓt (e)/qt (e).
η

X
e∈E

pt (e)XXℓt (e)ℓt (e) · |E|
λ · |E|λ|E|1≤ηpt (e)≤ηpt (e)=η=qt (e)
γ
γ
γ
2
e∈E

e∈E

where thePfirst inequality is due to the fact that qt (e) ≥ γ/|E|, ∀e ∈ E, the second is because ℓt (e) ≤ λ, the first equality is
because e∈E pt (e) = 1, and the last equality is because of the values that we chose for parameters η and γ.
The final step in proving the theorem is to bound the strategic discretization error that we incur because our algorithm only
chooses policies on the grid, while θ (1) , θ (0) (and hence, the actual optimal policy) may not correspond to any grid point.
Let a∗t correspond to the action chosen by the optimal policy.
E
X
X
XD ∗
SDE(T ) =E [rt (a∗t )] −E [rt (at,e∗ )] =θ (at ) − θ (at,e∗ ) , xtt∈[T ]t∈[T ]t∈[T ]

Strategic Apple Tasting

We separate the T rounds into 3 groups: in group G1 , we have rounds t ∈ [T ] such that a∗t = at,e∗ . In group G2 , we haverounds t ∈ [T ] such that a∗t = 0 but at,e∗ = 1. In group G3 , we have rounds t ∈ [T ], such that a∗t = 1 but at,e∗ = 0. With
these groups in mind, one can rewrite the above equation as:
E XD ∗E XD ∗E
XD ∗SDE(T ) =θ (at ) − θ (at,e∗ ) , xt +θ (at ) − θ (at,e∗ ) , xt +θ (at ) − θ (at,e∗ ) , xt
t∈G1

t∈G2

t∈G3

For all the rounds in G1 , the strategic discretization error is equal to 0. Hence the strategic discretization error becomes:
E
E XD ∗XD ∗SDE(T ) =θ (at ) − θ (at,e∗ ) , xt +θ (at ) − θ (at,e∗ ) , xt
(15)
t∈G3

t∈G2

|

{z

}

SDE(G2 )|{z

SDE(G3 )}We first analyze SDE(G2 ):SDE(G2 ) =EXDθ (0) − θ (1) , xtt∈G2b(1) − θb(0) . Adding and subtracting ⟨e∗ , xt ⟩ in the above, we get:b(1) and θb(0) the points such that e∗ = θ
Let us denote by θ
 
 

X 
(0)
(1)
(0)
(1)
(0)
(1)
b
b
b
b
SDE(G2 ) =θ − θ , xt + θ − θ , xt + θ − θ , xt
t∈G2

≤

X

θ

(0)

b(0) , xt
−θ




+

b(1) − θ (1) , xtθ

b(0) − θb(1) , xt+ θ(x ≤ |x|)t∈G2X  (0)(1)bb≤ 2εT +
θ − θ , xtt∈G2 |{z}(Cauchy-Schwarz)

Qt

Finally, we show that Qt ≤ 0. For the rounds where at,e∗ = 1 but a∗t = 0, it can be the case that xt ̸= x′t (as the agentsonly strategize in order to get assigned action 1. But since at,e∗ = 1, then from the algorithm:




(1)
(0)
(0)
(1)
′
∗
′
b
b
b
b
θ − θ , xt ≥ δ∥e ∥ ⇔ θ − θ , xt ≤ −δ∥e∗ ∥(16)Adding and subtracting x′t from quantity Qt , we have:

 

(0)
(1)
(0)
(1)
′
′
b
b
b
b
Qt = θ − θ , xt − xt + θ − θ , xt


(0)
(1)
′
b
b
≤ θ − θ , xt − xt − δ∥e∗ ∥(Equation (16))b(0) − θb(1) · ∥xt − x′ ∥ − δ∥e∗ ∥≤ θt(Cauchy-Schwarz)≤ ∥e∗ ∥ · δ − δ∥e∗ ∥.
As a result:
SDE(G2 ) ≤ 2εT(17)Moving on to the analysis of SDE(G3 ):SDE(G3 ) =EXDθ (0) − θ (1) , xtt∈G3b(1) and θb(0) the points that e∗ = θb(1) − θb(0) . Adding and subtracting ⟨e∗ , xt ⟩ and following the same
Again, we use θderivations as in SDE(G3 ), we have that:X  (1)b −θ
b(0) , xt
SDE(G3 ) ≤ 2εT +θ
(18)t∈G3 |{z}
Qt

Strategic Apple Tasting

Since at,e∗ = 0, then it must have been the case that x′t = xt ; this is because the agent would not spend effort to strategize
if they would still be assigned action 0. For this reason, it must be that Qt ≤ 0.
Combining the upper bounds for SDE(G2 ) and SDE(G3 ) in Equation (15), we 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 thestrategic discretization error, i.e.,
s
 d
p
1
E[Reg(T )] ≤ 3 T |E|σ log(T ) log(|E|) + 4εT = 3 T d
σ log(T ) log(1/ε) + 4εTεTuning ε =

dσ log TT1/(d+2)

we get that the regret is:e T (d+1)/(d+2) .
E[Reg(T )] ≤ 6T (d+1)/(d+2) (dσ log T )1/(d+2) = O

D. Extension to trembling hand best-response
Observe that when lazy tiebreaking (Definition 2.1), if agent t modifies their context they modify it by an amount δL suchthat
δL,t := min η0≤η≤δ

s.t. πt (x′t ) = 1∥x′t − xt ∥2 = η.
We define γ-trembling hand tiebreaking as δT H,t = δL,t + αt , where αt ∈ [0, min{δ − δL,t , γ}] 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 a shifted linear policy parameterized by β (1) ∈ Rd , we say that acontext x′ is clean if ⟨β (1) , x′ ⟩ > (δ + γ)∥β (1) ∥2 + r0 .
No further changes are required. This will result in a slightly worse constant in Theorem 3.3 (i.e. all instances of δ will be
replaced by δ + γ). Our algorithms and results in Section 4 do not change.