15 papers · 1 filter
No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints
Davide Maran, Marcello Restelli, Francesco Emanuele Stradi
Market makers keep trading efficient by setting bid and ask prices for buyers and sellers. In sequential market making, trades happen independently based on price thresholds, requi…
Instance-Dependent Regret for CMDPs with Step-Wise Constraints
Qian Zuo, Francesco Emanuele Stradi, Leyang Xue +1
We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that…
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 and the time horizon . 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…
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…
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…
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…
Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi +1
We study online learning in \emph{constrained MDPs} (CMDPs), focusing on the goal of attaining sublinear strong regret and strong cumulative constraint violation. Differently from…
Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni +2
We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial. In such settings, Stradi et al.(…
A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints
Francesco Emanuele Stradi, Filippo Cipriani, Lorenzo Ciampiconi +3
We address the challenging problem of dynamically pricing complementary items that are sequentially displayed to customers. An illustrative example is the online sale of flight tic…
Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni +2
In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear re…
Learning Adversarial MDPs with Stochastic Hard Constraints
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi +1
We study online learning in constrained Markov decision processes (CMDPs) with adversarial losses and stochastic hard constraints, under bandit feedback. We consider three scenario…
A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints
Jacopo Germano, Francesco Emanuele Stradi, Gianmarco Genalti +3
We study online learning in episodic constrained Markov decision processes (CMDPs), where the learner aims at collecting as much reward as possible over the episodes, while satisfy…