Author name cluster

Roberto Colomboni

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.

11 papers

2 author rows

ICML Conference 2025 Conference Paper

A Parametric Contextual Online Learning Theory of Brokerage

François Bachoc
Tommaso Cesari
Roberto Colomboni

We study the role of contextual information in the online learning problem of brokerage between traders. In this sequential problem, at each time step, two traders arrive with secret valuations about an asset they wish to trade. The learner (a broker) suggests a trading (or brokerage) price based on contextual data about the asset and the market conditions. Then, the traders reveal their willingness to buy or sell based on whether their valuations are higher or lower than the brokerage price. A trade occurs if one of the two traders decides to buy and the other to sell, i. e. , if the broker’s proposed price falls between the smallest and the largest of their two valuations. We design algorithms for this problem and prove optimal theoretical regret guarantees under various standard assumptions.

Details

ICLR Conference 2025 Conference Paper

An Online Learning Theory of Trading-Volume Maximization

Tommaso Cesari
Roberto Colomboni

We explore brokerage between traders in an online learning framework. At any round $t$, two traders meet to exchange an asset, provided the exchange is mutually beneficial. The broker proposes a trading price, and each trader tries to sell their asset or buy the asset from the other party, depending on whether the price is higher or lower than their private valuations. A trade happens if one trader is willing to sell and the other is willing to buy at the proposed price. Previous work provided guidance to a broker aiming at enhancing traders' total earnings by maximizing the *gain from trade*, defined as the sum of the traders' net utilities after each interaction. This classical notion of reward can be highly unfair to traders with small profit margins, and far from the real-life utility of the broker. For these reasons, we investigate how the broker should behave to maximize the trading volume, i.e., the *total number of trades*. We model the traders' valuations as an i.i.d. process with an unknown distribution. If the traders' valuations are revealed after each interaction (full-feedback), and the traders' valuations cumulative distribution function (cdf) is continuous, we provide an algorithm achieving logarithmic regret and show its optimality up to constants. If only their willingness to sell or buy at the proposed price is revealed after each interaction ($2$-bit feedback), we provide an algorithm achieving poly-logarithmic regret when the traders' valuations cdf is Lipschitz and show its near-optimality. We complement our results by analyzing the implications of dropping the regularity assumptions on the unknown traders' valuations cdf. If we drop the continuous cdf assumption, the regret rate degrades to $\Theta(\sqrt{T})$ in the full-feedback case, where $T$ is the time horizon. If we drop the Lipschitz cdf assumption, learning becomes impossible in the $2$-bit feedback case.

Details

EWRL Workshop 2025 Workshop Paper

Market Making without Regret

Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni
Luigi Foscari
Vinayak Pathak

We consider a sequential decision-making setting where, at every round $t$, the learner (a \emph{market maker}) post s a \emph{bid} price $B_t$ and an \emph{ask} price $A_t$ to an incoming trader (the \emph{taker}) with a private valuation for some asset. If the trader's valuation is lower than the bid price, or higher than the ask price, then a trade (sell or buy) occu rs. Letting $P_t$ be the market price (observed only at the end of round $t$), the maker's utility is $P_t-B_t$ if the maker bought the asset, it is $A_t-P_t$ if they sold it, and it is $0$ if no trade occurred. We characterize the maker's regret with respect to the best fixed choice of bid and ask pairs under a variety of ass umptions (adversarial, i. i. d. , and their variants) on the sequence of market prices and valuations. Our upper bound analysis unveils an intriguing connection relating market making to first-price auctions and dynamic pricing. Our main technical contribution is a lower bound for the i. i. d. \ case with Lipschitz distributions and independence between market prices and takers' valuations. The difficulty in the analysis stems from a unique relationship between the reward and feedback functions that allow s learning algorithms to trade off reward for information in a continuous way.

PDF

NeurIPS Conference 2025 Conference Paper

Online Bilateral Trade With Minimal Feedback: Don’t Waste Seller’s Time

Francesco Bacchiocchi
Matteo Castiglioni
Roberto Colomboni
Alberto Marchesi

Online learning algorithms for designing optimal bilateral trade mechanisms have recently received significant attention. This paper addresses a key inefficiency in prior two-bit feedback models, which synchronously query both the buyer and the seller for their willingness to trade. This approach is inherently inefficient as it offers a trade to the seller even if the buyer rejects the offer. We propose an asynchronous mechanism that queries the seller only if the buyer has already accepted the offer. Consequently, the mechanism receives one bit of feedback from the buyer and a "censored" bit from the seller---a signal richer than the standard one-bit (trade/no-trade) feedback, but less informative than the two-bit model. Assuming independent valuations with bounded densities---the same distributional conditions underlying the two-bit results of Cesa-Bianchi et al. [2024a]---we design an algorithm that achieves $\tilde{O}(T^{2/3})$ regret against the best fixed price in hindsight. This matches the lower bound for the strictly richer two-bit model, showing that our mechanism elicits the minimal feedback necessary to attain optimal rates.

PDF Details

NeurIPS Conference 2025 Conference Paper

Online Learning in the Repeated Mediated Newsvendor Problem

Nataša Bolić
Tom Cesari
Roberto Colomboni
Christian Paravalos

Motivated by real-life supply chain management, we study a repeated newsvendor problem in which the learner is a mediator that facilitates trades between suppliers and retailers in a sequence of supplier/retailer interactions. At each time step, a new supplier and retailer join the mediator's platform with a private production cost and utility function, respectively, and the platform proposes a unitary trading price. The supplier accepts the proposed price if it meets or exceeds their unitary production cost and communicates their decision to the platform; simultaneously, the retailer decides the quantity to purchase at the proposed trading price based on their private utility function and sends their decision to the platform. If the supplier accepts the trading price, the transaction proceeds, and the retailer purchases their chosen quantity of units, paying the product of this quantity and the trading price to the supplier. The mediator's objective is to maximize social welfare. We design an online mediator's pricing strategy that features sharp regret rates under some natural assumptions, and we investigate the necessity of these assumptions, proving that relaxing any of them leads to unlearnability.

PDF Details

TMLR Journal 2024 Journal Article

A Theoretical Framework for Zeroth-Order Budget Convex Optimization

François Bachoc
Tommaso Cesari
Roberto Colomboni
Andrea Paudice

This paper studies a natural generalization of the problem of minimizing a convex function $f$ by querying its values sequentially. At each time-step $t$, the optimizer selects a query point $X_t$ and invests a budget $b_t$ (chosen by the environment) to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy depends on the amount of budget invested in $X_t$ across times. This setting is motivated by the minimization of objectives whose values can only be determined approximately through lengthy or expensive computations, where it is paramount to recycle past information. In the univariate case, we design ReSearch, an anytime parameter-free algorithm for which we prove near-optimal optimization-error guarantees. Then, we present two applications of our univariate analysis. First, we show how to use ReSearch for stochastic convex optimization, obtaining theoretical and empirical improvements on state-of-the-art benchmarks. Second, we handle the $d$-dimensional budget problem by combining ReSearch with a coordinate descent method, presenting theoretical guarantees and experiments.

PDF Details

AAMAS Conference 2024 Conference Paper

An Online Learning Theory of Brokerage

Nata&scaron; a Bolić
Tommaso Cesari
Roberto Colomboni

We investigate brokerage between traders from an online learning perspective. At any round 𝑡, two traders arrive with their private valuations, and the broker proposes a trading price. Unlike other bilateral trade problems already studied in the online learning literature, we focus on the case where there are no designated buyer and seller roles: each trader will attempt to either buy or sell depending on the current price of the good. We assume the agents’ valuations are drawn i. i. d. from a fixed but unknown distribution. If the distribution admits a density bounded by some constant 𝑀, then, for any time horizon 𝑇: • If the agents’ valuations are revealed after each interaction, we provide an algorithm achieving regret 𝑀 log𝑇 and show this rate is optimal, up to constant factors. • If only their willingness to sell or buy at the proposed price is revealed after each interaction, we provide an algorithm achieving regret √ 𝑀𝑇 and show this rate is optimal, up to constant factors. Finally, if we drop the bounded density assumption, we show that the optimal rate degrades to √ 𝑇 in the first case, and the problem becomes unlearnable in the second.

PDF

NeurIPS Conference 2024 Conference Paper

Fair Online Bilateral Trade

François Bachoc
Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni

In online bilateral trade, a platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' valuation and higher than the sellers' valuation, then a trade takes place. Previous work focused on the platform perspective, with the goal of setting prices maximizing the *gain from trade* (the sum of sellers' and buyers' utilities). Gain from trade is, however, potentially unfair to traders, as they may receive highly uneven shares of the total utility. In this work we enforce fairness by rewarding the platform with the _fair gain from trade_, defined as the minimum between sellers' and buyers' utilities. After showing that any no-regret learning algorithm designed to maximize the sum of the utilities may fail badly with fair gain from trade, we present our main contribution: a complete characterization of the regret regimes for fair gain from trade when, after each interaction, the platform only learns whether each trader accepted the current price. Specifically, we prove the following regret bounds: $\Theta(\ln T)$ in the deterministic setting, $\Omega(T)$ in the stochastic setting, and $\tilde{\Theta}(T^{2/3})$ in the stochastic setting when sellers' and buyers' valuations are independent of each other. We conclude by providing tight regret bounds when, after each interaction, the platform is allowed to observe the true traders' valuations.

PDF Details DOI

JMLR Journal 2024 Journal Article

Regret Analysis of Bilateral Trade with a Smoothed Adversary

Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni
Federico Fusco
Stefano Leonardi

We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We completely characterize the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post the same or different prices to buyers and sellers. We begin by showing that, in the full-feedback scenario, the minimax regret after $T$ rounds is of order $\sqrt{T}$. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$, ignoring log factors. We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the paper's main technical contribution. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

PDF Details

STOC Conference 2024 Conference Paper

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni
Federico Fusco 0001
Stefano Leonardi 0001

We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item’s value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction’s transparency , which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder’s valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

Details

JMLR Journal 2022 Journal Article

Nonstochastic Bandits with Composite Anonymous Feedback

Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni
Claudio Gentile
Yishay Mansour

We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over the subsequent rounds in an adversarial way. The instantaneous loss observed by the player at the end of each round is then a sum of many loss components of previously played actions. This setting encompasses as a special case the easier task of bandits with delayed feedback, a well-studied framework where the player observes the delayed losses individually. Our first contribution is a general reduction transforming a standard bandit algorithm into one that can operate in the harder setting: We bound the regret of the transformed algorithm in terms of the stability and regret of the original algorithm. Then, we show that the transformation of a suitably tuned FTRL with Tsallis entropy has a regret of order $\sqrt{(d+1)KT}$, where $d$ is the maximum delay, $K$ is the number of arms, and $T$ is the time horizon. Finally, we show that our results cannot be improved in general by exhibiting a matching (up to a log factor) lower bound on the regret of any algorithm operating in this setting. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

PDF Details