Markov Decision Processes with Continuous Side Information

Aditya Modi, Nan Jiang, Satinder Singh, Ambuj Tewari

Research output: Contribution to journalConference articlepeer-review


We consider a reinforcement learning (RL) setting in which the agent interacts with a sequence of episodic MDPs. At the start of each episode the agent has access to some side-information or context that determines the dynamics of the MDP for that episode. Our setting is motivated by applications in healthcare where baseline measurements of a patient at the start of a treatment episode form the context that may provide information about how the patient might respond to treatment decisions. We propose algorithms for learning in such Contextual Markov Decision Processes (CMDPs) under an assumption that the unobserved MDP parameters vary smoothly with the observed context. We give lower and upper PAC bounds under the smoothness assumption. Because our lower bound has an exponential dependence on the dimension, we also consider a tractable linear setting where the context creates linear combinations of a finite set of MDPs. For the linear setting, we give a PAC learning algorithm based on KWIK learning techniques.

Original languageEnglish (US)
Pages (from-to)597-618
Number of pages22
JournalProceedings of Machine Learning Research
StatePublished - 2018
Externally publishedYes
Event29th International Conference on Algorithmic Learning Theory, ALT 2018 - Lanzarote, Spain
Duration: Apr 7 2018Apr 9 2018


  • KWIK Learning
  • PAC bounds
  • Reinforcement Learning

ASJC Scopus subject areas

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


Dive into the research topics of 'Markov Decision Processes with Continuous Side Information'. Together they form a unique fingerprint.

Cite this