Matteo Castiglioni

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

Matteo Bollini, Matteo Castiglioni, Alberto Marchesi

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and ef…

Support-Dependent Regret Rates for Profit Maximization in Multilateral Trade

Francesco Bacchiocchi, Matteo Castiglioni, Anna Lunghi +1

We study online profit maximization in multilateral trade, a setting that generalizes both dynamic pricing and bilateral trade. At each round, an intermediary posts prices to buyer…

cs.DS2026

A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +2

Subsampling theorems for constraint satisfaction problems (CSPs) guarantee that the value of the CSP is approximately preserved after restricting it to small random subsets of vari…

cs.DS2026

A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree- $d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{…

Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

We study regret minimization for learning CDF-related objectives of the form \[ g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), \] over $[0, 1]^{2}$ , where $g$ is a known Lipschitz fu…

Decoupling Corruption and Horizon in Robust Contextual Pricing

Matteo Castiglioni, Francesco Emanuele Stradi

We study robust repeated contextual pricing, where valuations depends linearly on the features. At each round $t \in [T]$ , a seller observes a context, posts a price, and receives on…

cs.DS2026

Min-Max Optimization Requires Exponentially Many Queries

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0, 1]^{d} \times [0, 1]^{d}$ . We show that, given oracle access to $f$ and to its grad…

Online Resource Allocation With General Constraints

Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Matteo Castiglioni +1

Online resource allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints, with applications ranging from online advertising to r…

Regret Minimization in Bilateral Trade With Perturbed Markets

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in…

Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time

Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni +1

We design the first regret guarantees for robust dynamic pricing that decouple the dependence on the corruption $C$ and the time horizon $T$ . In dynamic pricing, a seller with unli…

Multi-Armed Bandits With Best-Action Queries

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1

We study \emph{multi-armed bandits} (MABs) augmented with \emph{best-action queries}, in which the learner may additionally query an oracle that reveals the best arm in the current…

Replicable Constrained Bandits

Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi +2

Algorithmic \emph{replicability} has recently been introduced to address the need for reproducible experiments in machine learning. A \emph{replicable online learning} algorithm is…

Truly Adapting to Adversarial Constraints in Constrained MABs

Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2

We study the constrained variant of the \emph{multi-armed bandit} (MAB) problem, in which the learner aims not only at minimizing the total loss incurred during the learning dynami…

A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions

Anna Lunghi, Mattia Piccinato, Matteo Castiglioni +1

We study online bilateral trade, where a learner facilitates repeated exchanges between a buyer and a seller to maximize the Gain From Trade (GFT), i.e., the social welfare. In doi…

cs.LG2026★ 1 cited

The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms

Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

We study the sample complexity of learning a uniform approximation of an $n$ -dimensional cumulative distribution function (CDF) within an error $ε > 0$ , when observations are restri…

Learning in Bayesian Stackelberg Games With Unknown Follower's Types

Matteo Bollini, Francesco Bacchiocchi, Samuel Coutts +2

We study online learning in Bayesian Stackelberg games, where a leader repeatedly interacts with a follower whose unknown private type is independently drawn at each round from an…

cs.LG2025

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2

We study \emph{online episodic Constrained Markov Decision Processes} (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees great…

Better Regret Rates in Bilateral Trade via Sublinear Budget Violation

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

Bilateral trade is a central problem in algorithmic economics, and recent work has explored how to design trading mechanisms using no-regret learning algorithms. However, no-regret…

cs.LG2025

Data-Dependent Regret Bounds for Constrained MABs

Gianmarco Genalti, Francesco Emanuele Stradi, Matteo Castiglioni +2

This paper initiates the study of data-dependent regret bounds in constrained MAB settings. These bounds depend on the sequence of losses that characterize the problem instance. Th…

cs.LG2025

No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!

Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi +2

We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We f…

The Complexity of Correlated Equilibria in Generalized Games

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

Correlated equilibria -- and their generalization $Φ$ -equilibria -- are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in mu…

Online Two-Sided Markets: Many Buyers Enhance Learning

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

We study a repeated trading problem in which a mechanism designer facilitates trade between a single seller and multiple buyers. Our model generalizes the classic bilateral trade s…

Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1

Most microeconomic models of interest involve optimizing a piecewise linear function. These include contract design in hidden-action principal-agent problems, selling an item in po…