3

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987). When the decision horizon is infinite and we are using e.g. the ...


3

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a ...


1

One can verify that the following matrix $\Gamma$ has the desired properties: $\Gamma = [\pi]Q - Q^{\top}[\pi]$, where $[\pi]$ is a diagonal matrix with diagonal elements being the stationary distribution. This construction relates closely to the reversibility of a Markov chain as far as I know.


Only top voted, non community-wiki answers of a minimum length are eligible