Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring

2015-09-30 · NeurIPS 2015 12 · Junpei Komiyama, Junya Honda, Hiroshi Nakagawa

Partial monitoring is a general model for sequential learning with limited feedback formalized as a game between two players. In this game, the learner chooses an action and at the same time the opponent chooses an outcome, then the learner suffers a loss and receives a feedback signal. The goal of the learner is to minimize the total loss. In this paper, we study partial monitoring with finite actions and stochastic outcomes. We derive a logarithmic distribution-dependent regret lower bound that defines the hardness of the problem. Inspired by the DMED algorithm (Honda and Takemura, 2010) for the multi-armed bandit problem, we propose PM-DMED, an algorithm that minimizes the distribution-dependent regret. PM-DMED significantly outperforms state-of-the-art algorithms in numerical experiments. To show the optimality of PM-DMED with respect to the regret bound, we slightly modify the algorithm by introducing a hinge function (PM-DMED-Hinge). Then, we derive an asymptotically optimal regret upper bound of PM-DMED-Hinge that matches the lower bound.

📄 PDF Abstract BibTeX arXiv:1509.09011

Code (0)

등록된 구현이 없습니다.

Regret Analysis of the Anytime Optimally Confident UCB Algorithm

2016-03-29 · Tor Lattimore

I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is si…

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

2026-03-25 · Guy Zamir, Matthew Zurek, Yudong Chen arxiv

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-i…

Reinforcement Learning

Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning

2021-07-02 · NeurIPS 2021 12 · Christoph Dann, Teodor V. Marinov, Mehryar Mohri, Julian Zimmert

We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend on alternative definitions of gaps. These definitions are…

reinforcement-learning Reinforcement Learning (RL)

Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

2019-06-12 · NeurIPS 2019 12 · Zihan Zhang, Xiangyang Ji

We present an algorithm based on the \emph{Optimism in the Face of Uncertainty} (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space e…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Bounded Regret for Finite-Armed Structured Bandits

2014-11-11 · NeurIPS 2014 12 · Tor Lattimore, Remi Munos

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circum…