Imagine a single player game that begins with six empty squares printed on a casino table. Each turn:

  • The player pays a publicly visible, flat-rate cost (I'll call it "c") to take the turn
  • The player declares a number (with some restrictions)
  • A number of time(s) equal to the declared number, uniformly randomly selected square(s) are incremented, using six-sided dice as counters (each square can contain one die)
  • If the dice display certain configurations listed in a publicly visible payout table ("four 6's," "five 3's," "every number 1-6," etc., square order is never important), then the player wins the corresponding payout.

Then the next turn begins from the new game state.

(Alternatively, we can view the cost and payout as being applied to the player's dollar balance simultaneously. In any case, the combined reward for the turn is [-c + payout].)

If any of the dice "overflow" (increment to a value of 7 or higher), no payouts are won that turn, all dice are removed from the table, and the player is forced to start fresh (obviously their dollar balance will still reflect all previous rewards). Fudging a bit for now, let's consider the "already overflown" state to have a value of 0, thus effectively constituting a terminal state which ends the episode.

Since the transition dynamics and rewards are fully known in advance, this is a planning problem. As an initial approach, we could start by finding the value of the state 6 6 6 6 6 6 and work backward. Taking another turn from this state is guaranteed to overflow at least one die, leading to a reward of [-c + 0], so the player acting greedily would not take the turn, leaving the table instead.

Then consider 6 6 6 6 6 5. Declaring "1" from this state yields a 5/6 chance of overflow, leading to a reward of [-c + 0], and a 1/6 chance of receiving a reward of [-c + "six 6's" payout]. Assuming the EV of this action turns out to be positive, a player acting greedily would prefer it to leaving the table (with an EV of 0) or declaring a larger number (with an EV of c), in which case we'll record "1" as the action our policy will choose from state 6 6 6 6 6 5, and the corresponding EV as the state's value. Since states in this game lend themselves very naturally to partial ordering (to compare the order of two states, just compare the total number of dots on all dice in each state), and since each successive time-step is guaranteed to yield a state with strictly higher magnitude than the state at the previous time-step, this backward induction approach can solve for the value and optimal action at every state, yielding our first value function and policy. Evaluating the value function or policy at the first state, with no dice on the table, reveals whether the game itself has a profitable EV.

Notice that this value function and policy (which are optimal apart from a further consideration involving our prior fudge) were generated from one sweep through the state space. My question is how to categorize this approach within the framework of dynamic programming. It seems to clearly fall under in place asynchronous dynamic programming, but would it be a (single iteration) example of policy iteration, modified policy iteration, or value iteration?

Also, suppose we were to modify the above approach for further optimization. If the first approach suggests that the game is profitable in expectation, then it's actually false that leaving the table has a value of 0; its value is equal to the value of the game itself. A player acting greedily would choose to leave the table from a profitable state if the value of the game's starting state is even more profitable, since he or she could just start the game fresh at a new table. The same is true for starting fresh after an overflow, and the positive EV of the overflown state (identical to the starting state) will trickle backward into the values of every other state in the MDP. Since the value of the starting state will also be affected by this second sweep across the state space, the approach becomes iterative/recursive. That being said, it's not clear to me which if any of the aforesaid dynamic programming solution methods it exemplifies. It should still qualify as in place asynchronous dynamic programming, but the iterations here don't seem to align with the iterations involved in policy iteration or value iteration. What method of dynamic programming is at play now?


Your Answer

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

Browse other questions tagged or ask your own question.