1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you add a bit more structure? It is not even clear whether the rewards are bounded. $\endgroup$ – Michael Greinecker May 11 at 21:17
  • $\begingroup$ As Michael suggests, in this generality there need not be a stationary optimal strategy, nor, in fact, an optimal strategy. If the set of actions is not compact (or the payoff function is not continuous over the set of actions), then even if there is only one card in the deck and no punishment at all, there need not be an optimal action, since there might not be an action that yields the supremum of the payoffs. $\endgroup$ – Eilon May 12 at 13:26
  • $\begingroup$ Thank you both I missed this subtlety. Indeed there is nice structure on the reward. Here is the relevant portion I added to the main text. The reward for each possible action is determined by the card the agent draws. The action space is some bounded continous 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. $\endgroup$ – TPaul May 12 at 15:38
2
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your formulation is very close to correct. There is one problem I am seeing in your formulation you have $s=0$ as a single state. In reality there are many $s_0$ (corresponding to cards in the deck) that alter the reward function. Trying to use your formulation here, there is an uncountable set of actionable states which i will call $S_0$ and a distribution $D$ over this set. Now $p(s,a) = \delta_{s-1}$ for $s \notin S_0 \cup s_1$ and $p(s_1,a) = D$. The reward $r(s,a) = 0$ for all $s \notin S_0$. Now there is no state you return to infinitely often however you return to the set $S_0$. $\endgroup$ – TPaul May 13 at 17:33
  • $\begingroup$ If I understand you right (original descrition of the problem), $A$ and not $S$ should be interpreted as the deck of cards. Then an action $a \in A$ is just the card chosen. Since you put the chosen card back this simple interpretation is possible. Unfortunately in the original problem it is not clear what is action and what is state. $\endgroup$ – Dieter Kadelka May 13 at 19:04
  • $\begingroup$ The card drawn is the state not the action. The cards are always drawn from the same distribution but you do not get to pick a specific card. Based on which card is drawn you have access to a different set of actions. $\endgroup$ – TPaul May 13 at 22:01
  • $\begingroup$ @TPaul Sorry, without more information about the "game" I do not know which model is appropriate. The essentially point is (and without further information only you can decide): Before (!) you draw a card is there any information which changes from draw to draw. For model building it is irrelevant what you call state and what action. These are words we use for convenience. We can make $A$ as complicated as we will, of course with the possible consequence that nothing can be efficiently computed. In your case $A$ may even be a set of functions or probability measures. $\endgroup$ – Dieter Kadelka May 14 at 8:49
  • $\begingroup$ Thanks for all of your help. To answer your question there is no information which changes from draw to draw before you draw. To elaborate further, imagine every action results in a number of tokens being recieved in exchange for being placed in a certain place in the unactionable chain. Now imagine every card has a number which represents how much you value tokens in that round. So your action will depend on which card is drawn but the deck of cards does not change over time. $\endgroup$ – TPaul May 14 at 15:14

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.