Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Optimal Episode Complexity”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cs.LG
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.
Extends Thompson sampling for RL with fewer episodes.
problem Limited episodes in RL settings.
method Batch Bayesian optimization over episodes to learn action bias terms.
result Significantly outperforms standard Thompson sampling.
Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learningcs.LG
Paper addresses offline policy evaluation in RL, achieving near-optimal bounds for various policy classes.
problem Evaluate all policies in a class simultaneously for offline RL.
method Uniform convergence in OPE for various policy classes, achieving optimal episode complexity.
result Achieves optimal episode complexity of O(H^3/d_mε^2) for identifying ε-optimal policies.
New algorithm learns optimal policies with just 1 episode, settling horizon-dependence in RL.
problem Understanding the sample complexity of reinforcement learning with horizon length.
method Developed an algorithm using only episodes to achieve PAC guarantee, leveraging connections between value functions in discounted and finite-horizon MDPs and novel perturbation analysis.
result Achieved the same PAC guarantee with only episodes of environment interactions, completely settling horizon-dependence in RL.
New algorithm reduces reinforcement learning complexity, approaching contextual bandits.
problem Episodic reinforcement learning's difficulty compared to contextual bandits.
method Proposes MVP algorithm with a new Bernstein-type bonus for episodic reinforcement learning.
result Achieves near-optimal regret bound of $O\left(\left(\sqrt{SAK} + S^2A
ight) \poly\log \left(SAHK
ight)
ight)$, improving state-of-the-art results.
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.
Paper bounds PAC RL sample complexity in deterministic MDPs.
problem Identify ε-optimal policy with high probability.
method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.
result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.
The success of popular algorithms for deep reinforcement learning, such as policy-gradients and Q-learning, relies heavily on the availability of an informative reward signal at each timestep of the sequential decision-making process. When rewards are only sparsely available during an episode, or a rewarding feedback i…
New RL algorithm achieves nearly optimal performance for linear MDPs.
problem Optimal reinforcement learning for episodic linear MDPs.
method Weighted linear regression with variance estimator and rare-switching policy.
result Achieves nearly minimax optimal regret .
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.
Algorithm reduces episode count for CMDPs with constraints.
problem Online decision-making with constraints in episodic CMDPs.
method Optimistic planning using linear programming for PAC guarantee.
result Probably approximately correct (PAC) guarantee on episode count.
Improved reinforcement learning for episodes with varying action sets.
problem Reinforcement learning with context-dependent action sets.
method Extends MVP algorithm to handle adversarial and stochastic contexts.
result Established minimax regret bounds of for adversarial contexts.
Recurrent major mood episodes and subsyndromal mood instability cause substantial disability in patients with bipolar disorder. Early identification of mood episodes enabling timely mood stabilisation is an important clinical goal. Recent technological advances allow the prospective reporting of mood in real time enabl…
Reinforcement learning (RL) has traditionally been understood from an episodic perspective; the concept of non-episodic RL, where there is no restart and therefore no reliable recovery, remains elusive. A fundamental question in non-episodic RL is how to measure the performance of a learner and derive algorithms to max…
Optimistic Q-learning reduces sample complexity for systems with known dynamics.
problem Sample efficiency in reinforcement learning with partial dynamics knowledge.
method Optimistic Q-learning algorithm for systems with additive disturbance model.
result Achieves regret under perfect knowledge of dynamics.
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.
Algorithm learns near-optimal policies for reward-mixing MDPs with few latent contexts.
problem Episodic reinforcement learning in reward-mixing Markov decision processes with a few latent contexts.
method Sample-efficient algorithm EM^2 using higher-order method-of-moments approach.
result Provides an ε-optimal policy using O(ε^(-2) * S^d A^d * poly(H, Z)^d) episodes for arbitrary M ≥ 2.
New method learns near-optimal policies with polynomial samples in A and H.
problem Episodic latent MABs with partial observations are challenging.
method Experiment design and method-of-moments approach.
result Polynomial samples in A and H for near-optimal policy learning.
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 regret bound, where is the number of episodes, is the state space, $A…
Study risk-sensitive reinforcement learning with Lipschitz dynamic risk measures, establishing regret bounds.
problem Risk-sensitive reinforcement learning in Markov decision processes.
method Two model-based algorithms for Lipschitz dynamic risk measures, focusing on regret bounds.
result Upper bounds demonstrate optimal dependencies on actions and episodes, reflecting risk sensitivity vs. sample complexity trade-off.
Paper tackles regret bounds and exploration complexity for multi-objective reinforcement learning with picky preferences.
problem Formalizing multi-objective reinforcement learning with adversarial preferences.
method Model-based algorithm with nearly optimal regret bound and preference-free exploration.
result Achieves nearly minimax optimal regret bound and nearly optimal trajectory complexity.
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.
Paper optimizes learning MDPs with adversarial rewards using linear models.
problem Learning MDPs with adversarial rewards and changing reward functions.
method Proposes POWERS, an optimistic policy optimization algorithm.
result Achieves nearly optimal regret bound of .
Proposes PIC and POIC for measuring task difficulty in RL.
problem Lack of metrics to measure task difficulty in RL.
method Introduces policy information capacity (PIC) and policy-optimal information capacity (POIC) as metrics based on mutual information.
result Empirically shows PIC and POIC correlate with task solvability better than alternatives.
New RL method handles large state-action spaces with complex models.
problem Complex models and large state-action spaces in reinforcement learning.
method π-KRVI, an optimistic modification of least-squares value iteration using kernel ridge regression.
result First order-optimal regret guarantees under general settings, improving over state of the art.
Improved regret bound for MNL MDPs with variance-aware approach.
problem Optimal reinforcement learning for MNL MDPs with structured variance.
method Introducing a problem-dependent constant measuring average variance, proposing an algorithm with improved regret bound.
result Minimax optimal regret bound of for structured MDPs.
Paper solves learning imperfect-information games with fewer episodes.
problem Learning imperfect-information extensive-form games from bandit feedback.
method Balanced Online Mirror Descent and Balanced Counterfactual Regret Minimization algorithms.
result Achieves near-optimal sample complexity for finding approximate Nash equilibria.
Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for ex…
New algorithm reduces sample complexity for safe reinforcement learning.
problem Safe reinforcement learning in constrained MDPs with performance and safety constraints.
method Model-based primal-dual algorithm balancing regret and bounded constraint violations.
result Proves near-optimal policies with bounded violations or zero violations in CMDPs.
Most provably-efficient learning algorithms introduce optimism about poorly-understood states and actions to encourage exploration. We study an alternative approach for efficient exploration, posterior sampling for reinforcement learning (PSRL). This algorithm proceeds in repeated episodes of known duration. At the sta…
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 for Nash Q-learning and for Nash V-learning, closing the gap with lower bounds.
We propose a new reinforcement learning algorithm for partially observable Markov decision processes (POMDP) based on spectral decomposition methods. While spectral methods have been previously employed for consistent learning of (passive) latent variable models such as hidden Markov models, POMDPs are more challenging…
We introduce a lifelong language learning setup where a model needs to learn from a stream of text examples without any dataset identifier. We propose an episodic memory model that performs sparse experience replay and local adaptation to mitigate catastrophic forgetting in this setup. Experiments on text classificatio…
Paper proposes DAC-ML, a cognitive architecture that learns quickly from few episodes.
problem Sample inefficiency in AI learning action policies.
method Incorporates hippocampus-inspired sequential memory system into DAC theory of mind.
result DAC-ML rapidly converges to effective action policies maximizing reward.
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.
New RL algorithm reduces sample complexity for optimal learning.
problem Achieving optimal learning with minimal samples in RL.
method Early-settled variance reduction method with Q-learning sequences.
result Near-optimal regret achieved with sample size .
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…
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 per episode.
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.
We introduce a new class of reinforcement learning methods referred to as {\em episodic multi-armed bandits} (eMAB). In eMAB the learner proceeds in {\em episodes}, each composed of several {\em steps}, in which it chooses an action and observes a feedback signal. Moreover, in each step, it can take a special action, c…
This paper studies poisoning attacks in episodic RL and discovers their effectiveness depends on reward bounds.
problem Understanding security threats to RL algorithms through poisoning attacks.
method Examined two types of poisoning attacks: reward and action manipulation, in bounded and unbounded reward settings.
result The effectiveness of poisoning attacks depends on reward bounds, with different attack costs and success rates.
New rule reduces exploration regret to logarithmic, improving bad episode handling.
problem Improving exploration regret in average reward MDPs.
method Replacing Doubling Trick with Vanishing Multiplicative rule in EVI-based algorithms.
result Regret is logarithmic under the new rule, significantly better than linear.
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved sample complexity lower bound.
In an episodic Markov Decision Process (MDP) problem, an online algorithm chooses from a set of actions in a sequence of trials, where is the episode length, in order to maximize the total payoff of the chosen actions. Q-learning, as the most popular model-free reinforcement learning (RL) algorithm, directly pa…
New algorithms reduce dynamic regret in online MDPs with changing losses.
problem Online MDPs with adversarial loss changes and known transitions.
method Dynamic regret measure, novel ensemble algorithms for three models.
result Provably optimal dynamic regret bounds for episodic SSP, improved bounds for predictable environments.
Upside-Down Reinforcement Learning Can Diverge in Stochastic Environments With Episodic Resetsstat.ML
UDRL fails to converge in stochastic environments with episodic resets.
problem UDRL's convergence in stochastic environments with resets is questioned.
method UDRL is a supervised learning approach that does not use value functions.
result UDRL diverges in a simple stochastic environment with resets.
Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescs.LG
Algorithm improves RL model selection for repeated games with utility maximization.
problem Optimal policy learning in repeated games with unknown opponent strategy.
method Proposes MRBEAR for average reward RL, applying to utility maximization in repeated games.
result Regret bound shows linear dependence on number of model classes in average reward RL.