Learning and planning for time-varying MDPs using maximum likelihood estimation

Melkior Ornik, Ufuk Topcu

Research output: Contribution to journalArticlepeer-review


This paper proposes a formal approach to online learning and planning for agents operating in a priori unknown, time-varying environments. The proposed method computes the maximally likely model of the environment, given the observations about the environment made by an agent earlier in the system run and assuming knowledge of a bound on the maximal rate of change of system dynamics. Such an approach generalizes the estimation method commonly used in learning algorithms for unknown Markov decision processes with time-invariant transition probabilities, but is also able to quickly and correctly identify the system dynamics following a change. Based on the proposed method, we generalize the exploration bonuses used in learning for time-invariant Markov decision processes by introducing a notion of uncertainty in a learned time-varying model, and develop a control policy for time-varying Markov decision processes based on the exploitation and exploration trade-off. We demonstrate the proposed methods on four numerical examples: A patrolling task with a change in system dynamics, a two-state MDP with periodically changing outcomes of actions, a wind ow estimation task, and a multi-armed bandit problem with periodically changing probabilities of different rewards.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
StatePublished - 2021


  • Changing environment
  • Markov decision processes
  • Maximum likelihood estimation
  • Online learning
  • Uncertainty quantification

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Learning and planning for time-varying MDPs using maximum likelihood estimation'. Together they form a unique fingerprint.

Cite this