Optimal Model Selection in Contextual Bandits with Many Classes via Offline Oracles

Sanath Kumar Krishnamurthy and Susan Athey
Additional contact information
Sanath Kumar Krishnamurthy: Stanford University

Research Papers from Stanford University, Graduate School of Business

Abstract: We study the problem of model selection for contextual bandits, in which the algorithm must balance the bias-variance trade-off for model estimation while also balancing the exploration-exploitation trade-off. In this paper, we propose the first reduction of model selection in contextual bandits to offline model selection oracles, allowing for flexible general purpose algorithms with computational requirements no worse than those for model selection for regression. Our main result is a new model selection guarantee for stochastic contextual bandits. When one of the classes in our set is realizable, up to a logarithmic dependency on the number of classes, our algorithm attains optimal realizability-based regret bounds for that class under one of two conditions: if the time-horizon is large enough, or if an assumption that helps with detecting misspecification holds. Hence our algorithm adapts to the complexity of this unknown class. Even when this realizable class is known, we prove improved regret guarantees in early rounds by relying on simpler model classes for those rounds and hence further establish the importance of model selection in contextual bandits.

Date: 2021-06
New Economics Papers: this item is included in nep-cmp, nep-ecm and nep-ore
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.gsb.stanford.edu/faculty-research/work ... many-classes-offline

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ecl:stabus:3971

Access Statistics for this paper

More papers in Research Papers from Stanford University, Graduate School of Business Contact information at EDIRC.
Bibliographic data for series maintained by ().