New BE dimension measure reveals rich RL problems with sample-efficient algorithms.
problem Finding sample-efficient algorithms for complex RL problems.
method Introducing Bellman Eluder (BE) dimension and designing GOLF and OLIVE algorithms.
result GOLF and OLIVE algorithms learn near-optimal policies for low BE dimension problems with polynomial samples.
New insights on eluder dimension for function approximation in machine learning.
problem Complexity measure for online bandits and reinforcement learning with function approximation.
method Study the relationship between eluder dimension and generalized rank for different activation functions.
result Eluder dimension can be exponentially smaller or larger than generalized rank depending on the activation function.
New algorithm tackles non-stationary reinforcement learning with general function approximation.
problem Understanding non-stationary MDPs with function approximation.
method Dynamic Bellman Eluder (DBE) dimension for complexity, sliding window mechanism, confidence set design.
result Upper bound on dynamic regret for proposed SW-OPEA algorithm.
Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
problem Complexity measures in bandit and reinforcement learning.
method Equivalence of eluder dimension and information gain for reproducing kernel Hilbert spaces.
result Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
Paper analyzes distributional reinforcement learning with value function approximation, introducing Bellman unbiasedness and a new algorithm.
problem Improving reinforcement learning by capturing environmental stochasticity and addressing infinite dimensionality.
method Introduces Bellman unbiasedness and proposes SF-LSVI algorithm for provably efficient distributional reinforcement learning.
result Achieves a tight regret bound of O(d_E H^3/2 √K) for distributional reinforcement learning.
Develops a new model for RLHF accounting for partially observed states and intermediate feedback.
problem Lack of models for partially observed states and intermediate feedback in RLHF.
method PORRL model with cardinal and dueling feedback methods.
result Demonstrates improved learning and alignment with new model-based and model-free methods.
New algorithms achieve uniform-PAC guarantees for RL with bounded eluder dimension.
problem Achieving strong performance guarantees in reinforcement learning.
method Proposes algorithms for nonlinear bandits and model-based episodic RL with a bounded eluder dimension.
result Achieves uniform-PAC sample complexity that matches state-of-the-art regret bounds or sample complexity guarantees.
New insights show coverage conditions are crucial for efficient online reinforcement learning.
problem The role of coverage conditions in determining sample complexity of offline reinforcement learning.
method Established a connection between coverage conditions and sample efficiency in online reinforcement learning.
result Coverability, a structural property of MDPs, enables sample-efficient exploration in online reinforcement learning.
Improved Thompson Sampling for smoother functions with noise.
problem Applying Thompson Sampling to continuum armed bandits with weak conditions.
method Analysis of eluder dimension for function classes with smooth derivatives.
result New bounds on eluder dimension for classes of functions with Lipschitz derivatives.
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.
New RL method reduces sample complexity for large policy spaces.
problem Large-scale RL with unknown optimal policies and state/action spaces.
method Introduces eluder dimension for policy space, proving near-optimal sample complexity.
result Near-optimal sample complexity upper bound that depends linearly on eluder dimension.
We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as …
Paper develops efficient RL algorithm for general value function approximation.
problem Lack of theory for RL with general value function approximation.
method Provable efficient RL algorithm using bounded eluder dimension.
result Achieves a regret bound of O ~ ( p o l y ( d H ) T ) \widetilde{O}(\mathrm{poly}(dH)\sqrt{T}) O ( poly ( d H ) T ) . New algorithm LOOP learns infinite-horizon AMDPs efficiently with function approximation.
problem Learning optimal policies in infinite-horizon AMDPs with function approximation.
method LOOP combines model-based and value-based methods with novel confidence sets and policy updating.
result LOOP achieves sublinear regret bound of i l d e O ( p o l y ( d , s p ( V ∗ ) ) T β ) ilde{\mathcal{O}}(\mathrm{poly}(d, \mathrm{sp}(V^*)) \sqrt{Tβ} ) i l d e O ( poly ( d , sp ( V ∗ )) T β ) . A new framework reduces RL sample complexity for complex MDPs.
problem Handling large state and action spaces in reinforcement learning.
method Unified model-based and model-free RL framework with ABC class, novel estimation function, and functional eluder dimension.
result OPERA algorithm achieves sample-efficient regret bounds for various MDP models.
Unified framework for efficient RL in MDP, POMDP, and PSR.
problem Sample efficient reinforcement learning under various decision-making frameworks.
method Proposed GEC complexity measure and a posterior sampling algorithm.
result Sample efficient learning achieved with sublinear regret bound in terms of GEC.
Study experiment planning with function approximation in contextual bandit problems.
problem Designing effective data collection strategies in settings with limited rewards.
method Proposes two experiment planning strategies compatible with function approximation.
result Eluder planning and sampling procedure achieves optimality guarantees.
This work improves sample efficiency in neural function approximation for reinforcement learning.
problem Improving sample efficiency in reinforcement learning with neural function approximation.
method Study of function approximation with two-layer neural networks (ReLU and polynomial activations) under generative and realizability models.
result Significant improvement in sample complexity compared to linear methods.
New algorithm finds Nash equilibrium in multi-agent games.
problem Extending RL theory to multi-agent settings with large state spaces.
method Proposes an algorithm using an exploiter to find Nash equilibrium policies.
result Proves finding Nash equilibrium is possible with polynomial samples.
Paper proposes an algorithm for lifelong learning with shared structure.
problem Lifelong learning with shared structure in an online setting.
method Proposes a simple algorithm using multi-task empirical risk minimization.
result Establishes a sample complexity bound based on task-eluder dimension.
Du, Kakade, Wang, and Yang recently established intriguing lower bounds on sample complexity, which suggest that reinforcement learning with a misspecified representation is intractable. Another line of work, which centers around a statistic called the eluder dimension, establishes tractability of problems similar to t…
Study optimal policy regret in partially observable Markov games with adaptive opponents.
problem Optimal sequential decision-making in partially observable environments against strategic, adaptive opponents.
method An epoch-based optimistic maximum-likelihood algorithm that selects one policy per epoch using confidence sets built cumulatively from past data.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) policy regret for fixed problem parameters, with explicit dependence on horizon, adversary memory, confidence radius, and aggregate Eluder dimension. Framework reduces contextual bandit learning to offline regression with near-optimal regret.
problem Efficient learning with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that minimizes regret with near-optimal oracle calls.
result Near-optimal regret for contextual bandits with large action spaces and O ( l o g ( T ) ) O(log(T)) O ( l o g ( T )) offline oracle calls. ENIAC method optimizes and explores complex RL problems with non-linear policies.
problem Theoretical understanding of non-linear policies in RL with strategic exploration.
method ENIAC, an actor-critic method for non-linear function approximation.
result ENIAC finds near-optimal policies in polynomial exploration rounds under bounded eluder dimension.
OE2D framework reduces contextual bandits to offline regression for near-optimal regret.
problem Efficiently learning contextual bandits with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that reduces contextual bandits to offline regression.
result Near-optimal regret for contextual bandits with large action spaces and O ( log T ) O(\log T) O ( log T ) calls to an offline regression oracle. By using an explicit Bellman function, we prove a bilinear embedding theorem for the Laplacian associated with a weighted Riemannian manifold ( M , μ φ ) (M,μ_φ) ( M , μ φ ) having the Bakry-Emery curvature bounded from below. The embedding, acting on the cartesian product of L p ( M , μ φ ) L^p(M,μ_φ) L p ( M , μ φ ) and L q ( T ∗ M , μ φ ) L^q(T^*M,μ_φ) L q ( T ∗ M , μ φ ) , 1 / p + 1 / q = 1 1/p+1/q=1 1/ p + 1/ q = 1 , involves estimates…
Study contextual bandits with stage-wise constraints, proving regret bounds and extending results.
problem Contextual bandits with stage-wise constraints in high probability and expectation settings.
method Upper-confidence bound algorithms for linear and non-linear reward/cost functions, extending to multiple constraints.
result Regret bounds for various settings, including non-linear reward/cost functions.
RL in MFGs is as hard as solving many single-agent RL problems.
problem Learning Nash Equilibrium in Mean-Field Games (MFGs).
method Introduce P-MBED to measure model complexity, develop a novel exploration strategy, and establish polynomial sample complexity results.
result Learning Nash Equilibrium in MFGs is no more statistically challenging than solving a logarithmic number of single-agent RL problems.
Unified framework for constrained online decision-making.
problem Sequential decisions under stage-wise feasibility constraints.
method Upper counterfactual confidence bounds and generalized eluder dimension.
result Principled foundation for constrained sequential decision-making.
Deep neural nets approximate high-dimensional HJB equations efficiently.
problem Approximating solutions to high-dimensional HJB equations.
method Deep neural networks for approximating solutions.
result Deep neural networks can approximate solutions without the curse of dimensionality.
New findings on representation learning beyond linear functions.
problem Achieving diversity in representation learning beyond linear prediction functions.
method Analysis of eluder dimension and empirical risks.
result Diversity holds even with nonlinear prediction functions and multiple layers in neural networks.
New algorithm finds optimal policy with polynomial trajectories in deterministic systems.
problem Finding optimal policy in deterministic systems with function approximation.
method Novel recursion-based algorithm with tight bounds on error and sample complexity.
result Optimal policy found using O ( dim E ) O(\dim_E) O ( dim E ) trajectories with $δ= O\left(ρ/\sqrt{\dim_E}
ight)$ . New actor-critic algorithm achieves optimal sample efficiency in RL.
problem Achieving ε ε ε -optimal policies with minimal samples in RL. method Integrates optimism, off-policy critic estimation, and rare-switching policy resets.
result Sample complexity of O ( d H 5 log ∣ A ∣ / ε 2 + d H 4 log ∣ F ∣ / ε 2 ) O(dH^5 \log|\mathcal{A}|/ε^2 + d H^4 \log|\mathcal{F}|/ ε^2) O ( d H 5 log ∣ A ∣/ ε 2 + d H 4 log ∣ F ∣/ ε 2 ) trajectories. Deep nets solve MDPs without high dimensions.
problem Solving Bellman equations for MDPs in high dimensions.
method Deep neural networks with ReLU activation approximating payoff and transition functions.
result Deep nets can approximate Q Q Q -functions in polynomially bounded parameters. Improved machine learning for reservoir optimization problems.
problem Optimizing control in high-dimensional storage problems.
method Modified dynamic programming algorithm with neural networks for Bellman values and conditional cuts.
result Neural networks outperform classical feedforward networks in estimating Bellman values.
We address the problem of automatic generation of features for value function approximation. Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algor…
The paper tackles causal bandits with unknown SCMs and soft interventions, providing upper and lower bounds on regret.
problem Optimizing interventions in a causal system with unknown SCMs and soft interventions.
method Assumes unknown SCMs from a general class, allows infinite interventions, and provides upper and lower bounds on regret.
result General upper and lower bounds on cumulative achievable regret for various SCMs.
New algorithms reduce complexity for learning in MDPs with entropy regularization.
problem Efficient learning for MDPs with large or continuous state and action spaces.
method Multilevel Monte Carlo (MLMC) algorithms integrating fixed-point iteration and stochastic approximation of the Bellman operator.
result MLMC with unbiased approximation of the Bellman operator achieves polynomial sample complexity.
Decomposes ultrametric spaces into scaled simplices.
problem Understanding the structure of ultrametric spaces.
method Introducing metric resolutions and coarse disjoint union.
result Constructs universal spaces for asymptotic dimension 0.
The Bellman error is a poor proxy for value function accuracy, even with all state-action pairs.
problem The Bellman error is a poor proxy for the accuracy of the value function.
method Study of the Bellman equation as a surrogate objective for value prediction accuracy.
result The magnitude of the Bellman error is only weakly related to the distance to the true value function, even with all state-action pairs.
ARL-GEN adapts to the smallest model class in nested families for RL with improved regret.
problem Model selection for Reinforcement Learning with nested model families.
method Adaptive Reinforcement Learning (ARL-GEN) with value targeted regression and model selection module.
result ARL-GEN achieves a matching regret to an oracle with knowledge of the true model class.
New method stabilizes FQE by reweighting Bellman targets.
problem Stability guarantees for FQE often rely on Bellman completeness, which can fail with function approximation.
method Proposes stationary-weighted FQE, reweighting Bellman targets by stationary target-to-behavior density ratio.
result Proves finite-sample linear convergence to stationary projected Bellman fixed point without Bellman completeness.
A new method calibrates value predictions in offline RL to improve reliability.
problem Difficulty in long-horizon value prediction in offline reinforcement learning.
method Bellman calibration, a weak reliability criterion, and Iterated Bellman Calibration.
result Finite-sample guarantees show that Bellman calibration error is controlled at nonparametric rates.
We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies wit…
Improved risk-sensitive RL with exponential Bellman equation and better regret bounds.
problem Exponential gap between upper and lower bounds in risk-sensitive RL.
method Identified and addressed deficiencies in existing algorithms and analysis; developed novel analysis and exploration mechanism.
result Improved regret upper bounds over existing ones.
New Bellman error estimator improves offline model selection performance.
problem Selecting the best policy from logged data using mean squared Bellman error.
method Developed a more accurate estimator of MSBE and analyzed conditions for successful OMS.
result New estimator achieves impressive offline model selection performance on diverse tasks.
The paper explores solutions to the distributional Bellman equation in reinforcement learning.
problem Distributional reinforcement learning considers complete return distributions, not just expected returns.
method Study existence and uniqueness of solutions to general distributional Bellman equations, linking them to multivariate affine equations.
result Any solution to a distributional Bellman equation can be derived from a multivariate affine distributional equation.
Contextual bandits study how reward variance affects regret bounds.
problem Investigating how small reward variance impacts regret bounds in contextual bandits.
method Analyzing two types of adversaries and function approximation complexities.
result Regret bounds are influenced by the eluder dimension and reward variance.