Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

By Lin F. Yang, Mengdi Wang. 2019

315 citations recorded by the source corpus.

Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional value and policy functions using given features. However existing methods either have no theoretical guarantee or suffer a regret that is exponential in the planning horizon $H$. In this paper, we propose an online RL algorithm, namely the MatrixRL, that leverages ideas from linear bandit to learn a low-dimensional representation of the probability transition model while carefully balancing the exploitation-exploration tradeoff. We show that MatrixRL achieves a regret bound ${O}\big(H^2d\log T\sqrt{T}\big)$ where $d$ is the number of features. MatrixRL has an equivalent kernelized version, which is able to work with an arbitrary kernel Hilbert space without using explicit features. In this case, the kernelized MatrixRL satisfies a regret bound ${O}\big(H^2\widetilde{d}\log T\sqrt{T}\big)$, where $\widetilde{d}$ is the effective dimension of the kernel space. To our best knowledge, for RL using features or kernels, our results are the first regret bounds that are near-optimal in time $T$ and dimension $d$ (or $\widetilde{d}$) and polynomial in the planning horizon $H$.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Provable Representation Learning for Imitation with Contrastive Fourier Features (2021, background): “, [4, 39]), while to our knowledge no previous work has demonstrated a practical”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “In this paper, we have explored representation selection for reinforcement learning by focusing on a special class [Yang and Wang, 2020] of low-rank MDPs [Yang and Wang, 2019, Jin et al., 2020].”
Recent advances in reinforcement learning in finance (2021, background): “To tackle this issue, Yang and Wang (2020) learned a low-dimensional representation of the probability transition model and proved that their MatrixRL algorithm achieves a regret bound of ̃(𝑇2 𝑑√𝑀), which depends on the number of features 𝑑 rather than || and ||.”
Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “We also note that their very recent work [49], developed independently of the current paper, provides sample efﬁciency guarantees for exploration in the linear MDP setting.”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “In this setting, without additional assumptions, our regret bound will match that of (Yang & Wang, 2019a).”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, background): “…we also note that there many results for facing the exploration problem in continuous MDP with parametric structure, e.g., linear-quadratic systems (Abbasi-Yadkori & Szepesvári, 2011) or other linearity assumptions (Yang & Wang, 2019; Jin et al., 2019), which are outside the scope of our paper.”
Efficient Learning in Non-Stationary Linear Markov Decision Processes (2020, background): “Another structural assumption, that received attention in the recent literature (Yang and Wang, 2019; Jin et al., 2020; Zanette et al., 2020a), is when both reward and transition dynamics are linear functions with respect to a given feature mapping.”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “Later work gave computationally efficient algorithms for certain special cases (Dann et al., 2018; Du et al., 2019a; Yang & Wang, 2019b; Jin et al., 2019).”
Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, methodology): “In the contexture of RL with function approximations, our work is also related to a vast body of recent progress (Yang and Wang, 2020; Jin et al., 2020b; Cai et al., 2020; Du et al., 2021; Kakade et al., 2020; Agarwal et al., 2020; Zhou et al., 2021; Ayoub et al., 2020) on the sample eﬃciency of RL…”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “Turning to reinforcement learning with function approximation and exploration, a large body of effort focuses on (essentially) linear methods (Yang and Wang, 2019b; Jin et al., 2019; Cai et al., 2019; Modi et al., 2020; Du et al., 2019c; Wang et al., 2019).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, methodology): “…setting, sample-efﬁcient algorithms have been proposed using linear function approximators (Abbasi-Yadkori et al., 2019a,b; Jin et al., 2019; Yang and Wang, 2019a; Zanette et al., 2019; Du et al., 2019b; Cai et al., 2019; Wang et al., 2019), as well as nonlinear ones (Wen and Van Roy,…”
Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation (2020, methodology): “Similar to Lemma 14 in (Dani et al., 2008) and Lemma 13 in (Yang & Wang, 2019), we apply Freedman’s inequality to show that when ϑ h, 1 , . . . , ϑ h,N are appropriately chosen, the truncated martingale =1 α ,t n =1 , 2 ,...,N never grows too large.”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “We note that a low-rank MDP strictly generalizes the linear MDP model (Yang and Wang, 2020; Jin et al., 2020a) which assumes φ is known a priori.”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “…MDPs defined in Assumption 2.1 and the one studied by (Yang & Wang, 2019b; Jin et al., 2019) both cover the tabular setting and the one proposed by (Yang & Wang, 2019a) as special cases, they are two different definitions of linear MDPs as their feature maps ψ(·, ·, ·) and ϕ(·, ·) are defined on…”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “y consider the functionapproximationsetting with linear value functions. Positive results: upper bounds When the action value function has a linear parameterization and the transitions are low rank, [Yang and Wang, 2020, Jin et al., 2020, Zanette et al., 2020a] propose regret-minimizing online algor”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, unknown): “…2017, Krishnamurthy et al., 2016, Jiang et al., 2017, Dann et al., 2018, Du et al., 2019b, Feng et al., 2020, Du et al., 2019c, Zhong et al., 2019, Yang and Wang, 2019, Jin et al., 2019, Du et al., 2019a, Roy and Dong, 2019, Lattimore and Szepesvari, 2019, Du et al., 2020, Zanette et al., 2020].”