Stochastic linear bandits with global-local structure

This work pertains to the field of Multi-Armed-Bandits (MAB), a framework in online learning where an agent sequentially chooses from a set of available actions, called arms, and receives feedback in the form of a scalar reward for each choice, with the goal of maximizing the cumulative reward over time. A well-known extension of the MAB is the stochastic linear bandit, where each arm is a vector and the expected reward of each arm is the dot product between the arm vector and an unknown parameter vector, which the agent aims to estimate through repeated pulls of the arms. We analyze a specific multi-agent bandit setting, where multiple linear bandits face different yet related tasks, with the additional assumption that the parameter vector of each agent is decomposed into a global component shared across all agents and a local component specific to each agent. We call the proposed problem scenario Partitioned Linear Setting. At each time step, an external context index determines which agent will be the actor of the current turn, and the selected agent chooses an arm from a set of available arms. To solve this setting we propose P-LinUCB, an algorithm that effectively maximizes the collective reward of multiple agents by leveraging both global and local information. We provide an experimental analysis of the algorithm's performance and show that it outperforms a well-known baseline for the multi-agent bandit setting across multiple scenarios.

L'argomento di questo lavoro tratta il campo dei Multi-Armed-Bandits (MAB), un framework per l'apprendimento online in cui un agente sceglie ripetutamente un'azione da un'insieme di azioni disponibili, e riceve un feedback per ogni scelta, con l'obiettivo di massimizzare il reward cumulativo nel tempo. Una nota estensione del MAB è lo stochastic linear bandit, in cui ogni azione è un vettore e il valore atteso di ciascuna azione è il prodotto scalare tra il vettore dell'azione e un vettore di parametri sconosciuti, che l'agente stima scegliendo ripetutamente delle azioni. La tesi affronta una variante del MAB chiamata Partitioned Linear Setting, in cui abbiamo più linear bandit che affrontano compiti diversi ma correlati. Il vettore dei parametri di ciascun agente viene scomposto in una componente globale condivisa tra tutti gli agenti e una componente locale specifica per ciascun agente. Ad ogni istante di tempo, un indice di contesto esterno determina quale agente sarà designato per il turno corrente, e l'agente selezionato sceglie un'azione dall'insieme di azione disponibile. Per risolvere il problema descritto proponiamo P-LinUCB, un algoritmo che massimizza il reward collettivo di più agenti sfruttando sia le informazioni globali che quelle locali. Forniamo un'analisi sperimentale delle performance dell'algoritmo e dimostriamo che batte in vari scenari una baseline comunemente usata per il problema dei bandit multi-agente.