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.
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.
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.
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.
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 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.
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 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.
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. 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.
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)$ . 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. 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.
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.
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.
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. 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 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.
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.
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.
VO Q Q Q L optimizes RL with sparse rewards using weighted bounds.
problem Sparse rewards and non-linear function approximation in RL.
method VO Q Q Q L combines Q Q Q -learning with weighted bounds for optimal regret. result Achieves asymptotically optimal regret for linear function approximation.
Unified theory for kernel regression generalizes well under realistic assumptions.
problem Analyzing kernel regression under realistic conditions.
method Unified theory providing rigorous bounds for various settings.
result Self-regularization phenomenon in kernel matrices enables good generalization.
This paper explains why distributional reinforcement learning is better than vanilla RL using small-loss bounds.
problem Understanding when and why distributional reinforcement learning (DistRL) is superior to vanilla reinforcement learning (RL).
method The paper uses small-loss bounds to explain the benefits of DistRL, proposing algorithms and proving bounds for different RL settings.
result Distributional reinforcement learning (DistRL) outperforms vanilla RL when optimal costs are small, as shown by small-loss bounds.
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.
Algorithm adapts to shifting domains with minimal label queries.
problem Adaptive learning in online machine learning systems with domain shifts.
method Adaptive algorithm balancing regret and label queries for hidden domains.
result Achieves lower regret compared to uniform and greedy queries.
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 β ) . New algorithm explores reinforcement learning with noisy data.
problem Exploration in reinforcement learning with complex value functions.
method Randomized exploration with i.i.d. scalar noises and optimistic reward sampling.
result Achieves worst-case regret bound of O ~ ( p o l y ( d E H ) T ) \widetilde{O}(\mathrm{poly}(d_EH)\sqrt{T}) O ( poly ( d E H ) T ) . Paper develops efficient algorithms for zero-sum Markov games with general function classes.
problem Challenging settings in zero-sum Markov games with parameterized value functions or models.
method Developed new model-free and model-based algorithms for decoupled and coordinated settings.
result Improved sample complexity and regret bounds for various settings.
New algorithm reduces RL complexity with low switching costs.
problem Exploration-exploitation dilemma in RL with complex models.
method Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation.
result Achieves minimax optimal regret of O ( d H K ) O(d\sqrt{HK}) O ( d H K ) and near-optimal policy switching cost. New RL algorithm reduces regret in finite-horizon episodic tasks.
problem Minimizing regret in model-based reinforcement learning.
method Optimism principle applied to value-targeted regression.
result Regret bound of i l d e O ( d H 3 T ) ilde{\mathcal{O}}(d\sqrt{H^{3}T}) i l d e O ( d H 3 T ) for linear mixtures. New algorithms reduce contextual bandits' regret without knowing reward noise variances.
problem Reducing regret in contextual bandits with unknown reward noise variances.
method Developed new algorithms based on the optimism principle.
result Regret scales as the square root of the sum of measurement variances, not the time horizon.
Parallelized bandit algorithms speed up decision-making.
problem Sequential exploration limits decision-making speed.
method Developed parallel contextual bandit algorithms.
result Regret nearly identical to sequential algorithms.
Explaining the unreasonable effectiveness of deep learning has eluded researchers around the globe. Various authors have described multiple metrics to evaluate the capacity of deep architectures. In this paper, we allude to the radius margin bounds described for a support vector machine (SVM) with hinge loss, apply the…
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.
Algorithm minimizes regret while adhering to unknown safety constraints.
problem Online learning with unknown safety constraints.
method General meta-algorithm leveraging online regression and learning oracles.
result Concrete algorithm with T \sqrt{T} T regret for linear constraints. 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.
Improved regret bounds for contextual bandits considering variance sequences.
problem Establishing lower bounds for contextual bandits with variance-dependent regret.
method Developed variance-dependent lower bounds for linear contextual bandits under two settings: fixed and adaptive variance sequences.
result Lower bounds match upper bounds of SAVE algorithm up to logarithmic factors.
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.
Pessimistic RL algorithm improves offline RL performance.
problem Insufficient dataset coverage in offline RL.
method Proposes a pessimistic variant of value iteration (PEVI) with a penalty function.
result Establishes upper bound on suboptimality for general MDPs, matching lower bound.
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.
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.
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.
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…
Efficient RL algorithm for MDPs with linear Q π Q^π Q π realizability, achieving optimal regret bound.
problem Efficient reinforcement learning under linear Q π Q^π Q π realizability assumption for MDPs with stochastic dynamics. method Frozen Policy Iteration algorithm that uses high-confidence data and freezes policy for well-explored states.
result Achieves optimal regret bound of O ~ ( d 2 H 6 T ) \widetilde{O}(\sqrt{d^2H^6T}) O ( d 2 H 6 T ) for linear (contextual) bandits. Interactive IL algorithm queries noisy expert for feedback, reducing sample size.
problem Imitation learning with noisy expert feedback requires many samples.
method Selective sampling algorithm with online regression oracle.
result Interactive IL algorithm reduces query complexity and improves performance.