5
$\begingroup$

In a context that future return is discounted by a constant parameter, one-shot deviation principle holds for both repeated games and dynamic programming.

Because, in repeated games, a one-shot deviation refers to one history, so on equilibrium path, a one-shot deviation could produce a play that differs on more than one stages from the original equilibrium path.

Is it true for the sequence of state variables and control variables in dynamic programming? In other words, can a one-shot deviation generate an aforementioned sequence that differs for more than one stage?

Improve this question
$\endgroup$
  • $\begingroup$ I don't understand what the question is asking. Can you expand or explain more formally? Dynamic programming is just a general technique that is only useful for solving some problems. When it is useful, it is because the optimal solution has the form of optimally solving subproblems, then making the optimal decision at the current "level" given the subproblems' solutions. Since we make the optimal decision at each step or level, of course any other decision or "deviation" would be no better.... $\endgroup$ – usul Feb 19 '15 at 14:14
2
$\begingroup$

A deviation (one-shot or not) can certainly generate a sequence that differs from the optimal one for an arbitrary number of periods.

You could treat a dynamic programming problem as a repeated game between one player and chance. The one-shot deviation principle should then carry over from repeated games to dynamic programming.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your answer. But it occured to me, your argument holds only for stochastic dynamic programming, right? What if the transition rule on state space is deterministic? $\endgroup$ – Metta World Peace Apr 15 '15 at 6:58
2
$\begingroup$

There is an old result in dynamic programming due to David Blackwell, according to which stationary problems allow for stationary best responses. So if you would gain by changing your behavior after a certain history, you would gain by changing it at every history corresponding to the same state.

For the original reference, see the corollary to Theorem 1 here.

Improve this answer
$\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.