Abstract
I combinatorial bandit (CMAB) generalizzano il noto framework dei multi-armed bandit: a ogni round chi apprende sceglie, tra gli arm disponibili, un sottoinsieme che soddisfa vincoli noti, ne osserva i payoff e punta a massimizzare la ricompensa cumulata.
Studiamo per la prima volta scenari CMAB in cui le ricompense attese degli arm sono in qualche misura correlate. Questa correlazione è decisiva perché gli algoritmi restino efficaci quando lo spazio degli arm è molto ampio.
In questo paper proponiamo un algoritmo bandit, il Gaussian Combinatorial Bandit (GCB), pensato per contesti in cui gli arm sono divisi in sottoinsiemi e le funzioni di payoff degli arm di ciascun sottoinsieme hanno una distribuzione congiunta di tipo Gaussian Process (GP).
Ne presentiamo due varianti, frequentista e bayesiana, che sotto ipotesi poco stringenti raggiungono nel caso peggiore un regret di Õ(C √N), dove C è il numero di sottoinsiemi di arm con payoff correlati e N il numero di round.