Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916086384951296 |
|---|---|
| author | Rajaraman, Nived Han, Yanjun Jiao, Jiantao Ramchandran, Kannan |
| author_facet | Rajaraman, Nived Han, Yanjun Jiao, Jiantao Ramchandran, Kannan |
| contents | We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise in non-linear 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 non-linear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of non-linear 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06025 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits Rajaraman, Nived Han, Yanjun Jiao, Jiantao Ramchandran, Kannan Machine Learning Information Theory Statistics Theory We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise in non-linear 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 non-linear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of non-linear 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. |
| title | Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits |
| topic | Machine Learning Information Theory Statistics Theory |
| url | https://arxiv.org/abs/2302.06025 |