Efficient Learning in Non-Stationary Linear Markov Decision Processes

By Ahmed Touati, Pascal Vincent. 2020

33 citations recorded by the source corpus.

We study episodic reinforcement learning in non-stationary linear (a.k.a. low-rank) Markov Decision Processes (MDPs), i.e, both the reward and transition kernel are linear with respect to a given feature map and are allowed to evolve either slowly or abruptly over time. For this problem setting, we propose OPT-WLSVI an optimistic model-free algorithm based on weighted least squares value iteration which uses exponential weights to smoothly forget data that are far in the past. We show that our algorithm, when competing against the best policy at each time, achieves a regret that is upped bounded by $\widetilde{\mathcal{O}}(d^{7/6}H^2 \Delta^{1/3} K^{2/3})$ where $d$ is the dimension of the feature space, $H$ is the planning horizon, $K$ is the number of episodes and $\Delta$ is a suitable measure of non-stationarity of the MDP. This is the first regret bound for non-stationary reinforcement learning with linear function approximation.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

How researchers see this paper

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

In Artificial Intelligence

  1. Matthew Riemer
  2. Irina Rish
  3. Khimya Khetarpal
  4. Doina Precup
  5. Ben M. Hambly
  6. Huining Yang
  7. Renyuan Xu
  8. Sergey Levine

In Electrical and Electronic Engineering

  1. Doina Precup
  2. Ben M. Hambly
  3. Irina Rish
  4. Huining Yang
  5. Matthew Riemer
  6. Renyuan Xu

In Management Science and Operations Research

  1. Doina Precup
  2. Ben M. Hambly
  3. Irina Rish
  4. Huining Yang
  5. Khimya Khetarpal
  6. Matthew Riemer
  7. Renyuan Xu
  8. Sergey Levine

Citations in the corpus