Robust Learning with Private Information

Kyohei Okumura · 2025

Read Robust Learning with Private Information by Kyohei Okumura (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05341.txt.

Introduction

Kyohei Okumura studies learning algorithms that firms use on platform markets in this 2025 paper. Standard algorithms do well when platform rules stay fixed, but a platform may adapt its rules to a firm's behavior, and fast learning can then leak the firm's private type.

Okumura models a repeated screening problem where the agent commits to an algorithm while unsure whether the principal is fixed or adaptive. He shows that a broad class of standard algorithms, including all no-regret ones, can be manipulated until the platform extracts nearly all surplus. He then builds a robust algorithm that tests the fixed rule assumption. It earns the best payoff if rules are fixed and blocks rent extraction if they adapt.

Catalog record

CREATORKyohei Okumura
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05341

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Robust Learning with Private Information Kyohei Okumura Abstract Firms increasingly delegate decisions to learning algorithms in platform markets. Standard algorithms perform well when platform policies are stationary, but firms often face ambiguity about whether policies are stationary or adapt strategically to their behavior. When policies adapt, efficient learning under stationarity may backfire: it may reveal a firm’s persistent private information, allowing the platform to personalize terms and extract information rents. We study a repeated screening problem in which an agent with a fixed private type commits ex ante to a learning algorithm, facing ambiguity about the principal’s policy. We show that a broad class of standard algorithms, including all no-external-regret algorithms, can be manipulated by adaptive principals and permit asymptotic full surplus extraction. We then construct a misspecification-robust learning algorithm that treats stationarity as a testable hypothesis. It achieves the optimal payoff under stationarity at the minimax-optimal rate, while preventing dynamic rent extraction: against any adaptive principal, each type’s long-run utility is at least its utility under the menu that maximizes revenue under the principal’s prior. 0 0 footnotetext: I thank Hersh Chopra, Annie Liang, Harry Pei, Jon Schneider, Marciano Siniscalchi, and Bruno Strulovici for insightful comments. 1 Introduction Algorithmic decision-making is now routine in platform markets, and firms increasingly delegate their decisions to learning algorithms. Advertisers rely on automated bidding tools, while sellers and hosts use algorithmic pricing. They do so, in part, because the mapping from actions to outcomes is imperfectly known: market conditions such as demand and product quality are uncertain, and platform policies—including reserve prices, ranking scores, eligibility rules, and fee schedules—are often only partially understood ex ante and are learned through interaction. In such settings, a learning algorithm serves as a practical commitment device, specifying how the firm will experiment and adapt given its limited knowledge of the environment. Many firms deploy off-the-shelf learning algorithms that are guaranteed to perform well in stationary environments. Stationarity can be a reasonable approximation when policy updates are infrequent, and rapid personalization is limited by operational or institutional frictions. At the same time, modern platforms may implement adaptive, history-dependent policies firm-by-firm through automated experimentation and revenue optimization, so the terms a firm faces may respond to its past behavior. Do standard algorithms perform well when the environment is not stationary? If not, can we design algorithms that are robust to this form of model misspecification? This paper studies the design of learning algorithms for a firm facing ambiguity about whether a platform’s policy is stationary or adaptive. The ambiguity matters because efficient learning under stationarity requires payoff-responsive experimentation. With a persistent private type, payoff-responsive experimentation induces type-revealing behavior. When a platform conditions future terms of trade on observed behavior, it may be possible to use early play to infer private type and then extract information rents by personalizing future terms. We show that this tension is real for many standard learning objectives, but it can be resolved by an appropriately designed algorithm. The contribution of this paper is threefold. First, we formalize a robustness concern that arises when a privately informed agent commits ex ante to a learning algorithm in a screening environment where the principal’s policy may be stationary or adaptive. Second, we show that standard learning objectives do not address this concern: a broad class of off-the-shelf algorithms, including all no-external-regret algorithms, is vulnerable to adaptive principals and allows asymptotic full surplus extraction. Third, we construct a learning algorithm that is minimax-rate-optimal under stationarity and guarantees that, against any adaptive principal, each type’s long-run utility is at least its benchmark utility under the static revenue-maximizing menu. We model a two-player repeated screening problem between a privately informed agent and a principal. The agent privately observes his type before the interaction begins, and commits ex ante to an online learning algorithm. The agent’s type is persistent and fixed throughout the game. Each period, the agent chooses an action and observes the realized allocation and payment for the chosen action. The principal observes the committed algorithm and the agent’s actions, but not the agent’s type. The agent faces ambiguity about the principal’s behavior. Under stationarity , the principal’s per-period mechanism is drawn i.i.d. from an unknown distribution. Under adaptation , the principal chooses mechanisms strategically to maximize expected revenue given a prior over types, taking the committed algorithm as given. We evaluate learning algorithms along two dimensions. The goal is to achieve the best possible performance when the principal’s policy lies in a reference class, while guaranteeing a meaningful payoff when it does not. Specifically, under stationarity , the algorithm should learn efficiently: the agent’s time-average payoff should approach that of the best action. Under adaptation , the algorithm should limit dynamic rent extraction. To formalize this second requirement, we first introduce a conservative notion, weak extraction robustness , which rules out principal strategies that extract the agent’s full surplus for all types asymptotically. We then introduce a sharper benchmark, no dynamic rent extraction , which compares the agent’s long-run utility to its utility under the static revenue-maximizing screening menu. Our first results show that standard learning algorithms can be highly vulnerable when the principal adapts. The common force is that efficient learning induces type-dependent behavior. In particular, any algorithm that satisfies no external regret must respond approximately optimally to mechanisms that are held fixed for long periods. An adaptive principal can exploit this by running a short probing phase to elicit the agent’s type, then switching to personalized terms of trade that extract the agent’s information rent. We show that standard learning algorithms, including all no-external-regret algorithms, fail to achieve weak extraction robustness, thereby permitting asymptotic full surplus extraction. We then construct an algorithm that achieves rate-optimal learning under stationarity while satisfying no dynamic rent extraction. The key idea is to combine a statistical test with a credible opt-out threat, calibrated so that deviations from behavior consistent with stationarity are detected at asymptotically negligible cost. The algorithm begins with a short, type-independent exploration phase that establishes a baseline, and then runs a rate-optimal learning procedure while monitoring outcomes against that baseline. If the principal’s behavior becomes statistically inconsistent with stationarity in a manner indicative of adaptation, the algorithm triggers and permanently switches to an opt-out action that eliminates profitable trade. This opt-out threat disciplines the adaptive principal: to sustain long-run revenue, the principal must behave as if committed to a stationary policy before it can infer the agent’s private information. The remainder of the paper proceeds as follows. Section 2 presents a motivating example. Section 3 introduces the model. Section 4 defines the design goals. Section 5 establishes impossibility results for standard objectives and shows how canonical algorithms can be exploited. Section 6 presents the proposed algorithms and their guarantees. Section 7 discusses the conceptual limitations of regret-based objectives in strategic environments. Section 8 concludes. All proofs are in the Appendix. 1.1 Related literature This paper contributes to three strands of literature. Exploiting no-regret learners. A growing literature studies how a principal can exploit an agent who relies on a no-regret learning algorithm in repeated interaction, beginning with Braverman et al. (2018) . Most existing analyses focus on two benchmark environments. In repeated normal-form games (e.g., Deng et

Read the complete text