Factored approaches for high dimensional multi-armed bandits

This thesis focuses on the problem of price optimization for the airline ticket market, looking at it from the perspective of online travel agencies (OTA), selling through metasearch engines. Operating in this context is challenging for OTAs, since they have no information about individual users and face significant competition. Specifically, we will analyze the problem of inner competition, arising both when a group of partner OTAs prices the tickets for the same route and when a single OTA prices differently branded tickets. Existing approaches optimize independently, either at the OTA level or at the brand level, causing the selection of suboptimal pricing schemes and, ultimately, an overall decrease of the total revenue. On the contrary, performing joint optimization in a centralized manner guarantees, at least theoretically, to find the optimal pricing scheme, but, in practice, entails operating on high-dimensional spaces and presents severe scalability problems. Our proposed solution consists in a set of techniques that, taking into account the inner competition problem, operates on a factored representation of the joint optimization space. We take inspiration from the Multi-armed Bandit (MAB) and Cooperative Learning (CL) literature. MAB solutions focus on achieving optimal performance on single-state, sequential-decision problems, balancing exploration and exploitation on the basis of past plays and obtained revenue, while CL methods address the problem of coordinating a set of distributed learners, operating in a common environment, as to maximize a shared performance metric. By distributing the work to multiple cooperating agents, our solutions are able to find the optimal pricing scheme, with reasonable space and time constraints, in many real-world settings. We thoroughly tested our techniques both in a generic optimization context and in a pricing context, obtaining promising results and performing better than all of the baselines we considered.

Questa tesi affronta il problema dell'ottimizzazione dei prezzi per il mercato dei biglietti aerei, analizzandolo dalla prospettiva delle agenzie di viaggio online (OTA) che operano su metasearch engine. La forte competizione e l'assenza di informazioni sui singoli utenti fanno sì che operare in questo contesto risulti particolarmente difficile per le OTA. Nello specifico, ci concentreremo sul problema della competizione interna, che si presenta sia quando più OTA in partnership scelgono i prezzi per dei biglietti di una stessa tratta che quando una singola OTA sceglie i prezzi per dei biglietti di diverse compagnie aeree. Le tecniche attualmente in uso ottimizzano i prezzi in maniera indipendente, a livello di OTA per il caso partnership e di compagnia aerea per il caso singola OTA, causando la selezione di prezzi subottimali e, in definitiva, la perdita di profitti. Al contrario, ottimizzare congiuntamente, in maniera centralizzata, ci dà la garanzia teorica di trovare lo schema di prezzi ottimo, ma, in pratica, questo approccio presenta problemi di scalabilità. La soluzione che proponiamo consiste in una serie di tecniche che, tenendo in considerazione il problema della competizione interna, operano su una rappresentazione fattorizzata dello spazio di ottimizzazione congiunto. Esse sono il risultato della combinazione di diversi risultati della letteratura Multi-armed Bandit (MAB) e Cooperative Learning (CL). Le tecniche di MAB si concentrano sull'ottenere performance ottime in problemi di decisione sequenziale su singolo stato, bilanciando l'esplorazione e lo sfruttamento di quanto già appreso sulla base dei risultati ottenuti in passato, mentre quelle di CL affrontano il problema di coordinare un insieme di agenti distribuiti, che operano in un ambiente comune, per massimizzare una metrica di utilità condivisa. Distribuendo il carico computazionale su più agenti in cooperazione, le nostre tecniche sono in grado di trovare lo schema di prezzi ottimo con requisiti di tempo e spazio ragionevoli, in scenari realistici. Testandole sia in contesti di ottimizzazione generica che in contesti pricing, abbiamo ottenuto risultati promettenti e superato, relativamente alle metriche di maggiore interesse per l'applicazione, tutte le baseline considerate.