# Contractual Reinforcement Learning: Pulling Arms with Invisible Hands arXiv: https://arxiv.org/abs/2407.01458 · HTML: https://mlsanity.com/paper/2407.01458/ ## Key facts - Cited by 5 papers in the map (data through 14 Oct 2026). - Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. - Builds on 33 of its 56 references that are in the map. - First posted on arXiv 1 Jul 2024. ## Placed in - Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/) ## Builds on (most cited first, 30 of 33) - [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014) - [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015) - [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018) - [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018) - [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015) - [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014) - [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022) - [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016) - [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018) - [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016) - [How Bad is Top-K Recommendation under Competing Content Creators?](https://mlsanity.com/paper/2302.01971/) (2023) - [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018) - [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015) - [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020) - [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022) - [Semi-parametric dynamic contextual pricing](https://mlsanity.com/paper/1901.02045/) (2019) - [Multi-armed Bandit Problems with Strategic Arms](https://mlsanity.com/paper/1706.09060/) (2017) - [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023) - [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023) - [Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online Platforms](https://mlsanity.com/paper/2401.09804/) (2024) - [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024) - [Contracts with Private Cost per Unit-of-Effort](https://mlsanity.com/paper/2111.09179/) (2021) - [Designing Menus of Contracts Efficiently: The Power of Randomization](https://mlsanity.com/paper/2202.10966/) (2022) - [Rethinking Incentives in Recommender Systems: Are Monotone Rewards Always Beneficial?](https://mlsanity.com/paper/2306.07893/) (2023) - [Delegated Classification](https://mlsanity.com/paper/2306.11475/) (2023) - [Online Learning in a Creator Economy](https://mlsanity.com/paper/2305.11381/) (2023) - [Delegated Search Approximates Efficient Search](https://mlsanity.com/paper/1806.06933/) (2018) - [Fiduciary Bandits](https://mlsanity.com/paper/1905.07043/) (2019) - [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023) - [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023) ## Built on by (most cited first, 5 of 5) - [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024) - [Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents](https://mlsanity.com/paper/2412.16318/) (2024) - [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025) - [Contracting With a Reinforcement Learning Agent by Playing Trick or Treat](https://mlsanity.com/paper/2410.13520/) (2024) - [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025) ## Abstract (arXiv) The agency problem emerges in today's large scale machine learning tasks, where the learners are unable to direct content creation or enforce data collection. In this work, we propose a theoretical framework for aligning economic interests of different stakeholders in the online learning problems through contract design. The problem, termed contractual reinforcement learning, naturally arises from the classic model of Markov decision processes, where a learning principal seeks to optimally influence the agent's action policy for their common interests through a set of payment rules contingent on the realization of next state. For the planning problem, we design an efficient dynamic programming algorithm to determine the optimal contracts against the far-sighted agent. For the learning problem, we introduce a generic design of no-regret learning algorithms to untangle the challenges from robust design of contracts to the balance of exploration and exploitation, reducing the complexity analysis to the construction of efficient search algorithms. For several natural classes of problems, we design tailored search algorithms that provably achieve tildeO(√T) regret. We also present an algorithm with tildeO(T2/3) for the general problem that improves the existing analysis in online contract design with mild technical assumptions.