most recent 30 from http://mathoverflow.net 2013-05-23T00:22:54Z http://mathoverflow.net/feeds/user/10537 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po Lamine 2010-11-03T14:02:59Z 2011-06-22T13:03:12Z

<p>I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it shown that an optimal policy is always deterministic ?</p> <p>If a stochastic policy exist, is it shown that some algorithms (like Q-Learning) converge to this policy ?</p>

http://mathoverflow.net/questions/54758/does-the-following-series-converge/54792#54792 Lamine 2011-02-08T17:13:12Z 2011-02-14T12:18:18Z

<p><s>Since $\pi$ is transcendental (so also $\frac{\pi}{2}$ and $\frac{3\pi}{2}$), $\forall n \in \mathbb{N} , |\sin{n}|&lt;1$. In another hand, $\sum_{n=2}^\infty|\sin{n}|^n &lt;\sum_{n=2}^\infty|\sin{n}|^2$ which converges (because $\sum_{n=1}^\infty a^n$ converges if $|a| &lt; 1$.</p> <p>So, $\sum_{n=2}^\infty|\sin{n}|^n$ converges.</s></p>

http://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48015#48015 Lamine 2010-12-02T09:08:57Z 2010-12-02T09:36:33Z

<p>A problem is in P if it is <strong>decidable in polynomial time</strong>. So if it is undecidable, it is neither in P nor in NP. It is not even recursive. See <a href="http://en.wikipedia.org/wiki/Complexity_class" rel="nofollow">http://en.wikipedia.org/wiki/Complexity_class</a>.</p>

http://mathoverflow.net/questions/47921/discounted-total-reward-vs-average-total-reward Lamine 2010-12-01T16:22:36Z 2010-12-01T20:00:53Z

<p>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}$.</p> <p>My question is : is a policy $\pi$ that maximizes the discounted total reward also maximizes the average total reward ans vice versa ? Or there is a policy $\pi$ that maximizes the first and $\pi'$ that maximizes the second with $\pi \neq \pi'$ ?</p>

http://mathoverflow.net/questions/44326/most-memorable-titles/44963#44963 Lamine 2010-11-05T16:14:13Z 2010-11-05T16:14:13Z

<p>I really like humor in scientific texts, specially in titles. One of my favorite authors is Donald E. Knuth. A title like <em>The sandwich theorem</em> makes me curious about its content. <em>The Art of Computer Programming</em> is also a nice title.</p>

http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po/44837#44837 Lamine 2010-11-04T15:47:22Z 2010-11-04T15:47:22Z

<p>I finally found the proof of this in "Markov Decision Process -- Discrete Stochastic Dynamic Programming" by Martin L. Puterman (John Wilson and Sons Ed.). It is proved that if the reward function is deterministic, the optimal policy exists and is also deterministic. But I don't know if this result can be generalized to MDPs with stochastic reward function.</p>

http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po/68508#68508 Lamine 2011-06-24T13:54:40Z 2011-06-24T13:54:40Z

If you are looking for optimal policy, there are equivalent theorems and propositions at the beginning of chapters 7 and 8. Actually, even if the reward function is random (but with fixed distribution), there is a deterministic optimal policy. The only case where there is a stochastic optimal policy but not a deterministic one is when the distribution of the reward function varies (for instance, if there is two players learning at the same time in a game without pure Nash Equilibrium).

http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po/68508#68508 Lamine 2011-06-24T13:49:39Z 2011-06-24T13:49:39Z

Theorem 6.2.10 asserts that if the set of available actions is finite for each state, then an optimal deterministic policy exists. However, you have to read (at least) all the beginning of the chapter (and some previous chapter) to understand the proof. Of course, this theorems are valid under assumptions provided in the beginning of the chapter (the set of states is finite or countable, rewards are bounded, the discount factor is $ 0 \leq \lambda &lt; 1$ and rewards and transition probabilities don't vary from decision epochs to others).

http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po/68508#68508 Lamine 2011-06-24T13:42:13Z 2011-06-24T13:42:13Z

It depends if you are looking for maximal discounted total reward or maximal average total reward. For the first one, all the beginning of chapter 6 proves progressively the existence of a deterministic optimal policy. First theorems and propositions prove the existence of an optimal policy under some assumptions. Then theorems 6.2.9 and 6.2.10 prove the existence of an optimal deterministic policy under some reasonable assumptions. For instance, theorem 6.2.9 (p. 154) attests that if an optimal policy exists, then an optimal deterministic policy also exists (it may be the same or not).

http://mathoverflow.net/questions/54758/does-the-following-series-converge/54792#54792 Lamine 2011-02-14T12:16:56Z 2011-02-14T12:16:56Z

I'm ashamed of this answer. That's what happens when I don't sleep enough.

http://mathoverflow.net/questions/47921/discounted-total-reward-vs-average-total-reward/47939#47939 Lamine 2010-12-03T08:48:41Z 2010-12-03T08:48:41Z

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).

http://mathoverflow.net/questions/47954/is-pnp-relevant-to-finding-proofs-of-everyday-mathematical-propositions Lamine 2010-12-03T08:36:21Z 2010-12-03T08:36:21Z

I meant that computing capacities increase faster than the complexity of any problem in P (if the Moore's law is true). That allows some hope to solve this problem one day.

http://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48015#48015 Lamine 2010-12-03T08:28:41Z 2010-12-03T08:28:41Z

Is there some confusion between decision problems and the computation of their solutions ? A (decision) problem on the existence of a solution of length k can be in P but compute this solution can be exponential, nay currently impossible. This is precisely due to non-constructive proof procedure.

http://mathoverflow.net/questions/47954/is-pnp-relevant-to-finding-proofs-of-everyday-mathematical-propositions Lamine 2010-12-02T09:59:17Z 2010-12-02T09:59:17Z

The gap accorded by people between polynomial and exponential time can be justified by the Moore's law. It guesses that computing capacities increase exponentially (this may have a limit due to some silicon proprieties, but uses of other technologies to continue this increase can be expected). If A problem is in P, even if it has a large exponent and constant, it will be easy one day to compute.

http://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48015#48015 Lamine 2010-12-02T09:36:18Z 2010-12-02T09:36:18Z

Indeed ! Should not be confused between &quot;recursive&quot; and &quot;recursively enumerable&quot;. Thanks.

http://mathoverflow.net/questions/47921/discounted-total-reward-vs-average-total-reward/47939#47939 Lamine 2010-12-02T08:25:14Z 2010-12-02T08:25:14Z

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).

http://mathoverflow.net/questions/44677/is-there-mdps-markow-decision-process-which-have-a-non-deterministic-optimal-po/44685#44685 Lamine 2010-11-03T15:35:21Z 2010-11-03T15:35:21Z

Thank you for your answer. So, if a optimal policy exists, it is always deterministic ? If we model a game which has no pure Nash Equilibrium and only a mixed Nash Equilibrium, the policy which optimize the long time reward can not be deterministic (because it would mean that a pure NE corresponding to this policy exists), so can't we say that this policy is a stochastic optimal one for this MDP ? Or It means that there is no optimal policy for a game without pure NE wich is modeled as a MDP ?