Author name cluster

Alessandro Nuara

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

EWRL Workshop 2022 Workshop Paper

Dynamic Pricing with Online Data Aggregation and Learning

Gianmarco Genalti
Marco Mussi
Alessandro Nuara
Nicola Gatti

In several e-commerce scenarios, pricing long-tail products effectively is a central task for the companies, and there is broad agreement that Artificial Intelligence (AI) will play a prominent role in doing that in the next future. Nevertheless, dealing with long-tail products raises major open technical issues due to data scarcity which preclude the adoption of the mainstream approaches requiring usually a huge amount of data, such as, e.g., deep learning. In this paper, we provide a novel online learning algorithm for dynamic pricing that deals with non-stationary settings—due to, e.g., the seasonality or adaptive competitors—, and is very efficient in terms of the need for data thanks to assumptions—such as, e.g., the monotonicity of the demand curve in the price—that are customarily satisfied in long-tail markets. Furthermore, our dynamic pricing algorithm is paired with a clustering algorithm for the long-tail products which aggregates similar products such that the data of all the products of the same cluster are merged and used to choose their best price. We first evaluate our algorithms in an offline synthetic setting, comparing their performance with the state of the art and showing that our algorithms are more robust and data-efficient in long-tail settings. Subsequently, we evaluate our algorithms in an online setting with more than 8, 000 products, including popular and long-tail, in an A/B test with humans for about two months. The increase of revenue thanks to our algorithms is about 18% for the popular products and about 90% for the long-tail products.

PDF Details

AIJ Journal 2022 Journal Article

Online joint bid/daily budget optimization of Internet advertising campaigns

Alessandro Nuara
Francesco Trovò
Nicola Gatti
Marcello Restelli

Pay-per-click advertising includes various formats (e. g. , search, contextual, social) with a total investment of more than 200 billion USD per year worldwide. An advertiser is given a daily budget to allocate over several campaigns, mainly distinguishing for the ad, target, or channel. Furthermore, publishers choose the ads to display and how to allocate them employing auctioning mechanisms, in which, every day and for each campaign, the advertisers set a bid corresponding to the maximum amount of money per click they are willing to pay and the fraction of the daily budget to invest. In this paper, we study the problem of automating the online joint bid/daily budget optimization of pay-per-click advertising campaigns over multiple channels, and we face the challenging goal of designing techniques with theoretical guarantees that can be applied in real-world applications, where, commonly, data scarcity is a crucial issue. We formulate our problem as a combinatorial semi-bandit problem, which requires solving a special case of the Multiple-Choice Knapsack problem every day. Furthermore, we address data scarcity by designing a model for the dependency of the number of clicks on the bid and daily budget, requiring few parameters at the cost of mild regularity assumptions. We propose two algorithms—the first is randomized, while the second is deterministic—and show that they suffer from a regret that is upper bounded with high probability as O ˜ ( T ), where T is the time horizon of the learning process. We experimentally evaluate our algorithms with synthetic settings generated from real data provided by Yahoo! , and we present the results of adopting our algorithms in a real-world application with a daily spent of 1, 000 Euros for more than one year.

Details DOI

JMLR Journal 2021 Journal Article

Gaussian Approximation for Bias Reduction in Q-Learning

Carlo D'Eramo
Andrea Cini
Alessandro Nuara
Matteo Pirotta
Cesare Alippi
Jan Peters
Marcello Restelli

Temporal-Difference off-policy algorithms are among the building blocks of reinforcement learning (RL). Within this family, Q-Learning is arguably the most famous one, which has been widely studied and extended. The update rule of Q-learning involves the use of the maximum operator to estimate the maximum expected value of the return. However, this estimate is positively biased, and may hinder the learning process, especially in stochastic environments and when function approximation is used. We introduce the Weighted Estimator as an effective solution to mitigate the negative effects of overestimation in Q-Learning. The Weighted Estimator estimates the maximum expected value as a weighted sum of the action values, with the weights being the probabilities that each action value is the maximum. In this work, we study the problem from the statistical perspective of estimating the maximum expected value of a set of random variables and provide bounds to the bias and the variance of the Weighted Estimator, showing its advantages over other estimators present in literature. Then, we derive algorithms to enable the use of the Weighted Estimator, in place of the Maximum Estimator, in online and batch RL, and we introduce a novel algorithm for deep RL. Finally, we empirically evaluate our algorithms in a large set of heterogeneous problems, encompassing discrete and continuous, low and high dimensional, deterministic and stochastic environments. Experimental results show the effectiveness of the Weighted Estimator in controlling the bias of the estimate, resulting in better performance than representative baselines and robust learning w.r.t. a large set of diverse environments. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

PDF Details

AAAI Conference 2018 Conference Paper

A Combinatorial-Bandit Algorithm for the Online Joint Bid/Budget Optimization of Pay-per-Click Advertising Campaigns

Alessandro Nuara
Francesco Trovò
Nicola Gatti
Marcello Restelli

Pay-per-click advertising includes various formats (e. g. , search, contextual, and social) with a total investment of more than 140 billion USD per year. An advertising campaign is composed of some subcampaigns—each with a different ad—and a cumulative daily budget. The allocation of the ads is ruled exploiting auction mechanisms. In this paper, we propose, for the ﬁrst time to the best of our knowledge, an algorithm for the online joint bid/budget optimization of payper-click multi-channel advertising campaigns. We formulate the optimization problem as a combinatorial bandit problem, in which we use Gaussian Processes to estimate stochastic functions, Bayesian bandit techniques to address the exploration/exploitation problem, and a dynamic programming technique to solve a variation of the Multiple-Choice Knapsack problem. We experimentally evaluate our algorithm both in simulation—using a synthetic setting generated a Yahoo! dataset—and in a real-world application for two months.

PDF Details

EWRL Workshop 2018 Workshop Paper

When Gaussian Processes Meet Combinatorial Bandits: GCB

Guglielmo Maria Accabi
Alessandro Nuara
Francesco Trovò
Nicola Gatti
Marcello Restelli

Combinatorial bandits (CMAB) are a generalization of the well-known Multi-Armed Bandit framework, in which the learner chooses, at each round, a subset of the available arms that satisfies some known constraints. The learner observes the payoffs of each chosen arm and aims at maximizing the cumulative reward. We study, for the first time, CMAB settings with some form of correlation over the arms expected rewards. The arm correlation is crucial to allow algorithms to be effective when the space of the arms is large. In the present paper, we propose a bandit algorithm, namely Gaussian Combinatorial Bandit (GCB), designed for settings in which the arms are partitioned in subsets, and the payoff functions of the arms of each subset are jointly distributed as a Gaussian Process (GP). We provide two different variations of our algorithm (frequentist and Bayesian) that, under mild assumptions, their worst-case regret is Õ(C √ N), where C is the number of subsets of arms whose payoffs are correlated and N is the number of rounds.1

PDF Details

AAAI Conference 2017 Conference Paper

Estimating the Maximum Expected Value in Continuous Reinforcement Learning Problems

Carlo D'Eramo
Alessandro Nuara
Matteo Pirotta
Marcello Restelli

This paper is about the estimation of the maximum expected value of an inﬁnite set of random variables. This estimation problem is relevant in many ﬁelds, like the Reinforcement Learning (RL) one. In RL it is well known that, in some stochastic environments, a bias in the estimation error can increase step-by-step the approximation error leading to large overestimates of the true action values. Recently, some approaches have been proposed to reduce such bias in order to get better action-value estimates, but are limited to ﬁnite problems. In this paper, we leverage on the recently proposed weighted estimator and on Gaussian process regression to derive a new method that is able to natively handle inﬁnitely many random variables. We show how these techniques can be used to face both continuous state and continuous actions RL problems. To evaluate the effectiveness of the proposed approach we perform empirical comparisons with related approaches.

PDF Details

ICML Conference 2016 Conference Paper

Estimating Maximum Expected Value through Gaussian Approximation

Carlo D'Eramo
Marcello Restelli
Alessandro Nuara

This paper is about the estimation of the maximum expected value of a set of independent random variables. The performance of several learning algorithms (e. g. , Q-learning) is affected by the accuracy of such estimation. Unfortunately, no unbiased estimator exists. The usual approach of taking the maximum of the sample means leads to large overestimates that may significantly harm the performance of the learning algorithm. Recent works have shown that the cross validation estimator—which is negatively biased—outperforms the maximum estimator in many sequential decision-making scenarios. On the other hand, the relative performance of the two estimators is highly problem-dependent. In this paper, we propose a new estimator for the maximum expected value, based on a weighted average of the sample means, where the weights are computed using Gaussian approximations for the distributions of the sample means. We compare the proposed estimator with the other state-of-the-art methods both theoretically, by deriving upper bounds to the bias and the variance of the estimator, and empirically, by testing the performance on different sequential learning problems.

Details