8 ms·

The Markov Property, Chain, Reward Process and Decision Process

161 points by thebillkidy 8y ago

bhaavan 8y ago
Doesn't the typo "3th" annoy anyone when reading that article?
- gautamdivgi 8y ago
  No it doesn’t.
  - thebillkidy 8y ago
    also fixed it to "third" :) keep the feedback coming
lossolo 8y 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.
- thebillkidy 8y 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 8y ago
Here are a couple of other Markov Chain articles that are worthwhile: http://setosa.io/ev/markov-chains/ http://setosa.io/ev/markov-chains/ https://towardsdatascience.com/a-zero-math-introduction-to-markov-chain-monte-carlo-methods-dcba889e0c50 https://towardsdatascience.com/a-zero-math-introduction-to-m...
- baxtr 8y ago
  These are great! Thank you!!
TheCabin 8y 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.
- thebillkidy 8y 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 8y 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?
- thebillkidy 8y ago
  You are completely right! Thanks for spotting this! :)
  - thebillkidy 8y ago
    Update: Fixed it, the caching might need to expire on your side though (ctrl + shift + r should do the trick)
platz 8y 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 8y 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.
- thebillkidy 8y ago
  Hi Platz, MDPs are actually the basis that you should know towards creating the Bellman equations
- clickok 8y 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 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-History/biographies/jerry-lettvin/creative-writing/gallows-songs https://sites.google.com/site/lettvingroup/Home/Projects-His...).
antman 8y ago
Nice work! Any good pages for pomdp?

161 points by thebillkidy 8y ago

bhaavan 8y ago

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

gautamdivgi 8y ago
No it doesn’t.
- thebillkidy 8y ago
  also fixed it to "third" :) keep the feedback coming

lossolo 8y 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.

thebillkidy 8y 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 8y ago

Here are a couple of other Markov Chain articles that are worthwhile: http://setosa.io/ev/markov-chains/ http://setosa.io/ev/markov-chains/ https://towardsdatascience.com/a-zero-math-introduction-to-markov-chain-monte-carlo-methods-dcba889e0c50 https://towardsdatascience.com/a-zero-math-introduction-to-m...

baxtr 8y ago
These are great! Thank you!!

TheCabin 8y 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.

thebillkidy 8y 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 8y 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?

thebillkidy 8y ago
You are completely right! Thanks for spotting this! :)
- thebillkidy 8y ago
  Update: Fixed it, the caching might need to expire on your side though (ctrl + shift + r should do the trick)

platz 8y 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 8y 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.
thebillkidy 8y ago
Hi Platz, MDPs are actually the basis that you should know towards creating the Bellman equations
clickok 8y 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 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-History/biographies/jerry-lettvin/creative-writing/gallows-songs https://sites.google.com/site/lettvingroup/Home/Projects-His...).

antman 8y ago

Nice work! Any good pages for pomdp?