TL;DR
This paper introduces the Minimum Empirical Divergence (MED) policy for the multi-armed bandit problem, offering an asymptotically optimal solution for finite support models. MED efficiently balances exploration and exploitation by minimizing the empirical divergence between an arm's observed rewards and the best possible outcome, demonstrating strong performance in simulations.
What Problem Does This Paper Address?
The multi-armed bandit problem is a classic challenge in reinforcement learning where an agent must choose between exploring unknown options (arms of a slot machine) and exploiting known good options to maximize cumulative rewards. The core dilemma is that to know which arm is best, you need to pull it many times, but pulling suboptimal arms is a direct loss. Existing asymptotically optimal policies often require knowledge of the exact support of the reward distributions, which is often unavailable in practice. This paper addresses this limitation by proposing a policy that only requires knowledge of the bounds of the support, making it more practical.
Methods
The paper introduces the Minimum Empirical Divergence (MED) policy. At each round, MED calculates a "minimum empirical divergence" for each arm. This divergence measures how much the observed rewards from an arm deviate from the expected reward of the current best arm, assuming the arm's true distribution has a support within the known bounds. The arm is then chosen probabilistically, with higher probability given to arms with lower empirical divergence.
A key innovation is the efficient computation of this divergence. The paper formulates it as a convex optimization problem, specifically a minimization problem that can be solved using univariate convex optimization techniques (like Newton's method). This is a significant advantage over some prior methods that might require more complex optimization.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and simulation results using synthetic distributions.
Key Insights and Ideas
- Bridging the Gap in Support Knowledge: The MED policy's ability to achieve asymptotic optimality without knowing the exact support of reward distributions is a crucial practical advancement.
- Divergence as an Exploration Metric: Using empirical divergence as a criterion for arm selection provides an intuitive and mathematically sound way to balance exploration and exploitation.
- Efficient Convex Optimization: Reformulating the divergence calculation as a solvable convex optimization problem is key to the policy's practical implementability.
- Probabilistic Matching: MED can be viewed as a form of "probability matching," where arms are pulled with probabilities reflecting their likelihood of being optimal, based on empirical evidence.
Key Results
- Asymptotic Optimality: The paper proves that the MED policy is asymptotically optimal for finite support models, meaning its expected number of pulls of suboptimal arms grows at the slowest possible rate.
- Efficient Computation: The paper demonstrates that the core computation for MED, the minimum empirical divergence, can be efficiently performed using univariate convex optimization.
- Strong Simulation Performance: Simulations show that MED performs competitively with, and often better than, existing popular policies like UCB-tuned and UCB2, even for distributions with continuous supports (though theoretical guarantees are for finite supports). The asymptotic slope of the regret for MED is shown to be close to the theoretical bound.
Limitations and Future Work
- Finite Support Assumption: The theoretical guarantees of asymptotic optimality are proven for finite support models. While simulations suggest it works well for continuous bounded supports, further theoretical work is needed to confirm this.
- Finite Horizon Case: The current analysis focuses on infinite-horizon problems. The paper suggests that extending MED to finite-horizon scenarios, where the number of rounds is fixed, is an important area for future research. This would likely require developing finite-time bounds and potentially adapting the policy for scenarios where exploration opportunities diminish over time.
- Deterministic Version: The current MED policy is randomized. The authors suggest exploring the possibility of constructing a deterministic version.
- Other Distribution Families: The paper notes that MED could potentially be extended to other distribution families where the divergence can be computed efficiently, such as normal distributions.
Summary updated