Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

Time-homogeneous linear mixture MDPs

A time-homogeneous linear mixture Markov decision process is a mathematical model for sequential decision-making in reinforcement learning where the probability of transitioning from a given state and action to the next state is represented as a linear combination of known feature vectors, and this transition mechanism remains constant across every step of an episode. In this formulation, the transition probability distribution is parameterized by the inner product of a known feature mapping of the current state, action, and candidate next state with an unknown parameter vector. The time-homogeneous property dictates that this parameter vector and the underlying system dynamics are stationary and do not vary with the time step or stage of the planning horizon, unlike time-inhomogeneous models where transition dynamics change at each step. This shared, stationary structure enables reinforcement learning algorithms to efficiently approximate value functions and generalize across large or continuous state-action spaces by learning a single set of transition parameters.

1 item

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

Jiafan He, Heyang Zhao, Dongruo Zhou, Quanquan Gu

OrganizationsUniversity of California, Los Angeles

Why you should read this

Presents LSVI-UCB++, the first computationally efficient reinforcement learning algorithm for linear Markov decision processes to achieve nearly minimax optimal regret by combining variance-aware weighted regression with a rare-switching policy update scheme.

We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret Õ(d√H³K), where d is the dimension of the feature mapping, H is the planning horizon, and K is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the optimal value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.

Added

2026-10-02