Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Dec 6, 2021
Speakers
Baihe Huang
Speaker · 0 followers
Kaixuan Huang
Speaker · 0 followers
Sham M. Kakade
Speaker · 0 followers
Jason D. Lee
Speaker · 0 followers
Runzhe Wang
Speaker · 0 followers
Jiaqi Yang
Speaker · 0 followers
About
Much work has considered multi-armed bandit problems under linear (or kernelized) assumptions on the underlying reward function. This work considers bandit problems where the unknown underlying reward function is structured polynomials, including a two-layer neural network with polynomial activations and a low-rank generalized linear bandit problem.For the low-rank generalized linear bandit problem, we provide a minimax optimal algorithm in the dimension, refuting the conjectures in Jun et al (2019) and Lu et al (2021). Our algorithm is a unified zeroth-order optimization paradigm that applies in general, which attains optimal rates in several structured polynomial settings (in the dimension). We instantiate with the generalized low-rank bandit on how our techniques can be extended to the RL in the generative setting, resulting in improved sample complexity over prior approaches.Finally, we show that the standard optimistic algorithms (e.g., UCB) are sub-optimal by dimension factors. With the neural net setting (with polynomial activation functions), where, in the noise-free setting, we provide a bandit algorithm that has sample complexity equal to the intrinsic algebraic dimension. Again, we show that optimistic approaches have worse sample complexity, polynomial in the extrinsic dimension (which could be exponentially worse in the polynomial degree).Much work has considered multi-armed bandit problems under linear (or kernelized) assumptions on the underlying reward function. This work considers bandit problems where the unknown underlying reward function is structured polynomials, including a two-layer neural network with polynomial activations and a low-rank generalized linear bandit problem.For the low-rank generalized linear bandit problem, we provide a minimax optimal algorithm in the dimension, refuting the conjectures in Jun et al (2…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Entropy-based adaptive Hamiltonian Monte Carlo
Watch later
Marcel Hirt, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Near-Optimal No-Regret Learning in General Games
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Reinforcement learning: It´s all in the mind
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Minimizing Polarization and Disagreement in Social Networks via Link Recommendation
Watch later
Liwang Zhu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning
Watch later
Zhuqing Liu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Improved Drought Forecasting Using Surrogate Quantile And Shape (SQUASH) Loss
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%