Conditions for optimal stationary strategies in MDPs

Question

I have a specific Markov decision process (MDP) which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal strategy depends only on the state and not the history of actions. The problem is the literature on MDPs is very large and each proof of optimal stationary strategies make different assumptions about the structure of the chain. Since my chain is generated from a problem outside of this domain it doesn't exactly fit any of the sets of assumptions I have seen so far. So I am looking for the weakest set of assumptions necessary for proving the existence of an optimal stationary strategy. Also, a resource for conditions for stationarity that doesn't require extensive knowledge of MDPs would be greatly appreciated.

I will now detail both the problem which generates my MDP and the MDP itself. The problem is as follows:

An agent is playing a game with the following steps of play

1. An agent draws a card from a deck.
2. The reward for each possible action is determined by the card the agent draws. The action space is some bounded continuous interval i.e. ($[0,M]$ for some constant $M$). The reward is also from some bounded continuous interval i.e. ($[0,D]$ for some constant $D$). The reward is monotone increasing in the action.
3. Based on the action the agent plays he is forced to sit out a (potentially random) number of rounds
4. Card is returned to the deck, the agent draws another card (Back to step 1.)

Some additional facts there can be an uncountably infinite number of cards, the set of actions and punishment for each action is the same regardless of the card drawn , all that changes is the value of the reward for each action. Now I want to show that the agents action depends only on their card.

This can be modeled as the following MDP. There are an uncountable number of states (corresponding to drawing a card) each with an uncountable number of possible actions. There is also a finite length chain of states with a single action that transitions to the next element in the chain (corresponding to waiting), the last element transitions randomly to one of the uncountable states . When in one of states with many actions an agent picks an action and gets placed in the appropriate spot in the single action chain to induce the waiting period until he is returned randomly to a many action state.

Intuitively one can think of this as an infinitely wide chain connected to a path which leads back to the infinitely wide chain.

Things I have tried:

1. The biggest roadblock is the uncountable action and state space which is usually assumed finite or at least countable. However, the reason this assumption is needed (as far as I am aware) is to prevent infinitely long chains with certain undesirable properties. I feel like my infinite width chain should satisfy some different property that makes up for this.

2. At some point I came across a sufficient condition that only needed a specific state to be visited infinitely often. This is very close to being satisfied in my chain except for a degenerate strategy which plays an action which never gets any reward or punishment regardless of which card they draw. This causes the chain to always be in the infinitely wide section and hence never revisit the same state infinitely often.

Answer 1

I think your problem is that you have not specified your model. In your verbal formulation it does not seem even to be a Markov decision model. My proposal is the following formulation: Let

$S := \mathbb{N}_0$ be the state space, $A := [0,M]$ be the action space, endowed with Borel-$\sigma$-algebra $\cal{A}$, $q \colon S \times A \to P(S)$ be a Markov kernel with $P(S)$ be the space of all probabability measures on $S$ with the property that $p(s,a) = \delta_{s-1}$ for $s > 0$. The reward is a bounded (measurable) function $r \colon S \times A \to \mathbb{R}$ (you have punishment) with $r(s,a) \equiv 0$ for all $s > 0$. Then you are in the usual framework of MDP's. The only problem here is that $A$ is not countable. I think this is artificial generality.

Further you always return infinitely often to the state $s = 0$, so your second remark does not apply. Have a look into the book "Controlled Markov Processes" from E.B. Dynkin, A.A. Yushkevich, Springer (1979), ch. 7 or "Markov Decision Processes" of M.L. Puterman, Wiley & Sons (1994), ch.8.

Edit: As usual the problem with such models is: Describes it correctly the original problem? This usually can only be solved together with the user. If my formulation is correct it can be easily solved:

Let $X_a$ be any random variable with $\mathbb{P}(X_a = s) = q(0,a)(\{s\}), s \in S$ for $a \in A$. ($X_a+1$ is the random time until we reach $s = 0$ again, if we choose action $a \in A$). If there is any $a_0 \in A$ with $$\frac{r(0,a)}{\mathbb{E}(X_a+1)} \leq \frac{r(0,a_0)}{\mathbb{E}(X_{a_0}+1)}$$ for any $a \in A$, then it is optimal to choose always action $a_0$ if we are in state $s = 0$. We tentatively assume $\mathbb{E}X_a < \infty$ for all $a \in A$. Of course $a_0$ exists if $A$ is finite. (States $s \not= 0$ here are irrelevant.)