Noisy expert imitation learning requires exponential samples for offline methods but polynomial for a variant of on-policy distillation under a noise condition.
hub
Limitations
16 Pith papers cite this work. Polarity classification is still indexing.
16
Pith papers citing it
hub tools
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Algorithms and matching lower bounds for s-sparse contextual bandits yield Õ((s/ε² + |A|/ε) log |Π|/δ) samples to output an ε-optimal policy.
Joint KL yields horizon-free approximation but an information-theoretic lower bound of order Omega(H) for estimation error in autoregressive learning, with matching computationally efficient upper bounds.
The authors derive a finite-sample adaptive-data performance bound for FQI by chaining measure-theoretic probability with Bellman contractions and prove the first cumulative pathwise online regret guarantee in continuous spaces using sequential Rademacher complexity.
OPT-AIL provides the first provably efficient adversarial imitation learning algorithms under general function approximation, achieving polynomial expert sample and interaction complexity.
Derives explicit minimax quantile lower bounds for Gaussian mean estimation and K-armed bandits under interactive decision making and MI privacy, with log(1/δ)/n and √(KT log(1/δ)) scalings.
Establishes a variance-aware pointwise majorizing-measure theorem for Gaussian fields, records Bayesian algorithmic lower bounds, and constructs a separation example among classical, algorithmic, and pointwise quantities.
An explicitly exploratory iterative NLHF method achieves O(sqrt(T)) regret for Nash equilibria under general preference models, removing the exponential KL dependence that plagues standard iterative approaches.
F is learnable in adversarial noisy bandits iff the generalized maximin volume on co(F) is positive at every scale, equivalently for oblivious and adaptive adversaries.
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
Offline-to-online value adaptation in RL has a minimax lower bound matching pure online learning in hard cases, yet O2O-LSVI improves sample complexity under a novel structural condition on pretrained Q-functions.
Differential privacy in policy optimization adds sample complexity costs that often appear as lower-order terms rather than dominating the bounds.
Offline KL-regularized MABs require sample complexity scaling as O(η S A C^π*/ε) for large regularization and Ω(S A C^π*/ε²) for small regularization, with matching lower bounds across the full range.
A novel log-barrier and log-determinant regularized algorithm achieves Õ(√T) regret in tabular MDPs with O(H log log T) oracle calls independent of |S|×|A| and extends to linear MDPs with infinite states for sublinear regret.
The paper advertises a Bellman-style information-complexity framework and a negative resolution of GP-UCB minimax optimality, but the negative resolution is absent from the body.
citing papers explorer
-
Behavior Cloning is Not All You Need: The Optimality of On-Policy Distillation for Noisy Expert Feedback
Noisy expert imitation learning requires exponential samples for offline methods but polynomial for a variant of on-policy distillation under a noise condition.
-
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Algorithms and matching lower bounds for s-sparse contextual bandits yield Õ((s/ε² + |A|/ε) log |Π|/δ) samples to output an ε-optimal policy.
-
Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds
Joint KL yields horizon-free approximation but an information-theoretic lower bound of order Omega(H) for estimation error in autoregressive learning, with matching computationally efficient upper bounds.
-
A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration
The authors derive a finite-sample adaptive-data performance bound for FQI by chaining measure-theoretic probability with Bellman contractions and prove the first cumulative pathwise online regret guarantee in continuous spaces using sequential Rademacher complexity.
-
Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms
OPT-AIL provides the first provably efficient adversarial imitation learning algorithms under general function approximation, achieving polynomial expert sample and interaction complexity.
-
Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy
Derives explicit minimax quantile lower bounds for Gaussian mean estimation and K-armed bandits under interactive decision making and MI privacy, with log(1/δ)/n and √(KT log(1/δ)) scalings.
-
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Establishes a variance-aware pointwise majorizing-measure theorem for Gaussian fields, records Bayesian algorithmic lower bounds, and constructs a separation example among classical, algorithmic, and pointwise quantities.
-
Efficient Exploration for Iterative Nash Preference Optimization
An explicitly exploratory iterative NLHF method achieves O(sqrt(T)) regret for Nash equilibria under general preference models, removing the exponential KL dependence that plagues standard iterative approaches.
-
A Complete Characterization of Learnability for Adversarial Noisy Bandits
F is learnable in adversarial noisy bandits iff the generalized maximin volume on co(F) is positive at every scale, equivalently for oblivious and adaptive adversaries.
-
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
-
Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation
Offline-to-online value adaptation in RL has a minimax lower bound matching pure online learning in hard cases, yet O2O-LSVI improves sample complexity under a novel structural condition on pretrained Q-functions.
-
On the Sample Complexity of Differentially Private Policy Optimization
Differential privacy in policy optimization adds sample complexity costs that often appear as lower-order terms rather than dominating the bounds.
-
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
Offline KL-regularized MABs require sample complexity scaling as O(η S A C^π*/ε) for large regularization and Ω(S A C^π*/ε²) for small regularization, with matching lower bounds across the full range.
-
Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
A novel log-barrier and log-determinant regularized algorithm achieves Õ(√T) regret in tabular MDPs with O(H log log T) oracle calls independent of |S|×|A| and extends to linear MDPs with infinite states for sublinear regret.
-
Bellman-sufficient Information Complexity
The paper advertises a Bellman-style information-complexity framework and a negative resolution of GP-UCB minimax optimality, but the negative resolution is absent from the body.
- Minimax-Optimal Policy Regret in Partially Observable Markov Games