1
$\begingroup$

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to transform the automaton to a Markov chain [our "strategy" is m(state) -> (input), so the Markov transition is L(s, m(s)) -> pr(s) where L is the (probabilistic) automaton transition and pr(s) is probability distribution of the various states].

If we say the payoff of a strategy is the asymptotic average weight attained by states of this Markov chain over time, then the problem is to find the strategy with the highest payoff. We just innumerate all the possible matrices and compare their principle eigenvectors but that would be inelegant. We could assign proxy weights to each state based on what overall payoff the states seem to offer and choose strategies which maximize this but how would one prove such a "greedy" approach is optimal. (I'm assuming every state is reachable from every other state which believe makes the start-state irrelevant for the final result).

Also, we could allow our strategy to be "mixed", use a distribution of inputs instead of a fixed input. But my sense is that this wouldn't change the problem much.

I've Googled literature on eigenvalue optimization but nothing seems directly related to this.

So is this at all solvable? Is it pathological in general? Are there references to these thing.

$\endgroup$
1
$\begingroup$

The problem I described is essentially the problem of a Markov Decision Process. The Wikipedia article says everything I need to know to start investigating this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.