Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fast and Accurate Repeated Decision Making

Abstract : We study a setting in which a learner faces a sequence of decision tasks and is required to make good decisions as quickly as possible. Each task n is associated with a pair (Xn, µn), where Xn is a random variable and µn is its (unknown and potentially negative) expectation. The learner can draw arbitrarily many i.i.d. samples of Xn but its expectation µn is never revealed. After some sampling is done, the learner can decide to stop and either accept the task, gaining µn as a reward, or reject it, getting zero reward instead. A distinguishing feature of our model is that the learner's performance is measured as the expected cumulative reward divided by the expected cumulative number of drawn samples. The learner's goal is to converge to the per-sample reward of the optimal policy within a fixed class. We design an online algorithm with data-dependent theoretical guarantees for finite sets of policies, and analyze its extension to infinite classes of policies. A key technical aspect of this setting, which sets it aside from stochastic bandits, is the impossibility of obtaining unbiased estimates of the policy's performance objective.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Tommaso Cesari <>
Submitted on : Monday, February 15, 2021 - 1:01:30 PM
Last modification on : Thursday, February 18, 2021 - 3:32:20 AM


Files produced by the author(s)


  • HAL Id : hal-02976864, version 2
  • ARXIV : 1905.11797



Nicolò Cesa-Bianchi, Tommaso Cesari, Yishay Mansour, Vanney Perchet. Fast and Accurate Repeated Decision Making. 2021. ⟨hal-02976864v2⟩



Record views


Files downloads