A Markov Decision Process (MDP) is a popular model for reinforcement learning. However, its commonly used assumption of stationary dynamics and rewards is too stringent and fails to hold in adversarial, nonstationary, or multi-agent problems. We study an episodic setting where the parameters of an MDP can differ across…
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,695 papers · 148 categories
Trend · papers per month
48 results for “Adversarial MDPs”
Improved FPL algorithms for adversarial MDPs with better regret bounds.
problem Adversarial rewards and unknown transitions in MDPs.
method Refined analysis of FPL algorithms, matching current best regret bounds.
result Improved regret bounds for FPL algorithms in adversarial MDPs.
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 .
Improved exploration in adversarial MDPs via dilated bonuses.
problem Global exploration in adversarial MDPs with local-search policies.
method Dilated bonuses to facilitate global exploration.
result Improved regret bounds in various MDP settings.
Algorithm POLO learns low-rank MDPs with adversarial changes in full-info feedback.
problem Learning low-rank MDPs with adversarial changes and unknown transition probabilities.
method Policy optimization-based algorithm POLO with regret guarantee.
result POLO achieves sublinear regret guarantee with no dependence on state space size.
Deep RL policies share adversarial features across different MDPs.
problem Understanding decision boundaries and loss landscapes in neural policies.
method Investigating similarities in high sensitivity directions across MDPs using Arcade Learning Environment.
result High sensitivity directions for neural policies are correlated across MDPs, suggesting shared non-robust features.
New framework for reinforcement learning with adversarial preferences in tabular MDPs.
problem Learning from preferences rather than direct rewards in MDPs with adversarial settings.
method Developed PbMDPs framework, established lower bounds, and proposed algorithms for regret minimization.
result Achieved regret bounds of for PbMDPs with Borda scores.
New approach optimizes policies in adversarial MDPs using adversarial learning.
problem Optimizing policies in adversarial Markov decision processes.
method Adversarial learning on advantage functions, extending previous reductions.
result Stronger regret criteria and performance guarantees for policy optimization.
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.
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.
New algorithm reduces dynamic regret for MDPs with unknown transition and adversarial rewards.
problem Episodic linear mixture MDPs with unknown transition and adversarial rewards.
method Combines occupancy-measure-based global optimization and policy-based variance-aware value-targeted regression.
result Achieves near-optimal dynamic regret of .
Optimistic PPO variant solves linear MDPs with improved regret bound.
problem Understanding theoretical limits of PPO in linear MDPs.
method Proposes an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback.
result Establishes a regret bound.
New model selects robustly in adversarial reinforcement learning with unknown corruption.
problem Adversarial corruption in reinforcement learning with unknown total corruption amount.
method Model selection approach for finite-horizon tabular and linear MDPs.
result First worst-case optimal bound without knowledge of total corruption.
Improved regret bound for adversarial MDPs with linear function approximation.
problem Learning in adversarial MDPs with changing loss functions and large state spaces.
method Two algorithms: refined FTRL with log-barrier regularizer and magnitude-reduced loss estimator.
result Achieved regret, improving over .
Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.
problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.
method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.
result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving regret in stochastic and regret in adversarial settings.
This paper studies GAIL's global convergence for general MDP and nonlinear rewards.
problem Understanding when GAIL algorithms achieve global convergence for general MDP and nonlinear rewards.
method Characterization of global convergence for various policy gradient algorithms applied to GAIL.
result First systematic theoretical study of GAIL for global convergence.
Algorithm learns both stochastic and adversarial MDPs with best-of-both-worlds guarantees.
problem Learning episodic MDPs with known transition and bandit feedback.
method Follow-the-Regularized-Leader method with a hybrid regularizer.
result Achieves regret for stochastic losses and regret for adversarial losses.
New algorithm tackles adversarial RL without horizon constraints.
problem Adversarial reinforcement learning with unknown transition kernel.
method Uses weighted least square estimator and occupancy measure for policy search.
result Achieves near-optimal regret bound of .
Adversarial online multi-task RL with task separation.
problem Minimize regret in an adversarial online multi-task setting with unknown MDPs.
method Prove minimax and instance-specific lower bounds, develop a clustering algorithm with optimal sample complexity and regret.
result Tight sample complexity and regret bounds for adversarial online multi-task RL.
Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncs.LG
New algorithm reduces reinforcement learning regret for linear MDPs with unknown transitions.
problem Adversarial linear mixture MDPs with bandit feedback and unknown transition.
method Proposes a new algorithm with a least square estimator and self-normalized concentration.
result Achieves improved regret bound with high probability.
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…
Detects adversarial directions to make reinforcement learning policies more robust.
problem Adversarial attacks exploit non-robust directions in reinforcement learning policies, leading to instability.
method Local quadratic approximation of deep neural policy loss to identify non-robust directions.
result Provides a theoretical basis for distinguishing safe from adversarial observations.
New RL algorithm tackles online robust MDPs with uncertainty.
problem Developing robust reinforcement learning models for real-world environments.
method Proposes a robust optimistic policy optimization algorithm for online robust MDPs.
result Establishes the first regret bound for online robust MDPs.
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.
MetaCURL tackles non-stationary MDPs with optimal dynamic regret.
problem Online learning in non-stationary Markov decision processes.
method MetaCURL uses a meta-algorithm with multiple black-box algorithms and a sleeping expert framework.
result Achieves optimal dynamic regret without prior knowledge of MDP changes.
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…
New method defends RL agents from poisoning attacks without MDP knowledge.
problem Poisoning attacks on RL systems can cause learning failures.
method Generic poisoning framework for online RL, Vulnerability-Aware Adversarial Critic Poison (VA2C-P).
result Successfully prevents RL agents from learning good policies or converging to target policies.
We consider Markov Decision Processes (MDPs) where the rewards are unknown and may change in an adversarial manner. We provide an algorithm that achieves state-of-the-art regret bound of , where is the state space, is the action space, is the mixing time of the MDP, and $…
Two algorithms improve online reinforcement learning in adversarial linear MDPs with bandit feedback.
problem Online reinforcement learning in linear MDPs with adversarial losses and bandit feedback.
method Two algorithms: one computationally inefficient with $\widetilde{\mathcal{O}}\left(\sqrt{K}
ight)$ regret, and one computationally efficient with $\widetilde{\mathcal{O}}\left(K^{\frac{3}{4}}
ight)$ regret.
result Achieved improved regret performance compared to existing approaches.
Algorithm for online learning in MDPs with linear function approximation and bandit feedback.
problem Online learning in MDPs with changing reward functions and limited feedback.
method Developed MDP-LinExp3 algorithm with theoretical guarantees.
result Proved regret bounds for MDP-LinExp3 algorithm.
We address the problem of computing reliable policies in reinforcement learning problems with limited data. In particular, we compute policies that achieve good returns with high confidence when deployed. This objective, known as the \emph{percentile criterion}, can be optimized using Robust MDPs~(RMDPs). RMDPs general…
New state-only IL algorithm tackles MDP transition mismatch.
problem Transition dynamics mismatch between expert and imitator MDPs.
method Adversarial state-only IL with two subproblems solved iteratively.
result Effective performance improvement in transition dynamics mismatch scenarios.
We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of eac…
Robust RL with learned optimal adversary improves agent performance under adversarial state observations.
problem Ensuring reinforcement learning agents' robustness against adversarial perturbations of state observations.
method Proposed a framework of alternating training with learned adversaries (ATLA) to find optimal adversarial policies and enhance agent robustness.
result ATLA achieves state-of-the-art performance under strong adversaries in continuous control environments.
We study the question of how to imitate tasks across domains with discrepancies such as embodiment, viewpoint, and dynamics mismatch. Many prior works require paired, aligned demonstrations and an additional RL step that requires environment interactions. However, paired, aligned demonstrations are seldom obtainable an…
This work tackles the problem of robust zero-shot planning in non-stationary stochastic environments. We study Markov Decision Processes (MDPs) evolving over time and consider Model-Based Reinforcement Learning algorithms in this setting. We make two hypotheses: 1) the environment evolves continuously with a bounded ev…
Paper eliminates warm-up phase for PO in linear MDPs, achieving optimal regret.
problem Costly warm-up phase in PO algorithms for linear MDPs.
method Simple contraction mechanism replaces warm-up phase.
result Achieves rate-optimal regret with improved dependence on problem parameters.
New method improves DRL robustness against adversarial state observations.
problem Adversarial attacks on deep reinforcement learning agents observing state data.
method State-adversarial Markov decision process (SA-MDP) and policy regularization.
result Significant improvement in robustness of DRL algorithms under adversarial attacks.
Improves decision complexity in hybrid environments.
problem Complexity in hybrid decision-making problems.
method General extension of DEC framework, model aggregation approach.
result Improved regret bounds for linear Q*/V* MDPs.
New approach for online learning with adaptive adversaries, simpler and more effective.
problem Online learning with adaptive adversaries, especially in bandits and MDPs.
method Uses standard unbiased estimators and a simple increasing learning rate schedule, aided by logarithmically homogeneous self-concordant barriers and strengthened Freedman's inequality.
result First high-probability regret bounds for adversarial bandits and MDPs, resolving open problems.
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.
Paper shows RLHF can be solved similarly to standard RL.
problem Difficulty of RLHF compared to standard RL.
method Reduction to reward-based RL techniques.
result RLHF can be solved using existing algorithms for reward-based RL.
Adaptive reduction scheme approximates optimal policy in regularized MDPs.
problem Finding near optimal policy in regularized MDPs with biased solutions.
method Adaptive reduction of regularization parameter λ to approximate optimal policy.
result Iteration complexity reduced for obtaining ε-optimal policy.
We study Exo-MDPs to reduce sample complexity in reinforcement learning.
problem Reducing sample complexity in reinforcement learning for structured MDPs.
method Introducing Exo-MDPs and proving structural equivalence to linear mixture MDPs, establishing regret bounds.
result Proved regret bound for Exo-MDPs, matching lower bounds.
In this paper, a sparse Markov decision process (MDP) with novel causal sparse Tsallis entropy regularization is proposed.The proposed policy regularization induces a sparse and multi-modal optimal policy distribution of a sparse MDP. The full mathematical analysis of the proposed sparse MDP is provided.We first analyz…
We develop efficient and sharp bounds on policy value under perturbations in MDPs.
problem Evaluating policies under best- and worst-case perturbations in MDPs with transition observations.
method Proposed a perturbation model for MDPs, developed semiparametrically efficient estimator with asymptotic normality.
result Semiparametrically efficient and asymptotically normal estimator for policy value bounds.
GAN Q-learningstat.ML
Distributional reinforcement learning (distributional RL) has seen empirical success in complex Markov Decision Processes (MDPs) in the setting of nonlinear function approximation. However, there are many different ways in which one can leverage the distributional approach to reinforcement learning. In this paper, we p…
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.