Efficient learning by implicit exploration in bandit problems with side observations

TL;DR

We propose an implicit exploration-based algorithm for partial observability bandit problems that guarantees near-optimal regret without knowing the observation system.

Problem

Existing bandit problems assume either full information or bandit feedback, but many real-world scenarios involve intermediate situations with additional observations. There was a lack of efficient algorithms for learning under such partial observability when the observation system is unknown in advance.

Approach

We introduce a novel exploration strategy called implicit exploration, which considers observability when selecting actions and ensures regret bounds without prior knowledge of the observation system. The first algorithm handles general partial observability, while the second variant improves computational efficiency for combinatorial optimization problems.

Results & Contribution

The proposed algorithms achieve O(√T) regret even when the observation system is unknown, and are theoretically proven to be more efficient computationally and information-theoretically than existing exploration strategies. This significantly enhances the practical applicability of partial observability bandit problems.