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

<p>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.</p>

CC BY-SA 3.0
2015-04-15T06:58:05.200Z
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?
Metta World Peace
CC BY-SA 3.0
2015-04-15T04:29:26.267Z
2015-04-15T04:29:26.267Z
Sander Heinsalu
<p>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.</p>

<p>For the original reference, see the corollary to Theorem 1 <a href="http://projecteuclid.org/euclid.aoms/1177704593" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2015-05-11T00:31:37.993Z
2015-05-11T00:31:37.993Z
Michael Greinecker
<p>In a context that future return is discounted by a constant parameter, <a href="http://en.wikipedia.org/wiki/One-shot_deviation_principle">one-shot deviation principle</a> holds for both repeated games and dynamic programming.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2015-02-19T14:14:41.570Z
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....
usul
<academic-graduate><dynamic-programming><dynamic-games>
One-shot deviation principle for infinite repeated games and dynamic programming
Metta World Peace
# One-shot deviation principle for infinite repeated games and dynamic programming

(Asked by: username_0 on 2015-02-16)

In a context that future return is discounted by a constant parameter, [one-shot deviation principle](http://en.wikipedia.org/wiki/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?

**Tags:** academic-graduate, dynamic-programming, dynamic-games

> **Comments:**
> **username_1**: 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....  

---

## 2 answers

### Answer by username_2 on 2015-04-15. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  

---

### Answer by username_3 on 2015-05-11. Score: 2

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](http://projecteuclid.org/euclid.aoms/1177704593).


---

