New method improves policies by combining Markov and non-Markov strategies.
problem Improving policies in reinforcement learning.
method Geometric Policy Composition (GPI) using a geometric horizon model (GHM).
result GPI can improve non-Markov policies by composing GHMs of base Markov policies.
Study nonparametric estimator for Markov chain transition matrices in offline setting.
problem Estimating transition matrices of finite controlled Markov chains from logged data.
method Developed sample complexity bounds and conditions for minimaxity.
result Achieving certain statistical risk requires balancing mixing properties and sample size.
Develops CLTs for Markov chain transition probabilities and policies.
problem Estimating transition probabilities and policies in controlled Markov chains.
method Non-parametric estimator for transition matrices; CLTs for value, Q-, and advantage functions; goodness-of-fit tests.
result Asymptotic normality of estimators under specific logging policies.
New algorithm finds near-optimal policies efficiently in zero-sum games.
problem Lack of provable efficiency guarantees for policy optimization in zero-sum games.
method Policy optimization algorithm with function approximation.
result Proves efficient convergence to near-optimal policies with polynomial samples and iterations.
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.
Policy gradient algorithm with variable learning rates achieves near-optimal performance in multi-arm bandit problems.
problem Optimizing a policy gradient algorithm for multi-arm bandit problems with variable learning rates.
method Applied Foster-Lyapunov techniques to analyze a Markov chain formed by the state of the algorithm.
result The policy gradient algorithm converges to the optimal arm with logarithmic or poly-logarithmic regret.
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.
This paper investigates methods for estimating the optimal stochastic control policy for a Markov Decision Process with unknown transition dynamics and an unknown reward function. This form of model-free reinforcement learning comprises many real world systems such as playing video games, simulated control tasks, and r…
We consider the problem of learning a policy for a Markov decision process consistent with data captured on the state-actions pairs followed by the policy. We assume that the policy belongs to a class of parameterized policies which are defined using features associated with the state-action pairs. The features are kno…
This paper optimizes MDP policies for efficient state aggregation.
problem Optimizing policies in aggregated Markov chains while preserving optimal performance.
method Homomorphic mappings to establish optimal policy equivalence and derive performance bounds.
result Developed HPG and EBHPG methods for efficient aggregation and policy optimization.
Study on learning strategies in adaptive Markov games with policy regret as metric.
problem Learning in dynamic Markov games with adaptive opponents is challenging.
method Introduced policy regret as a new learning metric and developed algorithms for consistent adaptive adversaries.
result Achieved T \sqrt{T} T policy regret against certain adaptive adversaries. In reinforcement learning (RL) , one of the key components is policy evaluation, which aims to estimate the value function (i.e., expected long-term accumulated reward) of a policy. With a good policy evaluation method, the RL algorithms will estimate the value function more accurately and find a better policy. When th…
We consider the restless Markov bandit problem, in which the state of each arm evolves according to a Markov process independently of the learner's actions. We suggest an algorithm that after T T T steps achieves O ~ ( T ) \tilde{O}(\sqrt{T}) O ~ ( T ) regret with respect to the best policy that knows the distributions of all arms. No ass…
A new algorithm trains experts to safely guide agents in partially observed environments.
problem Existing imitation learning methods for POMDPs can lead to sub-optimal or unsafe policies.
method Derive an objective to encourage the expert to maximize the agent's reward, then use it to train both expert and agent.
result The algorithm produces an expert policy that the agent can safely imitate, outperforming fixed expert policies.
Proposes a Riemannian optimization for policy improvement in MDPs.
problem Optimizing policy functions in Markov decision processes (MDPs).
method Riemannian proximal optimization algorithm with Gaussian mixture model (GMM).
result Guaranteed convergence and efficacy demonstrated in preliminary experiments.
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. Paper tests Markov assumption in sequential decision making.
problem Testing the Markov assumption in sequential decision making.
method Forward-Backward Learning procedure to test MA without assuming parametric forms.
result The proposed test plays a crucial role in identifying optimal policies in complex decision processes.
Study shows TD(0) with linear approx. converges for reversible Markov chains.
problem TD(0) divergence with off-policy and function approximation.
method Analyzes standard TD(0) with reversible Markov chains, adapting stochastic approximation framework.
result Establishes convergence with probability one for projected Bellman error = 0.
This work extends ME-RL using diffusion models to sample optimal policies.
problem Sampling from the optimal policy trajectory distribution in ME-RL.
method Introducing Diffusion-Augmented Markov Decision Processes (DA-MDPs) to minimize reverse KL divergence.
result DA-MDPs enable seamless integration into various ME-RL methods and outperform baselines.
VPP learns joint policies for multi-agent RL through interactions.
problem Learning effective joint policies for multi-agent reinforcement learning.
method VPP integrates variational inference into policy layers for efficient sampling and differentiability.
result VPP outperforms previous methods on large-scale multi-agent tasks.
Algorithm finds safe zones in policy Markov Decision Processes to limit trajectory escape.
problem Finding safe zones in policy Markov Decision Processes to limit trajectory escape.
method Bi-criteria approximation learning algorithm with polynomial sample complexity.
result Achieves almost 2 approximation for both escape probability and safe zone size.
Bayesian regularization improves policy performance in noisy MDPs.
problem Suboptimal policies from estimated model parameters.
method Bayesian regularization of MDP objective function with prior information.
result Regularized policies show better robustness against model noise.
PPO algorithm converges to global optimality in multi-agent reinforcement learning.
problem Designing statistical guarantees for policy optimization methods in multi-agent reinforcement learning.
method Leveraging a multi-agent performance difference lemma, a localized action value function is used as a descent direction for each local policy, leading to a multi-agent PPO algorithm.
result The multi-agent PPO algorithm converges to the globally optimal policy at a sublinear rate under standard regularity conditions.
Minimal assumptions analysis of Q-learning with time-varying policies.
problem Finite-time analysis of Q-learning with time-varying policies for discounted MDPs.
method Minimal assumptions, Poisson equation decomposition, sensitivity analysis.
result Established convergence rate and sample complexity for Q-learning.
A new estimator for state values in reinforcement learning reduces complexity and improves convergence.
problem Estimating state values in reinforcement learning with Markov reward processes.
method Loop estimator exploiting regenerative structure of Markov reward processes.
result Instance-dependent convergence rate of O ~ ( τ s / T ) \widetilde{O}\left(\sqrt{τ_s/T}\right) O ( τ s / T ) for estimating state values. DORIS algorithm achieves no-regret learning in Markov games with adversarial opponents.
problem Decentralized policy learning in Markov games with nonstationary opponents.
method DORIS algorithm using optimistic hyperpolicy mirror descent.
result Achieves K \sqrt{K} K -regret in general function approximation. Paper tackles efficient policy gradient estimation from off-policy data.
problem Estimating policy gradients from off-policy data is challenging and inefficient.
method Derives asymptotic lower bounds, proposes a meta-algorithm with 3-way robustness, and establishes convergence guarantees.
result Meta-algorithm achieves the lower bound on mean-squared error without parametric assumptions.
Algorithm selects optimal experiments in Markov chains to learn unknown quantities.
problem Designing efficient experiments in Markov chains to learn about unknown quantities.
method Proposes extsc{markov-design} algorithm for sequential policy selection.
result Algorithm provably converges to optimal measurement allocation.
New methods improve temporal difference learning for policy evaluation in Markov decision processes.
problem Improving temporal difference learning for policy evaluation in Markov decision processes.
method Introduced variance-reduced forms of stochastic approximation to achieve non-asymptotic, instance-dependent optimality.
result Temporal difference learning is strictly suboptimal, but variance-reduced forms achieve optimality up to logarithmic factors.
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 O ( S 2 A H ) O(S^2AH) O ( S 2 A H ) per episode. Algorithm minimizes regret and converges to equilibria in Markov games.
problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.
method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.
result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.
Proposes CoPO, a new policy optimization method for competitive games.
problem Designing efficient optimization methods for competitive Markov decision processes.
method Competitive policy optimization (CoPO) approach that exploits game-theoretic nature of competitive games.
result Stable optimization, convergence to sophisticated strategies, and higher scores compared to baseline methods.
This work tackles learning Markov games with adversarial opponents and achieves both average reward and exploitation.
problem Achieving both average reward and exploiting adaptive opponents in Markov games.
method Develops efficient algorithms and proves hardness results for learning Markov games with adversarial opponents.
result Achieves K \sqrt{K} K -regret bounds for certain conditions on opponent policies, complemented by an exponential lower bound. A new method solves bilevel optimization problems in competitive Markov games.
problem Capturing competitive structures in RL with multiple interacting policies.
method Penalty-augmented Nikaido-Isoda descent-ascent (PANDA) method.
result PANDA converges to stationary points without convexity assumptions.
Study on policy testing in MDPs with lower bounds and new algorithm.
problem Deciding if policy value exceeds a threshold with limited samples.
method Derived lower bound, proposed new algorithm, reformulated problem, used policy optimization in reversed MDP.
result New algorithm outperforms existing methods in policy testing.
We present for the first time an asymptotic convergence analysis of two time-scale stochastic approximation driven by `controlled' Markov noise. In particular, both the faster and slower recursions have non-additive controlled Markov noise components in addition to martingale difference noise. We analyze the asymptotic…
New algorithms achieve logarithmic regret in KL-regularized Markov games.
problem Improving sample efficiency in game-theoretic settings with KL regularization.
method Developed OMG and SOMG algorithms for matrix and Markov games, using best response sampling and superoptimistic bonuses.
result Logarithmic regret in T T T that scales inversely with KL regularization strength β β β . To overcome the curses of dimensionality and modeling of Dynamic Programming (DP) methods to solve Markov Decision Process (MDP) problems, Reinforcement Learning (RL) methods are adopted in practice. Contrary to traditional RL algorithms which do not consider the structural properties of the optimal policy, we propose …
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.
Bootstrap method for Markov chains in reinforcement learning.
problem Distributional consistency in finite controlled Markov chains with unknown control policies.
method Model-based bootstrap with novel LLN and CLT for visitation counts and transition increments.
result Asymptotically valid confidence intervals for value and Q Q Q -functions in offline RL. DR-RPO optimizes robust policies in RL with limited interaction, achieving sublinear regret.
problem Policy optimization in RL under distribution shift and adversarial dynamics.
method DR-RPO algorithm incorporating reference-policy regularization and upper confidence bonus for exploration.
result DR-RPO achieves sublinear regret and polynomial suboptimality bounds in robust RL.
Paper explores PG for MCR, finding suboptimal policies but providing bounds.
problem Optimizing coherent risk in MDPs using PG.
method Developed practical PG implementation using state distribution reweighting.
result PG can learn risk-sensitive policies but suboptimality is common.
A method to learn robust policies for environments with model mismatches.
problem Training agents in high-stakes scenarios with mismatched training and real environments.
method Formalizes the perturbation as a zero-sum game to find Nash Equilibrium, which corresponds to the robust policy.
result Our algorithm can find a near-optimal robust policy with high probability using polynomial samples.
New algorithm identifies best policy in MDPs faster.
problem Identifying the best policy in Markov Decision Processes.
method Problem-dependent lower bound and first algorithm with instance-specific sample complexity.
result First algorithm with reduced exploration rate for faster convergence.
The paper tackles robust reinforcement learning with performance guarantees.
problem Finding a robust policy for RMDP with state space uncertainties.
method Proposes RLSPI algorithm for learning optimal robust policy with performance bounds.
result Demonstrates the performance of RLSPI on standard benchmark problems.
The paper studies risk-sensitive MDPs with recursive risk measures.
problem Risk-sensitive decision-making in MDPs with unbounded costs.
method Recursive application of static risk measures, Bellman equation derivation, existence of optimal policies.
result Existence of Markovian optimal policies for infinite planning horizons, contractive model for stationary optimal policy.
New algorithms for RL in Markov games with independent linear function approximation, breaking the curse of multiagents.
problem Tackles the challenge of learning Markov equilibria in large state space Markov games with multiple agents.
method Proposes independent linear Markov games and designs new algorithms for learning Markov coarse correlated equilibria and Markov correlated equilibria with polynomial sample complexity.
result Breaks the curse of multiagents by achieving sample complexity bounds that scale polynomially with each agent's function class complexity.
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.