STATISTICAL COMPLEXITY AND OPTIMAL ALGORITHMS FOR NONLINEAR RIDGE BANDITS

• 成果类型: Article
• 署名作者: Rajaraman, Nived; Han, Yanjun; Jiao, Jiantao; Ramchandran, Kannan
• 署名单位: University of California System; University of California Berkeley; New York University; New York University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/24-AOS2395
• 发表日期: 2024
• 页码: 2557-2582
• 关键词: sequential estimation; DESIGN; optimization; efficient

摘要

We consider the sequential decision-making problem where the mean outcome is a nonlinear function of the chosen action. Compared with the linear model, two curious phenomena arise in nonlinear models: first, in addition to the learning phase with a standard parametric rate for estimation or regret, there is an burn-in period with a fixed cost determined by the nonlinear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of nonlinear functions named ridge functions in the literature, we derive upper and lower bounds on the optimal burn-in cost, and in addition, on the entire learning trajectory during the burn-in period via differential equations. In particular, a two-stage algorithm that first finds a good initial action and then treats the problem as locally linear is statistically optimal. In contrast, several classical algorithms, such as UCB and algorithms relying on regression oracles, are provably suboptimal.