English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study reinforcement learning (RL) with linear function approximation wherethe underlying transition probability kernel of the Markov decision process(MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou etal., 2020) and the learning agent has access to either an integration or asampling oracle of the individual basis kernels. We propose a newBernstein-type concentration inequality for self-normalized martingales forlinear bandit problems with bounded noise. Based on the new inequality, wepropose a new, computationally efficient algorithm with linear functionapproximation named $\text{UCRL-VTR}^{+}$ for the aforementioned linear mixtureMDPs in the episodic undiscounted setting. We show that $\text{UCRL-VTR}^{+}$attains an $\tilde O(dH\sqrt{T})$ regret where $d$ is the dimension of featuremapping, $H$ is the length of the episode and $T$ is the number of interactionswith the MDP. We also prove a matching lower bound $\Omega(dH\sqrt{T})$ forthis setting, which shows that $\text{UCRL-VTR}^{+}$ is minimax optimal up tologarithmic factors. In addition, we propose the $\text{UCLK}^{+}$ algorithmfor the same family of MDPs under discounting and show that it attains an$\tilde O(d\sqrt{T}/(1-\gamma)^{1.5})$ regret, where $\gamma\in [0,1)$ is thediscount factor. Our upper bound matches the lower bound$\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$ proved by Zhou et al. (2020) up tologarithmic factors, suggesting that $\text{UCLK}^{+}$ is nearly minimaxoptimal. To the best of our knowledge, these are the first computationallyefficient, nearly minimax optimal algorithms for RL with linear functionapproximation.

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes