Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any $p \in [1/2,1]$ there exists an infinite partial monitoring game for which the minimax regret over $n$ rounds is $n^p$ up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is $n^{4/7}$ up to subpolynomial factors.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the infor…
Decision Theory for Treatment Choice Problems with Partial Identification
We apply classical statistical decision theory to a large class of treatment choice problems with partial identification. We show that, in a general class of problems with Gaussian likelihood, all decision rules are admi…
AllExploration by Optimisation in Partial Monitoring
We provide a simple and efficient algorithm for adversarial $k$-action $d$-outcome non-degenerate locally observable partial monitoring game for which the $n$-round minimax regret is bounded by $6(d+1) k^{3/2} \sqrt{n \l…
Online Learning with Gaussian Payoffs and Side Observations
We consider a sequential learning problem with Gaussian payoffs and side information: after selecting an action $i$, the learner receives information about the payoff of every action $j$ in the form of Gaussian observati…
Information Directed Sampling for Linear Partial Monitoring
Partial monitoring is a rich framework for sequential decision making under uncertainty that generalizes many well known bandit models, including linear, combinatorial and dueling bandits. We introduce information direct…
Decision MakingDecision Making Under UncertaintySequential Decision Making