Near-optimal Regret Bounds for Reinforcement Learning

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Journal of machine learning research

• Publication date

  2008-12-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.5555/1756006.1859902
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Piecewise-stationary bandit problems with side observations

  2009cited by this paper
• Online Markov Decision Processes

  2009cited by this paper
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

  2009cited by this paper
• An analysis of model-based Interval Estimation for Markov Decision Processes

  2008influential reference
• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

  2008cited by this paper
• Markov Decision Processes with Arbitrary Reward Processes

  2008influential reference
• Bounded Parameter Markov Decision Processes with Average Reward Criterion

  2007cited by this paper
• Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs

  2007influential reference
• PAC model-free reinforcement learning

  2006cited by this paper
• Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning

  2006cited by this paper
• A theoretical analysis of Model-Based Interval Estimation

  2005cited by this paper
• The Sample Complexity of Exploration in the Multi-Armed Bandit Problem

  2004cited by this paper
• An empirical evaluation of interval estimation for Markov decision processes

  2004cited by this paper
• Experts in a Markov Decision Process

  2004cited by this paper
• On the sample complexity of reinforcement learning.

  2003cited by this paper
• Inequalities for the L1 Deviation of the Empirical Distribution

  2003cited by this paper
• Near-Optimal Reinforcement Learning in Polynomial Time

  2002cited by this paper
• Finite-time Analysis of the Multiarmed Bandit Problem

  2002cited by this paper
• The Nonstochastic Multiarmed Bandit Problem

  2002influential reference
• R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

  2001cited by this paper
• Introduction to Reinforcement Learning

  1998cited by this paper
• Reinforcement Learning: An Introduction

  1998cited by this paper
• Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms

  1998cited by this paper
• Optimal Adaptive Policies for Markov Decision Processes

  1997influential reference
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Efficient reinforcement learning

  1994cited by this paper
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994influential reference
• On Tail Probabilities for Martingales

  1975cited by this paper
• WEIGHTED SUMS OF CERTAIN DEPENDENT RANDOM VARIABLES

  1967cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper

• AoI-Based Scheduling of Correlated Sources for Timely Inference

  2026cites this paper
• Policy Gradient Algorithms in Average-Reward Multichain MDPs

  2026cites this paper
• Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization

  2026cites this paper
• Generalizing the Fano inequality further

  2026cites this paper
• PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure

  2026cites this paper
• From Worst Case to Conditional Frontiers in Reinforcement Learning

  2026cites this paper
• Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

  2026cites this paper
• Optimistic World Models: Efficient Exploration in Model-Based Deep Reinforcement Learning

  2026influential citation
• In-Context Reinforcement Learning through Bayesian Fusion of Context and Value Prior

  2026influential citation
• Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

  2026cites this paper
• Near-Optimal Sample Complexity for Online Constrained MDPs

  2026cites this paper
• From Wasserstein to Maximum Mean Discrepancy Barycenters: A Novel Framework for Uncertainty Propagation in Model-Free Reinforcement Learning

  2026cites this paper
• Tuning the burn-in phase in training recurrent neural networks improves their performance

  2026cites this paper
• Reinforcement Learning for Automated Literature Screening: Enhancing E-Learning and University Research Classification in Computer Science

  2026cites this paper
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization

  2026cites this paper
• Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic

  2026cites this paper
• Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values

  2026cites this paper
• Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation

  2026cites this paper
• POPE: Learning to Reason on Hard Problems via Privileged On-Policy Exploration

  2026cites this paper
• Statistical Reinforcement Learning in the Real World: A Survey of Challenges and Future Directions

  2026cites this paper
• An identity for the bias in Markov reward processes with applications to Markov chain perturbation and Kemeny’s constant

  2026cites this paper
• Content-Aware Scheduling Policy for Goal-Oriented Status Updating With Multiple Sources

  2026cites this paper
• Learning Markov Decision Processes under Fully Bandit Feedback

  2026cites this paper
• Rationality Measurement and Theory for Reinforcement Learning Agents

  2026cites this paper
• Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

  2026cites this paper
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations

  2026cites this paper
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum

  2026cites this paper
• Track-MDP: Reinforcement Learning for Target Tracking With Controlled Sensing

  2025cites this paper
• SwiftVI: Time-Efficient Planning and Learning with MDPs

  2025cites this paper
• Auto-exploration for online reinforcement learning

  2025cites this paper
• An Empirical Study on the Effectiveness of Incorporating Offline RL As Online RL Subroutines

  2025cites this paper
• FOVA: Offline Federated Reinforcement Learning With Mixed-Quality Data

  2025cites this paper
• Provably Efficient Sample Complexity for Robust CMDP

  2025cites this paper
• Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems

  2025influential citation
• Tail Distribution of Regret in Optimistic Reinforcement Learning

  2025cites this paper
• No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes

  2025cites this paper
• Demystifying the Mechanisms Behind Emergent Exploration in Goal-conditioned RL

  2025cites this paper
• Count Counts: Motivating Exploration in LLM Reasoning with Count-based Intrinsic Rewards

  2025cites this paper
• Greedy Sampling Is Provably Efficient for RLHF

  2025cites this paper
• SOMBRL: Scalable and Optimistic Model-Based RL

  2025cites this paper
• Learning to Decide with Just Enough: Information-Theoretic Context Summarization for CMDPs

  2025cites this paper
• Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee

  2025cites this paper
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning

  2025cites this paper
• Priors Matter: Addressing Misspecification in Bayesian Deep Q-Learning

  2025cites this paper
• On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark

  2025cites this paper
• Reward-Guided Subspace Fusion and Spotlight for Multi-Agent State Space Exploration

  2025cites this paper
• UAMDP: Uncertainty-Aware Markov Decision Process for Risk-Constrained Reinforcement Learning from Probabilistic Forecasts

  2025cites this paper
• Online Policy Learning via a Self-Normalized Maximal Inequality

  2025cites this paper
• On the hardness of RL with Lookahead

  2025cites this paper
• The Confusing Instance Principle for Online Linear Quadratic Control

  2025cites this paper
• Reinforcement Learning Using known Invariances

  2025cites this paper
• Tensor-Efficient High-Dimensional Q-learning

  2025influential citation
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning

  2025cites this paper
• Hit the spot: Reachability guided subgoal generation for hierarchical reinforcement learning in stochastic environments

  2025cites this paper
• On Efficient Bayesian Exploration in Model-Based Reinforcement Learning

  2025cites this paper
• Studying Exploration in RL: An Optimal Transport Analysis of Occupancy Measure Trajectories

  2025influential citation
• Quantum algorithm for apprenticeship learning

  2025cites this paper
• Spectral Representation-based Reinforcement Learning

  2025cites this paper
• Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach

  2025cites this paper
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm

  2025cites this paper
• An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints

  2025cites this paper
• Statistical and Algorithmic Foundations of Reinforcement Learning

  2025cites this paper
• Q-Learning with Fine-Grained Gap-Dependent Regret

  2025cites this paper
• Natural Policy Gradient for Average Reward Non-Stationary RL

  2025cites this paper
• Posterior Sampling for Reinforcement Learning on Graphs

  2025cites this paper
• Toward Efficient Exploration by Large Language Model Agents

  2025cites this paper
• Smart Exploration in Reinforcement Learning Using Bounded Uncertainty Models

  2025cites this paper
• Contextual Similarity Distillation: Ensemble Uncertainties with a Single Model

  2025cites this paper
• Beyond-Expert Performance with Limited Demonstrations: Efficient Imitation Learning with Double Exploration

  2025cites this paper
• Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis

  2025cites this paper
• State-Independent Control for Constrained Markov Decision Processes With Birth-Death Dynamics

  2025cites this paper
• Offline RL with Smooth OOD Generalization in Convex Hull and its Neighborhood

  2025cites this paper
• Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds

  2025cites this paper
• Age-of-information minimization under energy harvesting and non-stationary environment

  2025influential citation
• Neural Fidelity Calibration for Informative Sim-to-Real Adaptation

  2025cites this paper
• Influential Bandits: Pulling an Arm May Change the Environment

  2025cites this paper
• Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes

  2025cites this paper
• Reinforcement Learning from Multi-level and Episodic Human Feedback

  2025cites this paper
• Multi-armed Bandit for Stochastic Shortest Path in Mixed Autonomy

  2025cites this paper
• Online Episodic Convex Reinforcement Learning

  2025cites this paper
• Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees

  2025cites this paper
• Deep Actor-Critics with Tight Risk Certificates

  2025cites this paper
• Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning

  2025cites this paper
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

  2025cites this paper
• Variation-Aware Bernstein-Based Upper Confidence Reinforcement Learning for Environment With Endogenous and Exogenous Uncertainty

  2025influential citation
• The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability

  2025influential citation
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs

  2025cites this paper
• Distributionally Robust Markov Games with Average Reward

  2025cites this paper
• Safe Learning Under Irreversible Dynamics via Asking for Help

  2025cites this paper
• Multi-policy reinforcement learning for network resource allocation with periodic behaviors

  2025cites this paper
• AoI-Based Scheduling of Correlated Sources for Timely Inference

  2025cites this paper
• Symmetry-Guided Multi-Agent Inverse Reinforcement Learning

  2025cites this paper
• Reinforcement learning algorithm for reusable resource allocation with unknown rental time distribution

  2025cites this paper
• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

  2025cites this paper
• Best of Both Worlds: Regret Minimization versus Minimax Play

  2025cites this paper
• Bayesian Optimization for Dynamic Pricing and Learning

  2025cites this paper
• ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning

  2025cites this paper
• Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewards

  2025cites this paper
• Finite-Time Bounds for Average-Reward Fitted Q-Iteration

  2025cites this paper
• Off-Policy Temporal Difference Learning for Perturbed Markov Decision Processes

  2025cites this paper