HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning and Monte Carlo Tree Search

2024-11-01 · Tuan Ngo Nguyen, Jay Barrett, Kwang-Sung Jun

We study the problem of estimating the \emph{value} of the largest mean among K distributions via samples from them (rather than estimating \emph{which} distribution has the largest mean), which arises from various machine learning tasks including Q-learning and Monte Carlo Tree Search (MCTS). While there have been a few proposed algorithms, their performance analyses have been limited to their biases rather than a precise error metric. In this paper, we propose a novel algorithm called HAVER (Head AVERaging) and analyze its mean squared error. Our analysis reveals that HAVER has a compelling performance in two respects. First, HAVER estimates the maximum mean as well as the oracle who knows the identity of the best distribution and reports its sample mean. Second, perhaps surprisingly, HAVER exhibits even better rates than this oracle when there are many distributions near the best one. Both of these improvements are the first of their kind in the literature, and we also prove that the naive algorithm that reports the largest empirical mean does not achieve these bounds. Finally, we confirm our theoretical findings via numerical experiments where we implement HAVER in bandit, Q-learning, and MCTS algorithms. In these experiments, HAVER consistently outperforms the baseline methods, demonstrating its effectiveness across different applications.

📄 PDF Abstract BibTeX arXiv:2411.00405

Code (0)

등록된 구현이 없습니다.

Tasks

Q-Learning

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Accelerated and instance-optimal policy evaluation with linear function approximation

2021-12-24 · Tianjiao Li, Guanghui Lan, Ashwin Pananjady

We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish bas…

Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning

2018-09-10 · Quentin Cappart, Emmanuel Goutierre, David Bergman, Louis-Martin Rousseau

Finding tight bounds on the optimal solution is a critical element of practical solution methods for discrete optimization problems. In the last decade, decision diagrams (DDs) have brought a new perspective on obtaining…

BIG-bench Machine Learning Combinatorial Optimization Deep Reinforcement Learning reinforcement-learning+2

Online Prediction with Limited Selectivity

2025-08-13 · Licheng Liu, Mingda Qiao arxiv

Selective prediction [Dru13, QV19] models the scenario where a forecaster freely decides on the prediction window that their forecast spans. Many data statistics can be predicted to a non-trivial error rate without any d…

Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs

2022-03-17 · Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann

In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. While minimax optimal algorithms exist for this problem, its…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Data-dependent Generalization Bounds via Variable-Size Compressibility

2023-03-09 · Milad Sefidgaran, Abdellatif Zaidi

In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework that we introduce newly here. In this framework, the generalizatio…

Generalization Bounds