Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits

Area of Science:

• Machine Learning
• Reinforcement Learning
• Optimization

Background:

• Information-directed sampling (IDS) is effective for bandit problems.
• Frequentist IDS requires accurate prior bounds on parameter norms for optimal performance.
• Inaccurate bounds lead to significant regret accumulation in bandit algorithms.

Purpose of the Study:

• To develop a novel frequentist IDS algorithm that overcomes the need for pre-defined parameter norm bounds.
• To improve the performance of bandit algorithms in practical scenarios where parameter norms are unknown.
• To establish theoretical guarantees for the new algorithm's performance.

Main Methods:

• Introduced a novel frequentist IDS algorithm for the linear bandit setting with heteroskedastic subgaussian noise.
• Developed a method to iteratively refine high-probability upper bounds on the true parameter norm using accumulating data.
• Utilized a mixture of information gain criteria to balance bound refinement and optimal action selection.

Main Results:

• The proposed algorithm achieves regret bounds independent of initial parameter norm assumptions.
• Demonstrated superior performance compared to existing state-of-the-art IDS and UCB algorithms.
• The method effectively balances exploration for bound tightening and direct optimization.

Conclusions:

• The novel IDS algorithm successfully addresses the limitation of requiring prior parameter norm knowledge.
• This approach offers improved regret performance and practical applicability in bandit problems.
• The findings advance the field of reinforcement learning and decision-making under uncertainty.