Linear MDPs

Linear Markov Decision Processes (Linear MDPs) are a simplified model of reinforcement learning problems where the transition dynamics and reward functions are linear in a given feature space, enabling efficient algorithms despite potentially large state spaces. Current research focuses on developing computationally efficient algorithms with near-optimal regret bounds for various settings, including offline and online learning, aggregate bandit feedback, and imitation learning, often employing techniques like linear regression, optimistic value iteration, and primal-dual methods. These advancements are significant because they provide theoretically grounded and practically applicable solutions for reinforcement learning in complex environments, improving sample efficiency and addressing challenges like partial data coverage and adversarial settings.

Papers

November 10, 2024

Optimal Execution with Reinforcement Learning
Yadh Hafsi, Edoardo Vittori
Reinforcement Learning Linear MDPs Limit Order Book Multi Agent Market Optimal Execution

November 7, 2024

Performative Reinforcement Learning with Linear Markov Decision Process
Debmalya Mandal, Goran Radanovic
Markov Decision Process Linear MDPs

October 31, 2024

May 27, 2024

Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability
Volodymyr Tkachuk, Gellért Weisz, Csaba Szepesvári
Offline Reinforcement Learning Efficient Learning Trajectory Data Finite Horizon Linear Ordered Data Linear MDPs Linear Markov Decision Process

May 13, 2024

Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback
Asaf Cassel, Haipeng Luo, Aviv Rosenberg, Dmitry Sotnikov
Reinforcement Learning Optimal Regret Bandit Feedback Policy Optimization Regret Guarantee Linear MDPs Optimistic Algorithm

May 3, 2024

Imitation Learning in Discounted Linear MDPs without exploration assumptions
Luca Viano, Stratis Skoulakis, Volkan Cevher
Imitation Learning Feature Imitation Efficient Exploration Linear Function Approximation Adversarial Loss Finite Horizon Linear MDPs

March 4, 2024

Tsallis Entropy Regularization for Linearly Solvable MDP and Linear Quadratic Regulator
Yota Hashizume, Koshi Oishi, Kenji Kashima
Regularization Model Linear Quadratic Regulator Shannon Entropy Linear MDPs Maximum Entropy Reinforcement Learning Tsallis Entropy

February 7, 2024

A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
Kihyuk Hong, Ambuj Tewari
Reinforcement Learning Offline Reinforcement Learning Optimal Policy Primal Dual Algorithm Linear MDPs Sample Complexity Bound

October 23, 2023

Making RL with Preference-based Feedback Efficient via Randomization
Runzhe Wu, Wen Sun
Reinforcement Learning Active Learning Regret Minimization Human Like RL Linear MDPs Randomization Program User Feedback

October 11, 2023

Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore
Gellért Weisz, András György, Csaba Szepesvári
Online Reinforcement Learning Episodic Markov Decision Process Linear MDPs Linear Markov Decision Process

June 18, 2023

On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization
Mudit Gaur, Amrit Singh Bedi, Di Wang, Vaneet Aggarwal
Neural Network Actor Critic Algorithm Global Convergence Linear MDPs Critic Regularization

May 22, 2023

Offline Primal-Dual Reinforcement Learning for Linear MDPs
Germano Gabbianelli, Gergely Neu, Nneka Okolo, Matteo Papini
Offline Reinforcement Learning Optimal Policy Primal Dual Near Optimal Policy Linear MDPs Average Reward MDPs Primal Dual Reinforcement Learning

April 25, 2023

What can online reinforcement learning with function approximation benefit from general coverage conditions?
Fanghui Liu, Luca Viano, Volkan Cevher
Reinforcement Learning Online Reinforcement Learning Function Approximation Sample Efficient Efficient Reinforcement Learning Higher Coverage Rate Linear MDPs

March 17, 2023

A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games
Anna Winnicki, R. Srikant
Reinforcement Learning Policy Iteration Zero Sum Markov Game Linear MDPs

January 30, 2023

Refined Regret for Adversarial MDPs with Linear Function Approximation
Yan Dai, Haipeng Luo, Chen-Yu Wei, Julian Zimmert
Loss Function Optimal Regret Linear Function Approximation Linear MDPs Adversarial Markov Decision Process

December 12, 2022

November 28, 2022

Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation
Arnob Ghosh
High Efficiency Bandit Feedback Model Free Markov Game Single Agent Linear Function Approximation Linear MDPs

October 3, 2022

Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
Dan Qiao, Yu-Xiang Wang
Reinforcement Learning Optimal Policy Linear Function Approximation Linear MDPs Reward Free Reinforcement Learning Optimal Deployment

Linear MDPs

Papers

Optimal Execution with Reinforcement Learning

Performative Reinforcement Learning with Linear Markov Decision Process

Demystifying Linear MDPs and Novel Dynamics Aggregation Framework

Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs

Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability

Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback

Imitation Learning in Discounted Linear MDPs without exploration assumptions

Tsallis Entropy Regularization for Linearly Solvable MDP and Linear Quadratic Regulator

A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs

Making RL with Preference-based Feedback Efficient via Randomization

Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore

On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization

Offline Primal-Dual Reinforcement Learning for Linear MDPs

What can online reinforcement learning with function approximation benefit from general coverage conditions?

A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games

Refined Regret for Adversarial MDPs with Linear Function Approximation

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

VO$Q$L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation

Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation