Instance-dependent Optimality in Statistical Decision-making
Wenlong Mou
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2023-220
August 11, 2023
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-220.pdf
Data-driven and learning-based methodologies have been very popular in modern decision-making systems. In order to make optimal use of data and computational resources, these problems require theoretically sound procedures for choosing between estimators, tuning their parameters, and understanding bias/variance trade-offs. In many settings, asymptotic and/or worst-case theory fails to provide the relevant guidance.
In this dissertation, I present some recent advances that involve a more refined approach, one that leads to non-asymptotic and instance-optimal guarantees. Focusing on function approximation methods for policy evaluation in reinforcement learning, in Part I, I describe a novel class of optimal oracle inequalities for projected Bellman equations, as well as computationally efficient algorithms achieving them. In contrast to corresponding results for ordinary regression, the approximation pre-factor depends on the geometry of the problem, and can be much larger than unity. In Part II, I discuss optimal procedures for estimating linear functionals from observational data. Our theory reveals a rich spectrum of behavior beyond the asymptotic semi-parametric efficiency bound. It also highlights the fundamental roles of geometry, and provides concrete guidance on practical procedures and parameter choices.
Advisors: Peter Bartlett and Martin Wainwright
BibTeX citation:
@phdthesis{Mou:EECS-2023-220, Author= {Mou, Wenlong}, Title= {Instance-dependent Optimality in Statistical Decision-making}, School= {EECS Department, University of California, Berkeley}, Year= {2023}, Month= {Aug}, Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-220.html}, Number= {UCB/EECS-2023-220}, Abstract= {Data-driven and learning-based methodologies have been very popular in modern decision-making systems. In order to make optimal use of data and computational resources, these problems require theoretically sound procedures for choosing between estimators, tuning their parameters, and understanding bias/variance trade-offs. In many settings, asymptotic and/or worst-case theory fails to provide the relevant guidance. In this dissertation, I present some recent advances that involve a more refined approach, one that leads to non-asymptotic and instance-optimal guarantees. Focusing on function approximation methods for policy evaluation in reinforcement learning, in Part I, I describe a novel class of optimal oracle inequalities for projected Bellman equations, as well as computationally efficient algorithms achieving them. In contrast to corresponding results for ordinary regression, the approximation pre-factor depends on the geometry of the problem, and can be much larger than unity. In Part II, I discuss optimal procedures for estimating linear functionals from observational data. Our theory reveals a rich spectrum of behavior beyond the asymptotic semi-parametric efficiency bound. It also highlights the fundamental roles of geometry, and provides concrete guidance on practical procedures and parameter choices.}, }
EndNote citation:
%0 Thesis %A Mou, Wenlong %T Instance-dependent Optimality in Statistical Decision-making %I EECS Department, University of California, Berkeley %D 2023 %8 August 11 %@ UCB/EECS-2023-220 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-220.html %F Mou:EECS-2023-220