31 papers
Kernel Methods for Refined Prophet Inequalities
Patrick Loiseau, Mathieu Molina, Vianney Perchet +2
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irr…
Learning When to Automate: Queue Control in Human-AI Service Systems
Giovanni Montanari, Marco Scarsini, Vianney Perchet
We study a human-AI service system in which tasks arrive sequentially and are processed through a two-stage architecture: an automated chatbot followed, when necessary, by a human…
I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case
Jung-hun Kim, Vianney Perchet
We study prophet inequalities with discounted rewards, where i.i.d. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitr…
Asymptotically Optimal Learning for Parametric Prophet Inequalities
Jung-hun Kim, Anna Grebennikova, Vianney Perchet
We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter , a class that includes exponential, Pa…
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Corentin Pla, Hugo Richard, Marc Abeille +1
We study PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts, with discount factor , finite state space , action space $\mat…
Prophet Inequalities under Local Differential Privacy
Achraf Azize, Mathieu Molina, Hugo Richard +1
Many online decision platforms, from hiring marketplaces to auctions, face a tension between efficient decision-making and the protection of participants' privacy. Personal informa…