Quick Best Action Identification in Linear Bandit Problems
This addresses a specific problem in bandit theory for learners needing efficient parameter estimation, but it is incremental as it adapts existing setups with a new objective.
The paper tackles the problem of best action identification in stochastic linear bandits by focusing on accurate parameter estimation rather than minimizing cumulative regret, and shows that their designed policy achieves the same scaling order as a derived lower bound on estimation error.
In this paper, we consider a best action identification problem in the stochastic linear bandit setup with a fixed confident constraint. In the considered best action identification problem, instead of minimizing the accumulative regret as done in existing works, the learner aims to obtain an accurate estimate of the underlying parameter based on his action and reward sequences. To improve the estimation efficiency, the learner is allowed to select his action based his historical information; hence the whole procedure is designed in a sequential adaptive manner. We first show that the existing algorithms designed to minimize the accumulative regret is not a consistent estimator and hence is not a good policy for our problem. We then characterize a lower bound on the estimation error for any policy. We further design a simple policy and show that the estimation error of the designed policy achieves the same scaling order as that of the derived lower bound.