Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In a Markov Decision Process (MDP), the discounted total reward is defined as $\sum_{t=0}^\infty \gamma^tr_t$ where $r_t$ is the reward perceived at time $t$ and $\gamma$ is a real number $\in ]0, 1[$. The average total reward is defined as $\lim_{t\rightarrow \infty}\frac{\sum_{i=0}^tr_i}{t}$.

My question is: does a policy $\pi$ that maximizes the discounted total reward also maximize the average total reward and vice versa? Or there is a policy $\pi$ that maximizes the first and $\pi'$ that maximizes the second where $\pi \neq \pi'$?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Consider first the extreme case where future value is steeply discounted, meaning that $\gamma$ is very small, close to $0$. In this case, the discounted total reward approaches identity with $r_0$, and the maximizing policy in that case will approach the policy of maximizing $r_0$. This makes sense, since if you don't value future rewards, then you should try to maximize the present reward. The average total reward, in contrast, can depend sensitively on future rewards $r_n$, and so we shouldn't expect the two policies to coincide in general.

This way of thinking guides one toward a counterexample where the policies differ: in a Markov decision process where there is comparatively large but deferred reward---that is, a choice between a small present reward followed by a large future payoff and a medium-sized present reward followed by a small future payoff---the two policies will come to different maximizing decisions.

share|improve this answer
    
Similarly, when $\gamma$ approaches $1$, then future reward is treated on a par with current reward, and we should expect the two policies to increasingly agree. In any finite system, with $\gamma$ close enough to $1$, the maximizing policies will come to the same decision. –  Joel David Hamkins Dec 1 '10 at 21:15
    
Thanks. So without any constraint on gamma (except that $\gamma \in ]0, 1[$) the optimal policy for discounted total reward and the optimal policy for average total reward may be different. I'm also looking if they can be different if the MDP has only one state (always same actions are available at each step). –  Lamine Dec 2 '10 at 8:25
    
But if there is only one state, then isn't it clear that either maximizing criterion will require you to choose the action with the largest immediate reward? A policy must always choose the same action from the same state, and so choosing a lesser action will lead to a worse outcome with respect either to average value or discounted value. –  Joel David Hamkins Dec 2 '10 at 13:23
    
I'm working on the relation between Markov decision processes and Game Theory. In this context the agent cannot know which action has the largest immediate reward since the reward is random. This randomness is due to actions of other players which are not known by the agent (which models some player $i$). If the reward function is deterministic, the optimal policy must also be deterministic (always the same action from the same state). But if the reward function is random, the optimal policy can be stochastic (it represents mixed Nash equilibria in the modeled game). –  Lamine Dec 3 '10 at 8:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.