The Markov Property, Chain, Reward Process and Decision Process

https://xaviergeerinck.com/markov-property-chain-reward-decision

by thebillkidy • 8 years ago

161 25 8 years ago

xaviergeerinck.com

bhaavan• 8 years ago

Doesn't the typo "3th" annoy anyone when reading that article?

gautamdivgi• 8 years ago

No it doesn’t.

thebillkidy7• 8 years ago

also fixed it to "third" :) keep the feedback coming

lossolo• 8 years ago

Xavier works on enabling everyone to construct products that make a life changing impact on world scale.

I would remove/change that sentence if I were you. I suppose it was made to make what you do look impactful and serious but I have exact opposite impression after reading it.

thebillkidy7• 8 years ago

Hi Lossolo, thanks a lot for this feedback, I took it into account and refactored this sentence a bit :) (deploy will be done in +-2min)

melling• 8 years ago

Here are a couple of other Markov Chain articles that are worthwhile:

http://setosa.io/ev/markov-chains/

https://towardsdatascience.com/a-zero-math-introduction-to-m...

baxtr• 8 years ago

These are great! Thank you!!

TheCabin• 8 years ago

For my taste, the article is a bit too high-level to build a meaningful intuition. I think a more complex example would be beneficial.

thebillkidy7• 8 years ago

Thanks a lot for your feedback! Currently I am working on the high-level definitions of Reinforcement Learning, so that i can build on that to go deeper in the more advanced ones. I'd like to have a series that explains the OpenAI examples :)

glitchc• 8 years ago

Hi Xavier, in the discount factor equation, shouldn't the last term of the expansion be gamma^n.Rn instead of gamma^2.Rn? Or am I missing something?

thebillkidy7• 8 years ago

You are completely right! Thanks for spotting this! :)

thebillkidy7• 8 years ago

Update: Fixed it, the caching might need to expire on your side though (ctrl + shift + r should do the trick)

platz2• 8 years ago

there is a lot of info out there about markov chains, but very little about markov decision processes (MDP).

How popular are MDP? What are their strengths? weaknesses?

Is there really a connection between MDP and reinforcement learning as the author claims, as I've not heard this connection before?

This is a very welcome article.

pilooch• 8 years ago

MDPs are the core holistic framework for decision under uncertainty, especially pomdps and dec-pomdps. That and the various forms of the Bellman equation are with your attention. RL is a model free MDP.

thebillkidy7• 8 years ago

Hi Platz, MDPs are actually the basis that you should know towards creating the Bellman equations

clickok3• 8 years ago

Consider reading "Reinforcement Learning, an Introduction" by Rich Sutton[0]. It is very accessible (and probably the most used textbook in the field), and goes into detail about the connection between RL and MDPs.

If you want a high-level answer right now about how the two are related: reinforcement learning focuses on predicting or maximizing the discounted sum of rewards, G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + ... which is called the return Crucially, the process generating the rewards (the environment) is assumed to be memoryless[1]. So we can reformulate the return as a recursive equation: G_{t} = R_{t+1} + γ G_{t+1}, since the return from "t+1" doesn't depend on the reward you got from the previous time step ("R_{t+1}").

This in turn allows you to define Bellman equations (which define optimal solutions to the problem of maximizing return, which is what you want to do). More generally assuming the problem is Markovian makes things substantially easier to reason about, because you don't have to worry about complex histories leading up to the agent's arrival in a state.

While it's honestly a pretty strong assumption, it's one that we make across many fields and particularly in RL. It's actually not too inaccurate; for example most games are Markovian (or close), and in physical problems (e.g. robot locomotion) if you've got position+velocity then controlling the robot can be viewed as a (continuous-time) MDP.

The weaknesses are obvious: not every environment is Markovian, sometimes there is long-term dependence on the past. For example, translating prose or poetry in such a way that preserves the point across is very tough[2], not really something you can formulate as an MDP. Other times, the weaknesses are easier to overcome (think of a poker game, where you can combine the present state information with the betting patterns from the past; this augmented state should be able to tell you everything you need to know).

---

0. http://incompleteideas.net/book/bookdraft2017nov5.pdf

1. Another way of phrasing this is that each state provides all the useful information, and knowing about previous states does not tell you anything new about the environment. Think of perfect information games, like Chess. It doesn't really matter how you got into a particular position, just the moves you make from there.

2. Compare the poetry translations of Jerry Lettvin with what you'd get using existing translation software (https://sites.google.com/site/lettvingroup/Home/Projects-His...).

thebillkidy7• 8 years ago

Thanks for this! I think you actually summarized the Bellman equations very well! This gave me some ideas for future blog posts on how to make it more clearer for everyone to understand it better :) most likely the next one is about Bellman equations ;)

chris_st2• 8 years ago

Wow, what a great answer -- thanks!

I have a question -- in a card game, it appears that knowing which cards have been played is important (or can help, anyway). This seems to violate the idea of being memoryless.

Can you "cheat" and make reason on the cards left instead? Thanks for any clues.

antman• 8 years ago

Nice work! Any good pages for pomdp?

The Markov Property, Chain, Reward Process and Decision Process

Related Stories