29 papers
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…
A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
The paper presents a method to construct ε‑covers for the joint value sets of constant-degree polynomials over convex domains, enabling quasi‑polynomial time approximation schemes…
Breaking the 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 , where is a known Lipschitz fu…
Decoupling Corruption and Horizon in Robust Contextual Pricing
Matteo Castiglioni, Francesco Emanuele Stradi
The paper proposes an online algorithm for repeated contextual pricing that tolerates a bounded number of corrupted sale feedbacks, achieving regret that scales with the corruption…
Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2
The paper proposes a new online algorithm for episodic constrained Markov decision processes that achieves sublinear regret and constraint violation without assuming Slater's condi…
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
Gianmarco Genalti, Marco Mussi, Nicola Gatti +3
Rested and Restless Bandits are two well-known bandit settings that are useful to model real-world sequential decision-making problems in which the expected reward of an arm evolve…