Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
In the fixed budget thresholding bandit problem, an algorithm sequentially allocates a budgeted number of samples to different distributions. It then predicts whether the mean of each distribution is larger or lower than a given threshold. We introduce a large family of algorithms (containing most existing relevant ones), inspired by the Frank-Wolfe algorithm, and provide a thorough yet generic analysis of their performance. This allowed us to construct new explicit algorithms, for a broad class of problems, whose losses are within a small constant factor of the non-adaptive oracle ones. Quite interestingly, we observed that adaptive methods empirically greatly out-perform non-adaptive oracles, an uncommon behavior in standard online learning settings, such as regret minimization. We explain this surprising phenomenon on an insightful toy problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Recursive nonlinear-system identification using latent variables
In this paper we develop a method for learning nonlinear systems with multiple outputs and inputs. We begin by modelling the errors of a nominal predictor of the system using a latent variable framework. Then using the m…
Identification of Nonlinear Dynamic Panels under Partial Stationarity
This paper studies identification for a wide range of nonlinear panel data models, including binary choice, ordered response, and other types of limited dependent variable models. Our approach accommodates dynamic models…
On Space-Filling Input Design for Nonlinear Dynamic Model Learning: A Gaussian Process Approach
While optimal input design for linear systems has been well-established, no systematic approach exists for nonlinear systems where robustness to extrapolation/interpolation errors is prioritized over minimizing estimated…
Efficient ExplorationEfficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation
We present the OMG-CMDP! algorithm for regret minimization in adversarial Contextual MDPs. The algorithm operates under the minimal assumptions of realizable function class and access to online least squares and log loss…
regressionAccelerated Alternating Minimization for X-ray Tomographic Reconstruction
While Computerized Tomography (CT) images can help detect disease such as Covid-19, regular CT machines are large and expensive. Cheaper and more portable machines suffer from errors in geometry acquisition that downgrad…
Image Reconstruction