In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler’s objective is to maximize cumulative expected earnings over some planning horizon of length T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation). The gambler’s policy is measured relative to a (static) oracle that knows the identity of the best arm a priori. The gap in performance between the former and latter is often referred to as the regret, and the main question is how small the regret can be as a function of problem primitives (hardness of the problem, typically measured as the distinguishability of the best arm) and the game horizon (T). This problem has been studied extensively when the reward distributions do not change over time. The uncertainty in this set up is purely spatial and essentially amounts to identifying the optimal arm. We complement this literature by developing a flexible nonparametric model for temporal uncertainty in the rewards. The extent of temporal uncertainty is measured via the cumulative mean change of the rewards over the horizon, a metric we refer to as temporal variation, and regret is measured relative to a (dynamic) oracle that plays the pointwise optimal action at each instant in time. Assuming that nature can choose any sequence of mean rewards such that their temporal variation does not exceed V (viewed as a temporal uncertainty budget), we characterize the complexity of this MAB game via the minimax regret which depends on V (the hardness of the problem) the horizon length T and the number of arms K. When the uncertainty budget V is not known a priori, we develop a family of “master-slave” policies that adapt to the realized variation in rewards and provide numerical evidence suggesting that these policies are nearly minimax optimal.
-
Faculty
- Academic Areas
- Awards & Honors
- Seminars
-
Conferences
- Accounting Summer Camp
- California Econometrics Conference
- California Quantitative Marketing PhD Conference
- California School Conference
- China India Insights Conference
- Homo economicus, Evolving
-
Initiative on Business and Environmental Sustainability
- Political Economics (2023–24)
- Scaling Geologic Storage of CO2 (2023–24)
- A Resilient Pacific: Building Connections, Envisioning Solutions
- Adaptation and Innovation
- Changing Climate
- Civil Society
- Climate Impact Summit
- Climate Science
- Corporate Carbon Disclosures
- Earth’s Seafloor
- Environmental Justice
- Finance
- Marketing
- Operations and Information Technology
- Organizations
- Sustainability Reporting and Control
- Taking the Pulse of the Planet
- Urban Infrastructure
- Watershed Restoration
- Junior Faculty Workshop on Financial Regulation and Banking
- Ken Singleton Celebration
- Marketing Camp
- Quantitative Marketing PhD Alumni Conference
- Rising Scholars Conference
- Theory and Inference in Accounting Research
- Voices
- Publications
- Books
- Working Papers
- Case Studies
-
Research Labs & Initiatives
- Cities, Housing & Society Lab
- Corporate Governance Research Initiative
- Corporations and Society Initiative
- Golub Capital Social Impact Lab
- Policy and Innovation Initiative
- Rapid Decarbonization Initiative
- Stanford Latino Entrepreneurship Initiative
- Value Chain Innovation Initiative
- Venture Capital Initiative
- Behavioral Lab
- Data, Analytics & Research Computing