Faster algorithms for solving multichain MDPs under average-reward criterion.
problem Navigating towards the best connected component in multichain MDPs.
method Developed algorithms to better solve the navigational subproblem, achieving faster convergence rates.
result Improved rates of convergence and sharper complexity measures for multichain MDPs.
Optimizes learning policies in average-reward MDPs with improved sample complexity.
problem Learning optimal policies in average-reward MDPs with limited samples.
method Reduces to discounted MDPs and uses improved bounds for variance parameters.
result Establishes minimax optimal sample complexity bound of O(SA(H/ε^2))
Optimizes learning policies in MDPs with weakly communicating structure.
problem Learning optimal policies in weakly communicating MDPs with generative model.
method Span-based approach, reducing to discounted MDPs for analysis.
result First minimax optimal sample complexity bound for weakly communicating MDPs.
A new model-free algorithm achieves near-optimal regret for infinite-horizon MDPs.
problem Model-free reinforcement learning for infinite-horizon average-reward MDPs.
method Exploration Enhanced Q-learning (EE-QL) for weakly communicating MDPs.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bound for general weakly communicating MDPs. Actor-Critic method achieves optimal regret for unichain MDPs.
problem Scalable regret analysis for infinite-horizon average-reward MDPs.
method NAC-B, a Natural Actor-Critic with batching.
result Order-optimal regret of i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) in infinite-horizon average-reward MDPs. Study improves reinforcement learning for stable long-term performance.
problem Distributionally robust average-reward reinforcement learning for stable long-term performance.
method Proposes two algorithms to achieve near-optimal sample complexity.
result Achieves a sample complexity of O ( ∣ S ∣ ∣ A ∣ t m i x 2 ε − 2 ) O(|\mathbf{S}||\mathbf{A}| t_{\mathrm{mix}}^2\varepsilon^{-2}) O ( ∣ S ∣∣ A ∣ t mix 2 ε − 2 ) for estimating optimal policy and robust average reward. UCRL2-VTR achieves nearly optimal regret for learning MDPs with linear function approximation.
problem Learning infinite-horizon average-reward MDPs with linear function approximation.
method UCRL2-VTR algorithm with Bernstein-type bonus.
result Achieves a regret of i l d e O ( d D T ) ilde{O}(d\sqrt{DT}) i l d e O ( d D T ) with matching lower bound. New algorithm reduces reinforcement learning regret to sqrt(T) without strong dynamics assumptions.
problem Infinite-horizon average-reward reinforcement learning with linear MDPs.
method Approximate by discounted-reward MDPs and apply optimistic value iteration.
result Achieves O(sqrt(T)) regret with polynomial complexity.
This work improves Q-learning for average-reward MDPs, reducing sample and communication complexities in federated settings.
problem Improving sample complexity of Q-learning for average-reward MDPs.
method Simple Q-learning algorithm with carefully chosen parameters for both single-agent and federated scenarios.
result Established first federated Q-learning algorithm for average-reward MDPs with provable efficiency in sample and communication complexities.
New algorithm achieves optimal regret in average reward MDPs without prior bias information.
problem Achieving optimal regret in average reward MDPs with computational efficiency and without prior bias information.
method Projective Mitigated Extended Value Iteration (PMEVI) to compute bias-constrained optimal policies efficiently.
result First tractable algorithm with minimax optimal regret of O ~ ( s p ( h ∗ ) S A T ) \widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T}) O ( sp ( h ∗ ) S A T ) . Study non-rectangular robust MDPs for average-reward, finding optimal policies and transient values.
problem Non-rectangular robust Markov decision processes under average-reward criterion.
method Proves history-dependent policies are robust-optimal, introduces transient-value framework, constructs epoch-based policy.
result Existence and properties of robust optimal policies, transient value bounds.
Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-r…
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
New offline RL method handles average-reward MDPs with single-policy coverage.
problem Challenges in offline reinforcement learning due to distribution shift and non-uniform coverage.
method Develops an algorithm based on pessimistic discounted value iteration with quantile clipping.
result First fully single-policy sample complexity bound for average-reward offline RL.
Optimal sample complexity analysis for plug-in approach in average-reward MDPs.
problem Learning optimal policies in average-reward MDPs with a generative model.
method Plug-in approach that constructs a model estimate and computes an optimal policy.
result Optimal sample complexities for the plug-in approach without prior knowledge of problem parameters.
New algorithm reduces sample complexity for constrained MDPs.
problem Learning policies in constrained average-reward MDPs.
method Model-based algorithm for relaxed and strict feasibility settings.
result Achieves minimax-optimal bounds for constrained MDPs.
Improved exploration in factored average-reward MDPs reduces regret.
problem Minimizing regret in unknown Factored Markov Decision Processes (FMDPs).
method DBN-UCRL strategy, inspired by UCRL2, uses Bernstein-type confidence sets for individual elements of the transition function.
result Achieves a regret bound with a leading term strictly improving over existing bounds.
New algorithm learns optimal policy for average reward MDPs with sample complexity matching lower bound.
problem Learning optimal policy for average reward in uniformly ergodic MDPs.
method Developed an estimator with sample complexity of O(|S||A|t_{mix}ε^{-2}).
result First algorithm to match lower bound of existing literature.
Develops first-order methods for average-reward MDPs with strong guarantees.
problem Lack of strong theoretical guarantees for first-order methods in AMDPs.
method Average-reward stochastic policy mirror descent (SPMD) and variance-reduced temporal difference (VRTD) methods.
result Establishes sample complexity results for solving AMDPs.
New algorithms for learning MDPs with linear approximations in infinite-horizon settings.
problem Learning infinite-horizon average-reward MDPs with linear function approximation.
method Optimism principle, adversarial linear bandits, Natural Policy Gradient.
result Efficient algorithms with optimal or near-optimal regret bounds.
A new parallel algorithm for learning optimal policies in MDPs with low communication costs.
problem Learning optimal policies for infinite-horizon MDPs.
method Primal-Dual Stochastic Mirror Descent for convex programming problems with inexact constraints.
result First parallel algorithm for average-reward MDPs with generative model and low communication costs.
New algorithm reduces regret in infinite MDPs with optimal variance-dependent bounds.
problem Infinite horizon MDPs lack optimal algorithms with low regret.
method Developed a UCB-style algorithm for average-reward and γ-regret.
result Achieved optimal variance-dependent regret bounds for both objectives.
New algorithm for average reward learning with bounded hitting time assumption.
problem Minimizing regret in average reward reinforcement learning with bounded hitting time.
method Optimistic Q-learning with a novel L ‾ \overline{L} L operator for bounded hitting time. result Regret bound of i l d e O ( H 5 S A T ) ilde{O}(H^5 S\sqrt{AT}) i l d e O ( H 5 S A T ) for average reward learning. We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward structure. We show that this parameter replaces diameter in the upper bound on the optimal value span of a…
Paper proposes new γ γ γ -regret measure for non-episodic RL.
problem Measuring performance in non-episodic RL environments.
method Introduces γ γ γ -regret as a new performance measure and derives bounds. result Closed the gap between lower and upper bounds for γ γ γ -regret. Unified framework for solving MDPs with stochastic mirror descent.
problem Approximately solving infinite-horizon Markov decision processes (MDPs).
method Primal-dual stochastic mirror descent for MDPs with a unified framework.
result Computes ε-optimal policies with expected samples for both average-reward and discounted MDPs.
New method reduces sample complexity for robust reinforcement learning.
problem Finite sample analysis in robust reinforcement learning.
method Stochastic approximation framework with controlled bias, using MLMC techniques and geometric truncation.
result Order-optimal sample complexity of i l d e O ( ε − 2 ) ilde{\mathcal{O}}(ε^{-2}) i l d e O ( ε − 2 ) for robust policy evaluation. 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 β ) . We address reinforcement learning problems with finite state and action spaces where the underlying MDP has some known structure that could be potentially exploited to minimize the exploration rates of suboptimal (state, action) pairs. For any arbitrary structure, we derive problem-specific regret lower bounds satisfie…
New algorithms find optimal policies without knowing MDP span.
problem Finding optimal policies in MDPs without knowing span.
method Horizon calibration and span penalization techniques.
result First algorithms achieving optimal span-based complexity without prior knowledge.
While learning in an unknown Markov Decision Process (MDP), an agent should trade off exploration to discover new information about the MDP, and exploitation of the current knowledge to maximize the reward. Although the agent will eventually learn a good or optimal policy, there is no guarantee on the quality of the in…
The problem of reinforcement learning in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion is considered, when the learner interacts with the system in a single stream of observations, starting from an initial state without any reset. We revisit the minimax lower bound for that pr…
New algorithms improve robust reinforcement learning under uncertainty.
problem Robust reinforcement learning in MDPs with contamination.
method Non-asymptotic convergence analysis of Q Q Q -learning and actor-critic methods. result Efficient algorithms learn robust policies with minimal samples.
Model-free reinforcement learning algorithms combined with value function approximation have recently achieved impressive performance in a variety of application domains. However, the theoretical understanding of such algorithms is limited, and existing results are largely focused on episodic or discounted Markov decis…
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.
The paper tackles robust policy learning in MDPs using statistical methods.
problem Offline data-driven sequential decision making in MDPs.
method Evaluates policies using average rewards centered at policy-induced stationary distributions. Developed a statistically efficient method for estimating robust optimal policies.
result Established a rate-optimal regret bound up to a logarithmic factor.
New RL algorithms improve average-reward performance.
problem Improving RL algorithms for average-reward criteria.
method Developed novel algorithms addressing average-reward criterion directly.
result ATRPO significantly outperforms TRPO in challenging MuJuCo environments.
To overcome the curse of dimensionality and curse of modeling in Dynamic Programming (DP) methods for solving classical Markov Decision Process (MDP) problems, Reinforcement Learning (RL) algorithms are popular. In this paper, we consider an infinite-horizon average reward MDP problem and prove the optimality of the th…
We propose a general framework for entropy-regularized average-reward reinforcement learning in Markov decision processes (MDPs). Our approach is based on extending the linear-programming formulation of policy optimization in MDPs to accommodate convex regularization functions. Our key result is showing that using the …
New TD method stabilizes average-reward learning.
problem Stability issues in average-reward TD learning.
method Implicit fixed point update for average-reward TD( λ λ λ ). result Improved numerical stability and broader step-size range.
AIF reformulated as convex MDP for adaptive behavior.
problem Adaptive behavior and policy optimization.
method Formulating AIF as convex MDP, deriving mirror descent algorithm.
result EFE minimization in AIF is equivalent to reward maximization in latent MDP, with epistemic component.
New algorithms learn MDPs with better regret bounds using generative sampling.
problem Learning MDPs with optimal policies under uncertainty.
method Hybrid exploration-generative RL model, classical and quantum algorithms.
result Quantum algorithms achieve poly log T \operatorname{poly}\log{T} poly log T regret for infinite-horizon MDPs. The paper tackles batch policy learning in Markov Decision Processes, focusing on average reward maximization.
problem Maximizing long-term average reward in Markov Decision Processes with batch learning.
method Doubly robust estimator for average reward, optimization algorithm for optimal policy, finite-sample regret guarantee.
result The proposed method achieves semiparametric efficiency and provides a finite-sample regret guarantee.
Hypothesis testing is an important problem with applications in target localization, clinical trials etc. Many active hypothesis testing strategies operate in two phases: an exploration phase and a verification phase. In the exploration phase, selection of experiments is such that a moderate level of confidence on the …
Improved stochastic Halpern iteration for fixed-point approximation in normed spaces.
problem Approximating fixed-points of nonexpansive and contractive operators in normed finite-dimensional spaces.
method Stochastic Halpern iteration with minibatch, analyzing oracle complexity.
result Improved oracle complexity for nonexpansive operators, with a lower bound of Ω ( ε − 3 ) Ω(\varepsilon^{-3}) Ω ( ε − 3 ) . In many sequential decision-making problems we may want to manage risk by minimizing some measure of variability in rewards in addition to maximizing a standard criterion. Variance related risk measures are among the most common risk-sensitive criteria in finance and operations research. However, optimizing many such c…
New method stabilizes saddle-point optimization with unbounded gradients.
problem Stochastic saddle-point optimization faces instability due to large gradients.
method Proposes a regularization technique to stabilize iterates.
result Yields meaningful performance guarantees even with unbounded gradients.
Paper proposes a model-free algorithm for CMDPs with long-term constraints, achieving optimal regret bounds.
problem Optimizing systems with long-term constraints where transition probabilities are unknown.
method Combines concepts from constrained optimization and Q-learning to propose an algorithm.
result Achieves optimal regret bounds for reward and constraint violation.