A learning approach for pricing in e-commerce scenario

Over the past few years, there has been a significant increase in the use of e-commerce websites. Nowadays, almost everything can be bought online, and market research shows that the online market is steadily growing. With the spread of e-commerce, metasearch engines began to arise, which conduct searches across multiple independent e-commerce, as a response to the need of users to compare offerings without having to consult each website individually. Metasearch engines effectively act as middlemen, sending a large portion of the traffic to e-commerce, but giving them barely no information about customers' behavior and purchasing history. In this thesis, we investigate the problem of optimal pricing in the setting of online sales of goods from the point of view of an e-commerce selling its products in the profitable and challenging environment of metasearch engines. In this setting, we have a vast catalog of items to price, no information about our customers, low conversion rates and the environment is non-stationary. We study the problem of finding the pricing strategy that maximizes the profit of the e-commerce selling its products in this scenario. We propose an automatic pricing system which uses clustering techniques to partition the catalog of items into subsets sharing similar features, and machine learning techniques to learn the optimal price of each subset. First, we deal with the problem of partitioning the catalog of items. We tackle it by learning from historical data collected by the interactions with customers. We propose a novel algorithm which, differently from existing solutions, provides a clear interpretability to business analysts of the resulting model and a risk-averse pricing policy to maximize the profit. With a wide experimental campaign, we present empirical evidence for the improved performance of our algorithm over the state-of-the-art ones. Then, we study algorithms to learn the optimal policy to follow in each of the subset. We focus on online learning techniques, in particular on the Multi-Armed Bandit ones, widely studied in the machine learning literature. Even if existing general-purpose algorithms can be applied to the pricing task, we propose novel algorithms exploiting the properties of the pricing problem (some of them already studied in literature, other unexplored so far). We derive upper bounds over the regret for the proposed algorithms and we present a thorough experimental evaluation in a wide range of configurations, some of them based on real-world data, showing that we significantly improve the performances of the state-of-the-art algorithms. The clustering algorithm and the online learning policies we propose are interconnected and continuously communicating. Indeed, the data generated from the interaction of the users with the bandits algorithms are collected and passed through the clustering algorithm to update the partitioning and to improve the performance of the system.

Negli ultimi anni, si è verificato un significativo aumento dell'utilizzo degli e-commerce e degli acquisti online. Al giorno d'oggi, praticamente ogni bene può essere acquistato online e ricerche di mercato mostrano che il valore del mercato online è in costante crescita. In seguito alla diffusione degli e-commerce, sistemi di ricerca denominati metasearch hanno iniziato a prendere piede. Questi sistemi conducono ricerche su molteplici siti di e-commerce e aggregano i risultati per poi mostrarli agli utenti. L'elevato utilizzo dei metasearch è nato in risposta all'esigenza degli utenti di confrontare le offerte per un prodotto senza dover consultare più siti separatamente. Lo scenario della vendita online di prodotti di viaggio, come biglietti aerei e hotel, è un esempio degno di nota in cui il ruolo dei metasearch ha acquisito una grande importanza. Difatti, i metasearch agiscono da intermediari, generando grandi quantitativi di traffico per gli e-commerce ma fornendogli poche informazioni sugli utenti, rendendo difficile analizzarne il comportamento non avendo accesso allo storico delle ricerche effettuate. In questa tesi, investighiamo lo scenario della vendita online di prodotti da parte di un e-commerce che opera in un ambiente in cui sono presenti metasearch e studiamo il problema del pricing ottimo, ovvero della ricerca della strategia che massimizza il profitto dell'e-commerce. Questo ambiente presenta grandi possibilità di profitto, ma anche una serie di caratteristiche che rendono impegnativa la ricerca di una soluzione. Abbiamo un vasto catalogo di prodotti e poche informazioni sui nostri clienti. Inoltre, la maggior parte degli utenti fa ricerche senza l'effettivo intento di comprare, ma solo per informarsi o tenere d'occhio i prezzi, andando a generare un enorme quantitativo di ricerche di cui solo poche convertono realmente in acquisti. Infine, il mercato è non stazionario, dato che presenta effetti di stagionalità e un alto numero di competitor. Come soluzione, proponiamo un sistema automatico di pricing che utilizza tecniche di clustering per partizionare il catalogo in sottoinsiemi di prodotti con caratteristiche simili, e tecniche di machine learning per apprendere il prezzo ottimo da impostare su ciascuno dei prodotti all'interno dei sottoinsiemi selezionati. Inizialmente, approcciamo il problema del clustering, studiando algoritmi che apprendono dai dati storici generati dall'interazione con gli utenti. L'algoritmo che proponiamo, a differenza delle soluzioni esistenti in letteratura, fornisce una chiara interpretabilità del modello generato e segue una politica avversa al rischio, fattori molto importanti in ambito economico. Con una estesa campagna sperimentale, mostriamo empiricamente i migliori risultati ottenuti dal nostro algoritmo in confronto agli algoritmi dello stato dell'arte. In seguito, studiamo algoritmi per la ricerca della strategia ottima da seguire in ogni sottoinsieme generato dal partizionamento. Ci focalizziamo su tecniche di online learning, in particolare su quelle di Multi-Armed Bandit, ampiamente studiate in letteratura. Nonostante sia possibile utilizzare algoritmi generici per risolvere il nostro problema, gli algoritmi che proponiamo sono in grado di ottenere risultati migliori sfruttando informazioni sulla struttura del problema. Per fornire assicurazioni teoriche, presentiamo upper bounds sul regret ottenuto dai nostri algoritmi e, con un'ampia campagna sperimentale basata su dati reali, mostriamo il miglioramento significativo dei risultati ottenuti dai nostri algoritmi rispetto a quelli della letteratura. Nell'architettura finale del sistema proposto, l'algoritmo per il partizionamento dei prodotti e gli algoritmi per apprendere la strategia ottima sono interconnessi. Infatti, i dati generati dall'interazione degli utenti con i nostri algoritmi di learning sono collezionati e passati all'algoritmo di clustering in modo da aggiornare ciclicamente il partizionamento e migliorare le performance del sistema.