Model selection in markovian processes

By Assaf Hallak, Dotan Di Castro, Shie Mannor. 2013

25 citations recorded by the source corpus.

When analyzing data that originated from a dynamical system, a common practice is to encompass the problem in the well known frameworks of Markov Decision Processes (MDPs) and Reinforcement Learning (RL). The state space in these solutions is usually chosen in some heuristic fashion and the formed MDP can then be used to simulate and predict data, as well as indicate the best possible action in each state. The model chosen to characterize the data affects the complexity and accuracy of any further action we may wish to apply, yet few methods that rely on the dynamic structure to select such a model were suggested. In this work we address the problem of how to use time series data to choose from a finite set of candidate discrete state spaces, where these spaces are constructed by a domain expert. We formalize the notion of model selection consistency in the proposed setup. We then discuss the difference between our proposed framework and the classical Maximum Likelihood (ML) framework, and give an example where ML fails. Afterwards, we suggest alternative selection criteria and show them to be weakly consistent. We then define weak consistency for a model construction algorithm and show a simple algorithm that is weakly consistent. Finally, we test the performance of the suggested criteria and algorithm on both simulated and real world data.

Subfields: Artificial Intelligence

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

Citations in the corpus

Graying the black box: Understanding DQNs (2016, background): “In order to capture the game dynamics, DQN represents a state by a sequence of history frames and pads initial states with zero frames.”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, background): “The very few results that come with finite sample guarantees can only handle a small number of candidate abstractions (Hallak et al., 2013; Ortner et al., 2014; Jiang et al., 2015).”
Visualizing Dynamics: from t-SNE to SEMI-MDPs (2016, methodology): “We follow the analysis of (Hallak et al., 2013) and define criteria to measure the fitness of a model empirically.”
Spatio-Temporal Abstractions in Reinforcement Learning Through Neural Encoding (2016, methodology): “Motivated by (Hallak et al., 2013), we define the Value Mean Square Error(VMSE).”
Abstraction Selection in Model-based Reinforcement Learning (2015, methodology): “Nevertheless, there are interesting similarities between our Algorithm 1 and the method of Hallak et al. (2013): both algorithms test relative properties of hc and hf so as to avoid the large primitive representation, and both choose the coarser abstraction unless a statistical test rejects the…”