Problemas de bandit de múltiplas armas com braços dependentes

Fornecermos uma estrutura para explorar dependências entre braços em problemas de bandit de múltiplas armas, quando as dependências estão na forma de um modelo generativo em clusters de braços. Encontramos uma política ótima baseada em MDP para o caso de recompensa descontada e também damos uma aproximação dela com garantia formal de erro. Discutimos limites inferiores sobre o arrependimento no cenário de recompensa não descontada e propomos uma política geral de bandit de dois níveis para isso. Propomos três diferentes instanciações de nossa política geral e fornecemos justificativas teóricas de como o arrependimento das políticas instanciadas depende das características dos clusters. Finalmente, demonstramos empiricamente a eficácia de nossas políticas em dados do mundo real em larga escala e sintéticos, e mostramos que elas superam significativamente políticas clássicas projetadas para bandits com braços independentes.