Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
The authors establish minimax lower bounds for quantum multi-armed bandits (QMAB) and finite-action quantum linear bandits (QLB), showing worst-case regret grows logarithmically with time T. They also present upper bounds using algorithms like LV-G-Elim, which achieve near-linear regret in dimension d for QLB, providing a comprehensive analysis of performance limits.