Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

Dylan J. Foster, Noah Golowich, Yanjun Han
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3969-4043, 2023.

Abstract

A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what algorithm design principles achieve optimal sample complexity. Recently, Foster et al. (2021) introduced the Decision- Estimation Coefficient (DEC), a measure of statistical complexity which leads to upper and lower bounds on the optimal sample complexity for a general class of problems encompassing bandits and reinforcement learning with function approximation. In this paper, we introduce a new variant of the DEC, the Constrained Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts:• they hold in expectation, with no restrictions on the class of algorithms under consideration.• they hold globally, and do not rely on the notion of localization used by Foster et al. (2021).• most interestingly, they allow the reference model with respect to which the DEC is defined to be improper, establishing that improper reference models play a fundamental role.We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. (2021). Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-foster23b, title = {Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient}, author = {Foster, Dylan J. and Golowich, Noah and Han, Yanjun}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3969--4043}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/foster23b/foster23b.pdf}, url = {https://proceedings.mlr.press/v195/foster23b.html}, abstract = {A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what algorithm design principles achieve optimal sample complexity. Recently, Foster et al. (2021) introduced the Decision- Estimation Coefficient (DEC), a measure of statistical complexity which leads to upper and lower bounds on the optimal sample complexity for a general class of problems encompassing bandits and reinforcement learning with function approximation. In this paper, we introduce a new variant of the DEC, the Constrained Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts:• they hold in expectation, with no restrictions on the class of algorithms under consideration.• they hold globally, and do not rely on the notion of localization used by Foster et al. (2021).• most interestingly, they allow the reference model with respect to which the DEC is defined to be improper, establishing that improper reference models play a fundamental role.We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. (2021). Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.} }
Endnote
%0 Conference Paper %T Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient %A Dylan J. Foster %A Noah Golowich %A Yanjun Han %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-foster23b %I PMLR %P 3969--4043 %U https://proceedings.mlr.press/v195/foster23b.html %V 195 %X A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what algorithm design principles achieve optimal sample complexity. Recently, Foster et al. (2021) introduced the Decision- Estimation Coefficient (DEC), a measure of statistical complexity which leads to upper and lower bounds on the optimal sample complexity for a general class of problems encompassing bandits and reinforcement learning with function approximation. In this paper, we introduce a new variant of the DEC, the Constrained Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts:• they hold in expectation, with no restrictions on the class of algorithms under consideration.• they hold globally, and do not rely on the notion of localization used by Foster et al. (2021).• most interestingly, they allow the reference model with respect to which the DEC is defined to be improper, establishing that improper reference models play a fundamental role.We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. (2021). Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
APA
Foster, D.J., Golowich, N. & Han, Y.. (2023). Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3969-4043 Available from https://proceedings.mlr.press/v195/foster23b.html.

Related Material