2
$\begingroup$

I'm trying to find an optimal policy for a Stochastic game which I thought was simple, but seems increasingly complicated! It seems like this problem is accessible with a Markov Decision Process, but I'm unsure about how to include the rewards. I'm not very familiar with MDPs in general, but it feels like the decisons required in this game are appropriate for an MDP.

The game:

  • Players run a business where they make money by sending elves out to cut down christmas trees and sell them. The winner is the player with the most money at the end of 10 turns.

  • There are three possible locations to send elves: Woods (\$10 per tree), Forest (\$20) and Mountain (\$50).

  • Risks are associated with different tree locations, depending on the weather: If the weather is bad (where p(bad weather) = 1/3): Elves in the forest return empty handed Elves on the mountain get lost and never return.

  • Each turn, players can hire more elves ($75 each)

  • Players start with 12 elves, and $0.

My questions:

  • Could this be modelled using an MDP where the player state is number of elves, and amount of cash, and the actions are the allocation of elves to locations, and number of elves to hire? How would I do this specifically?
  • What cost is associated with sending elves to the mountain (since it's delayed, and based on the weather)?
  • Would I use reinforcement learning to find an optimal strategy? (Or even a good one!)
$\endgroup$
1
$\begingroup$

I received the following answer from an academic at Edinburgh University, Kousha Essetami, and wanted to repost it here:

It is indeed possible to model your problem as a so-called:

"finite-horizon MDP with expected total reward objective"

One can then, in principle, solve such a model to find the optimal policy by using a "backward induction" dynamic programming algorithm.

However, because of the finite-horizon structure, and because both the amount of money accumulated so far, and the number of elves obtained so far, are part of the state, and because there are ponentially many (but only a bounded number of) choices for "moves" at each state, one important issue is that the number of states and moves in the model can potentially get very large (this is often referred to as the "curse of dimensionality" or the "state explosion problem").

(But the number of states/moves is nevertheless always finite, because of the finite-horizon nature (namely a fixed number, 10, of rounds) ensures that the total amount of elves and money accumulated at any time during play, and upon termination after 10 rounds, can not exceed a specific finite amount.)

Because of the potentially large state space, such a model will not be very easy to solve by hand: you will need a computer implementation of, e.g., the backward induction algorithm to solve it. This is so especially if the number of rounds and initial number of elves/money is large. In your case, with 10 rounds, and with initially 12 elves and no money, it should hopefully be managable for a computer to solve such a model, (with, say, a 10^6 rounds, and 10^5 initial elves, it would become prohibitively inefficient to solve it by backward induction, even on a computer, and one would need to try to invent new specialized ways to solve this specific model).

In more detail, here is a way that you could set this up as an MDP model. We view things from the point of view of a single player who is trying to optimize its expected total earnings during the 10 rounds.

1) each "state" of the MDP encodes: the amount of money accumulated thus far by the player, and the number of elves that the player has, the number of "rounds" that have been played thusfar, and finally, whether or not the player has already made its choice regarding how many elves to buy before the next round (and after the prior one).

So, a "state" is given by a quadruple of numbers: (i,j,k,b), where i is a number between 0 and 10, specifying the number of rounds that have been played thusfar, where j specifies the number of elves the player has, where k specifies the amount of money the player has, and where b is a "bit" (i.e., either 0 or 1) which specifies whether the player has already made its choice regarding whether to purchase any elves prior to the next round (b=0 means the choice has not yet yet been made, and b=1 means that the choice has been made).

So the "initial state" that the player starts in is: (i,j,k,b) := (0,12,0,0)

2) Now lets consider what happens in any state:

When the player is currently in a state (i,j,k,0), i.e., it has not yet made a choice about its purchase of elves before the next round, the first thing it needs to do is to choose how many elves it want to buy with its current money k. Of course, it can only buy at most \floor(k/75) states So, the player has precisely \floor(k/75)+1 choices: it can choose to buy 0,1,2, ...., or \floor(k/75) elves before the next round.

Suppose the player makes its choice, and decides to buy m elves, then the new "state" after this choice "move" will be: (i,j+m,k-(m*75),1)

Next, we have to specify what happens when a player is in some state of the form (i,j,k,1) (in other words, after it has chosen its elve purchase).

In such a state, the player next has to choose how many elves to send into the woods, into the forest, and into the mountains, respectively.

Specifically, it has j elves to use up, and it has to make a "choice move" specified by a triple of non-negative numbers (a,b,c), such that a + b + c <= j, where a is number of elves that it chooses to send to the woods, b is the number elves that it chooses to send to the forest, c is the number that it chooses to send to the mountains.

Having made that choice (a,b,c), then with certain probabilities the player accumulates some payoffs from the trees cut by the elves, and with certain probabilities loses some elves, etc.

It is possible to calculate these probabilities in such a way as so set up "probabilitic transitions" such that after choice (a,b,c) is made, the "state" transitions with some specific probability p(a,b,c,alpha), to a new state alpha.

By this I mean the following: if currently in state (i,j,k,1) the player makes choice move (a,b,c), then for some calculatable probability p(a,b,c,j',k') (which we can calculate based on the 1/3 probability of bad weather, and the choices (a,b,c) of where to send the elves in that round) we transition next with probability p(a,b,c,j',k') to the state (i+1,j-j',k+k',0), where j' is the number of elves lost in the mountains, which can be between 0 to c, and k' is the amount of money made by the elves in that round.

Note that the number of possible values of j' and k' is bounded, so this remains a "finite state" model.

(Notice that we have in the above state updated the number of rounds played thusfar to i+1, and we have reset the bit b=0 to indicate that we have not yet chosen whether to purchase elves before the (new) next round).

I will not specify in detail how to calculate the above transition probabilities, but if you know a little basic probability it is not difficult see how one can calculate them.

In this way, the player continues to play until we have finished 10 rounds, i.e., until we have reached a state (10,j,k,0).

In such a state, the play terminates, and the player receives the "payoff" k (which is the amount of money it has accumulated by the end).

Of course, the player's goal in this model is to maximize the EXPECTED VALUE of its total payoff at the end of play (i.e., upon termination after 10 rounds), starting from the initial state (0,12,0,0).

That completes the description of the finite-horizon MDP. (This is in fact also an example of what one calls a 1-player finite extensive form game of perfect information, with chance moves.)

Once we "build" such a model, we can "solve" for the optimal strategy by a "backward induction" algorithm.

I will not explain this algorithm in detail here (it is described more generally in the lecture notes for my algorithmic game theory course), but the basic idea is that one starts at the "leaves" of the game tree (i.e., at the terminal states in this MDP), and by induction going back up the tree, one makes an optimal choice for (a,b,c) at that state, depending on the already computed optimal expected payoffs that have been calculated for all of its "children" (i.e., states in the "next" round).

$\endgroup$
0
$\begingroup$

Could this be modelled using an MDP where the player state is number of elves, and amount of cash, and the actions are the allocation of elves to locations, and number of elves to hire?

Sure. Unless the effects are delayed from actions, in which case the state should include that.

If so, what cost is associated with sending elves to the mountain?

You want to maximize the total amount of money, so the reward at the end of each turn is the gross profit.

Would I use reinforcement learning to find an optimal strategy? (Or even a good one!)

I don't see why not.

$\endgroup$
  • $\begingroup$ Does this address the game theory aspect - the end goal is not to maximize the expected amount of money but the probability of having most, which may change the strategy? $\endgroup$ – Juho Kokkala May 4 '16 at 13:06
  • $\begingroup$ @DonReba, I've edited the question. Could you give me more detail on how to do this? The potential loss of elves on the mountain is delayed, so how would I include that in the state? $\endgroup$ – TMrtSmith May 4 '16 at 14:11
  • $\begingroup$ @JuhoKokkala This would depend on whether players have information about each other's scores? $\endgroup$ – TMrtSmith May 4 '16 at 14:12

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.