# Strategic Apple Tasting

arXiv: https://arxiv.org/abs/2306.06250 · HTML: https://mlsanity.com/paper/2306.06250/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 57 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 30 of 35)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021)
- [Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses](https://mlsanity.com/paper/2107.05762/) (2021)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [Greedy Algorithm almost Dominates in Smoothed Contextual Bandits](https://mlsanity.com/paper/2005.10624/) (2020)
- [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023)
- [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Bayesian Persuasion for Algorithmic Recourse](https://mlsanity.com/paper/2112.06283/) (2021)
- [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022)

## Built on by (most cited first, 10 of 10)

- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Classification Under Strategic Self-Selection](https://mlsanity.com/paper/2402.15274/) (2024)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025)
- [Strategic Usage in a Multi-Learner Setting](https://mlsanity.com/paper/2401.16422/) (2024)
- [The Active and Noise-Tolerant Strategic Perceptron](https://mlsanity.com/paper/2512.01783/) (2025)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [Strategic Hypothesis Testing](https://mlsanity.com/paper/2508.03289/) (2025)
- [Ambiguous Strategic Classification](https://mlsanity.com/paper/2606.10137/) (2026)

## Abstract (arXiv)

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 O (√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 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).