Reachability in MDPs

Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices TVT\subseteq V, determine whether there is an infinite path that visits a vertex in TT at least once (i.e. you want to reach some vertex in TT).

Parameters

  • nn: number of vertices
  • mm: number of edges
  • MECMEC: O(\min(n^2, m^{1.5}))

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table