Algorithm tackles constrained reinforcement learning with concave-convex and knapsack constraints.
problem Constrained episodic reinforcement learning with concave rewards and convex constraints.
method Modular analysis with strong theoretical guarantees for concave-convex and knapsack settings.
result Significantly outperforms existing approaches in constrained episodic environments.
RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.
problem Minimizing regret in episodic MDPs with model-free methods.
method Randomized Q-learning with learning rate randomization.
result RandQL achieves optimal regret bounds in both tabular and metric state-action spaces.
Efficiently identifies best policies in tabular MDPs with reduced computational cost.
problem Identifying the best policy in tabular MDPs with high computational cost.
method Combines posterior sampling with online learning to achieve asymptotic optimality.
result Achieves optimal sample complexity and posterior contraction rate with O ( S 2 A H ) O(S^2AH) O ( S 2 A H ) per episode. New framework for reinforcement learning with adversarial preferences in tabular MDPs.
problem Learning from preferences rather than direct rewards in MDPs with adversarial settings.
method Developed PbMDPs framework, established lower bounds, and proposed algorithms for regret minimization.
result Achieved regret bounds of Ω ( ( H 2 S K ) 1 / 3 T 2 / 3 ) Ω( (H^2 S K)^{1/3} T^{2/3} ) Ω (( H 2 S K ) 1/3 T 2/3 ) for PbMDPs with Borda scores. Bayes-UCBVI tackles reinforcement learning with a new upper confidence bound method.
problem Optimizing exploration in reinforcement learning without bonuses.
method Bayes-UCBVI uses a quantile of a Q-value function posterior as an upper confidence bound.
result Proves a regret bound of order O ~ ( H 3 S A T ) \widetilde{O}(\sqrt{H^3SAT}) O ( H 3 S A T ) for tabular reinforcement learning. Long horizon reinforcement learning is as hard as short horizon learning.
problem Understanding the difficulty of long horizon reinforcement learning problems.
method Introduced new concepts: ε-net for optimal policies and Online Trajectory Synthesis algorithm.
result Proved that sample complexity scales logarithmically with the planning horizon, refuting the conjecture.
This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
New algorithm reduces RL policy optimization gap.
problem Insufficient theoretical understanding of policy optimization methods.
method Reference-based Policy Optimization with Stable at Any Time guarantee (RPO-SAT)
result Achieves nearly minimax optimal policy-based algorithm for tabular RL.
Orion-Bix combines biaxial attention and meta-learning for tabular few-shot learning.
problem Scaling and generalizing tabular models with mixed numeric and categorical fields, weak feature structure, and limited labeled data.
method Orion-Bix uses biaxial attention and meta-learned in-context reasoning to efficiently capture local and global dependencies.
result Orion-Bix outperforms gradient-boosting baselines and state-of-the-art tabular models on public benchmarks.
New method achieves nearly horizon-free offline reinforcement learning for tabular and linear MDPs.
problem Achieving efficient reinforcement learning without knowing the horizon.
method Simple recursion-based method to bound total variance in offline scenarios.
result Nearly horizon-free sample complexity bounds for offline policy evaluation and optimization.
Proposes a method to avoid excessive exploration in reinforcement learning.
problem Avoiding excessive exploration in reinforcement learning to deploy it in practice.
method Designs a novel algorithm using UCB reinforcement learning policy with adaptive exploration constraints.
result Proves that the approach remains conservative while minimizing regret in tabular settings and validates on real-world tasks.
The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.
problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.
method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.
result The proposed bounds match theoretical lower bounds up to a logarithmic term.
Deep reinforcement learning methods attain super-human performance in a wide range of environments. Such methods are grossly inefficient, often taking orders of magnitudes more data than humans to achieve reasonable performance. We propose Neural Episodic Control: a deep reinforcement learning agent that is able to rap…
New RL method learns K-step lookahead Q-functions for fixed-horizon MDPs.
problem Challenges in online reinforcement learning for non-episodic, finite-horizon MDPs.
method Introduces a K-step lookahead Q-function with a time-varying threshold for selecting actions.
result Achieves minimax optimal constant regret for K=1 and O ( max ( ( K − 1 ) , C K − 1 ) S A T log ( T ) ) \mathcal{O}(\max((K-1),C_{K-1})\sqrt{SAT\log(T)}) O ( max (( K − 1 ) , C K − 1 ) S A T log ( T ) ) regret for K ≥ 2. New algorithms reduce regret in online MDPs by adapting to data and variance.
problem Adapting to both adversarial and stochastic environments in online MDPs.
method Develops algorithms based on global optimization and policy optimization, using optimistic follow-the-regularized-leader with log-barrier regularization.
result Achieves refined data-dependent and variance-dependent regret bounds.
HyperAgent improves RL exploration in large-scale problems.
problem Efficient exploration in large-scale reinforcement learning problems.
method Hypermodel framework for incremental posterior approximation without conjugacy.
result HyperAgent achieves logarithmic per-step computational complexity and sublinear regret.
DARLING tackles non-stationary RL with guarantees, improving dynamic regret.
problem Non-stationary reinforcement learning in unknown change points.
method Detection Augmented Reinforcement Learning (DARLING) for tabular and linear MDPs.
result DARLING matches minimax lower bounds in tabular and linear MDPs.
A new RL framework allows removing user data without affecting performance.
problem Efficiently removing user data from a reinforcement learning model without affecting performance.
method Formulated a ρ ρ ρ -TV-stable RL algorithm for tabular MDPs that supports exact unlearning. result Achieved a nearly minimax optimal regret bound of Ω ( H S A T + S A H / ρ ) Ω(H\sqrt{\!SAT}\! +\! {SAH}/ρ) Ω ( H S A T + S A H / ρ ) for ρ ρ ρ -TV-stable RL algorithms. StepMix algorithm ensures safe exploration in reinforcement learning with near-optimal performance.
problem Conservative exploration in reinforcement learning under episode-wise constraints.
method StepMix algorithm balances exploitation and exploration while ensuring episode-wise conservative constraint.
result StepMix achieves near-optimal regret order as in the constraint-free setting.
Improved RL algorithm for robustness against parameter mismatches.
problem Learning robust control policies against parameter mismatches between training and testing environments.
method Formulated as DR-RL problem, proposed RPVL algorithm for tabular episodic learning with four divergences.
result Achieved i l d e O ( ∣ S ∣ ∣ A ∣ H 5 ) ilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}| H^{5}) i l d e O ( ∣ S ∣∣ A ∣ H 5 ) sample complexity uniformly better than existing results. We initiate the study of multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system extending recent results for the special case of stochastic bandits. We provide a framework which modifies the aggressive exploration enjoyed b…
Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.
problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.
method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.
result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving O ( log T ) O(\log T) O ( log T ) regret in stochastic and O ( T ) {O}(\sqrt{T}) O ( T ) regret in adversarial settings. Unified framework for model- and value-optimistic reinforcement learning.
problem Designing and analyzing algorithms for episodic reinforcement learning.
method Lagrangian duality for a unified view of optimism.
result Unified algorithms with both efficient implementation and probabilistic analysis.
We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of eac…
New framework uses unsupervised learning for efficient exploration in RL.
problem Efficient exploration in reinforcement learning with rich observations.
method Combines unsupervised learning and no-regret RL algorithms.
result Proves sample complexity for finding near-optimal policies.
UCBMQ improves Q-learning by adding momentum to correct bias and limit regret.
problem Improving Q-learning's bias and regret in reinforcement learning.
method UCBMQ combines Q-learning with an upper confidence bound and momentum term.
result UCBMQ guarantees a regret of O ( H 3 S A T + H 4 S A ) O(\sqrt{H^3SAT}+ H^4 S A ) O ( H 3 S A T + H 4 S A ) with a linear second-order term in S S S . Optimal strategy for reinforcement learning with delayed observations.
problem Delayed state observation in reinforcement learning.
method Combines augmentation method and upper confidence bound approach.
result Minimax optimal regret bound of i l d e O ( H D max S A K ) ilde{\mathcal{O}}(H \sqrt{D_{\max} SAK}) i l d e O ( H D m a x S A K ) . New algorithm reduces regret in CMDPs without cancellation of errors.
problem Lagrangian approaches in CMDPs struggle with cancellation of errors.
method OptAug-CMDP, based on augmented Lagrangian method.
result Regret of i l d e O ( K ) ilde{O}(\sqrt{K}) i l d e O ( K ) for both objective and constraint violation. ZoomRL learns efficient strategies for large state-action spaces using a metric.
problem Handling large state-action spaces in reinforcement learning.
method ZoomRL leverages continuous bandits to adaptively discretize the joint space.
result Achieves worst-case regret of $ ilde{O}(H^{ rac{5}{2}} K^{ rac{d+1}{d+2}})$ .
New model selects robustly in adversarial reinforcement learning with unknown corruption.
problem Adversarial corruption in reinforcement learning with unknown total corruption amount.
method Model selection approach for finite-horizon tabular and linear MDPs.
result First worst-case optimal bound without knowledge of total corruption.
New framework finds periodic policies in reset-free MDPs with sublinear regret.
problem Reset-free reinforcement learning with unknown dynamics and terminal law constraints.
method Periodic framework, periodic policies, periodic regret.
result First non-asymptotic guarantees for reset-free learning in multi-agent settings.
Paper optimizes reinforcement learning in self-play games with reduced steps.
problem Optimizing reinforcement learning algorithms for self-play in two-player zero-sum games.
method Proposes optimistic Nash Q-learning and Nash V-learning algorithms with improved sample complexity.
result Achieves sample complexity of O ( S A B ) O(SAB) O ( S A B ) for Nash Q-learning and O ( S ( A + B ) ) O(S(A+B)) O ( S ( A + B )) for Nash V-learning, closing the gap with lower bounds. Fine-grained gap-dependent regret bounds for reinforcement learning.
problem Achieving optimal regret bounds for reinforcement learning with suboptimality gaps.
method Developed novel analytical frameworks and refined algorithms for UCB-based and non-UCB-based reinforcement learning.
result Established the first fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms.
Improved exploration in adversarial MDPs via dilated bonuses.
problem Global exploration in adversarial MDPs with local-search policies.
method Dilated bonuses to facilitate global exploration.
result Improved regret bounds in various MDP settings.
Survey of reinforcement learning guarantees with data constraints.
problem Guaranteeing near-optimal policies with limited data in reinforcement learning.
method Coverage-Structure-Objective (CSO) framework to decompose sample complexity results.
result Progress on PAC guarantees for reinforcement learning, covering various models and settings.
Paper improves Bayesian regret bounds for Thompson Sampling in reinforcement learning.
problem Improving Bayesian regret bounds for Thompson Sampling in reinforcement learning.
method Using a discrete set of surrogate environments and posterior consistency analysis, the authors derive an upper bound of order O ( H d l 1 T ) O(H\sqrt{d_{l_1}T}) O ( H d l 1 T ) . result The derived upper bound of O ( H d l 1 T ) O(H\sqrt{d_{l_1}T}) O ( H d l 1 T ) is a significant improvement over previous bounds. The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing it, and thus have limited use in high-stakes applications like healthcare. We address this lack of …
New RL algorithm tackles large state spaces using optimistic function approximation.
problem Challenges in reinforcement learning with large state spaces and modern function approximators.
method Optimistic modification of least-squares value iteration algorithm for kernel functions or overparameterized neural networks.
result Polynomial runtime and sample complexity, independent of the number of states, with i l d e O ( δ F H 2 T ) ilde{\mathcal{O}}(δ_{\mathcal{F}} H^2 \sqrt{T}) i l d e O ( δ F H 2 T ) regret. Algorithm learns NE in imperfect information games with imperfect feedback.
problem Learning Nash equilibrium in imperfect information games with bandit feedback.
method IXOMD algorithm for model-free learning with 1 / T 1/\sqrt{T} 1/ T convergence rate. result IXOMD achieves 1 / T 1/\sqrt{T} 1/ T convergence rate to NE. A method for self-supervised representation learning in partially observable environments.
problem Sparse rewards and stochasticity in partially observable environments.
method World model in latent space for estimating missing information.
result Significant improvement in exploration compared to prior work.
Logarithmic regret achieved in Q-learning with positive gap.
problem Achieving logarithmic cumulative regret in Q-learning with positive sub-optimality gap.
method Optimistic Q-learning with logarithmic regret bound.
result Logarithmic cumulative regret bound proven for optimistic Q-learning.
PyTorch Frame simplifies multi-modal tabular learning with modular data and model handling.
problem Handling complex multi-modal tabular data in deep learning.
method A PyTorch-based framework that provides a data structure, model abstraction, and integration with external models.
result Demonstrated the effectiveness of PyTorch Frame in implementing and applying diverse tabular models to complex multi-modal tabular data.
Study preference-based reinforcement learning in episodic kernel MDPs.
problem Learning from episodic human preferences in reinforcement learning.
method Developed preference-based value estimation and confidence sets for kernel-based MDPs.
result Proved high-probability regret bounds that converge to optimal policy value.
Algorithm improves multi-armed bandit performance by transferring reward samples.
problem Sequential multi-armed bandit problem with changing reward distributions.
method UCB algorithm with reward sample transfer.
result Significant improvement in cumulative regret over standard UCB.
BerlinUCB learns from episodic rewards in nonstationary contexts.
problem Online learning with episodic rewards in nonstationary environments.
method BerlinUCB integrates clustering for self-supervision.
result BerlinUCB outperforms standard contextual bandits in various scenarios.
We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show O ~ ( L ∣ X ∣ ∣ A ∣ T ) \tilde{O}(L|X|\sqrt{|A|T}) O ~ ( L ∣ X ∣ ∣ A ∣ T ) regret bound, where T T T is the number of episodes, X X X is the state space, $A…
MET learns tabular data representations without data augmentations.
problem Lack of effective self-supervised learning methods for tabular data.
method Reconstruction-based approach using masked encoding, with separate representations for each coordinate and adversarial reconstruction loss.
result MET achieves state-of-the-art performance on five diverse tabular datasets, improving up to 9% over current methods.