Partial Monitoring - Classification, Regret Bounds, and Algorithms

By Gábor Bartók, Dean Phillips Foster, Dávid Pál, Alexander Rakhlin, Csaba Szepesvari. 2014

183 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistical Learning Theory, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistical Learning Theory

In Game & Decision Theory

Citations in the corpus

Surprising Negative Results for Generative Adversarial Tree Search (2018, background): “Furthermore, more general settings like partial monitoring games are theoretically tackled (Bartók et al., 2014) and minmax regret guarantees are provided.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “Perhaps the most well-known case is the multi-armed bandits problem [18, 8, 7], with many other variants being developed, such as contextual bandits [39, 41], combinatorial bandits [21], and more general models such as partial monitoring [18, 13].”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “[14] tackles a general case of partial monitoring games and provides minimax regret guarantee.”
Learning to Optimize via Information-Directed Sampling (2014, background): “Recent work [11] has focused on classifying the minimax-optimal scaling of regret in the problem’s time horizon as a function of the level of feedback the agent receives.”
A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (2015, background): “As mentionned earlier, the dueling bandits problem is a special instance of a partial monitoring game (Piccolboni and Schindelhauer, 2001; Cesa-Bianchi and Lugosi, 2009; Bartók et al., 2014).”
Causal Bandits: Learning Good Interventions via Causal Inference (2016, background): “Most recently, Alon et al. (2015), Kocák et al. (2014) have considered very general models related to partial monitoring games (Bartók et al., 2014) where rewards on unplayed actions are revealed according to a feedback graph.”
Introduction to Multi-Armed Bandits (2019, background): “Another model, termed partial monitoring (Bartók et al., 2014; Antos et al., 2013), posits that the outcome for choosing an arm a is a (reward, feedback) pair, where the feedback can be an arbitrary message.”
Stochastic matrix games with bandit feedback (2020, background): “Partial monitoring is now reasonably well understood theoretically [7] and sensible algorithms exist [22].”
Sample-Efficient Deep RL with Generative Adversarial Tree Search (2018, background): “Furthermore, Bartók et al. (2014) tackles the general case of partial monitoring games and provides a minimax regret guarantee that is polynomial in certain dimensions of the problem.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “Gajane and Urvoy (2015) study the dueling bandit problem as an instance of a partial monitoring (PM) problem (Bart´ok et al., 2011; Bart´ok, 2013; Bart´ok et al., 2014)—a generic model for sequential decision-making with incomplete feedback, which is deﬁned by a quin-tuple ( N , M , Σ , L , H ),…”
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods (2016, background): “(Bartók et al., 2014) tackles a general case of partial monitoring games and provides minimax regret guarantee which is polynomial in certain dimensions of the problem.”