Back to search

Cornell University

Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms

Abstract

dc:description.abstract

We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Xiangyu
Chair dc:contributor.chair
  • Frazier, Peter
Committee members dc:contributor.committeemember
  • Chen, Yudong
  • Dai, Jim
  • Topaloglu, Huseyin

Rights

dc:rights
Statement dc:rights
  • Attribution-ShareAlike 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15578911
Dc Identifier Other
ProQuest Submission ID: 13180
ProQuest Publication ID: 29261579

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Xiangyu. Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms. Doctor of Philosophy thesis, Cornell University, 2022. https://hdl.handle.net/1813/112101