Bayesian Regret Minimization in Offline Bandits
This work addresses decision-making in offline bandits for researchers and practitioners, offering a novel method with proven superiority over existing approaches, though it is incremental in improving regret bounds.
The paper tackles the problem of minimizing Bayesian regret in offline linear bandits by arguing that prior LCB-based methods are flawed and proposing a new algorithm that directly minimizes tight upper bounds using conic optimization and connections to monetary risk measures. The results show that the approach outperforms LCB methods in synthetic domains.
We study how to make decisions that minimize Bayesian regret in offline linear bandits. Prior work suggests that one must take actions with maximum lower confidence bound (LCB) on their reward. We argue that the reliance on LCB is inherently flawed in this setting and propose a new algorithm that directly minimizes upper bounds on the Bayesian regret using efficient conic optimization solvers. Our bounds build heavily on new connections to monetary risk measures. Proving a matching lower bound, we show that our upper bounds are tight, and by minimizing them we are guaranteed to outperform the LCB approach. Our numerical results on synthetic domains confirm that our approach is superior to LCB.