The Markov Property, Chain, Reward Process and Decision Process
xaviergeerinck.com
xaviergeerinck.com
http://setosa.io/ev/markov-chains/
https://towardsdatascience.com/a-zero-math-introduction-to-m...
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.
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.
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...).
In most other situations you're forced to "wait and see" when you want to learn how a given strategy will turn out. This is not the case if you're dealing with an MDP. If the current state is `s`, the next state is `s'`, and the reward you got for transitioning between the two is `r`, then for a given value function V(.) you can express the temporal-difference error (which is sort of a gradient for the value function) as: δ = r + γ v(s') - v(s) ≈ ∂v(s)
Other formulations of rewards/objectives don't tend to permit such elegant constructions, which is why MDPs are so special (and reinforcement learning so successful).
However I feel like it's a struggle getting that point across, so I'm interested in reading your next post to see how you convey things.
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.
I was thinking Hearts or Spades, which aren't perfect information, but since the whole deck is dealt out, you can (with a lot of memory :-) know what cards are left.
Initially, your state is your hand plus the initial rules (who goes first, which suit is trump, etc depending on what kind of game you're playing). After each player's turn you transition into a new state, which is <<starting hand>> + <<history of cards played>>, so at each point in time the state has all the available information. Obviously this leads to a combinatorially huge state space, because there's O(52!) different possible sequences for a standard deck of cards.
Typically you have to use some sort of approximation architecture because evaluating all different possible responses to a given sequence of cards would both take too long and even if you could do it, the memory requirements would be enormous. See for example DeepStack[0], which uses a neural net to approximate the quality of positions + possible responses (along with other techniques), rather than having a lookup table for what to do in each possible game state.
So you can formulate such games as MDPs, but the question then becomes: is this a useful way to think about it? Sometimes it is, because your approach to the problem scales and so you can throw enough resources (training data, compute power) at it to learn a useful strategy; other times there is a better way of formulating the problem[1].
I have some implementations of reinforcement learning algorithms and code for working with MDPs if you're interested in that sort of thing[2], and of course I highly recommend Rich's book.
---
0. https://www.deepstack.ai/ -- note that it's not really an RL system, but it does illustrate using neural nets to learn complicated functions in a large state space.
1. For example, I am not sure that such an MDP for hearts is well-posed: the convergence results that I'm familiar with rely on the MDP being ergodic and aperiodic, but the suggested construction is obviously periodic.
2. The algorithms: https://github.com/rldotai/rl-algorithms An MDP library: https://github.com/rldotai/mdpy (check out notebooks/example_notebook.ipynb for a basic demo).
In short, a regular MDP models moving from one state to future states with some probability. In a POMDP, we don't know which state we're in, but we have some guesses, i.e. we have a probability distribution over all states. So we model a sequence of taking actions and performing observations, and using those observations to update the probability distribution, so that we can reduce the uncertainty as much as possible.
The typical example is robot navigation, where POMDPs are used extensively. For example, a blind robot starts out somewhere, it doesn't know where, so the probability distribution over all possible locations is uniform. Then it moves north, and discovers that it was successful; this observation modifies the PD to states that are reachable by moving north from previously likely states (conceptually: this will exclude all sorts of corners and dead ends from consideration). Then let's say it tries to drive north once again, but it discovers it bumped into a wall and was unsuccessful. Now the PD gets updated again, based on previous PD and the results of this action (conceptually: we bump the probability of any state that we can drive north to, and hit a dead end or a t-intersection), and so on. As this sequence of actions and observations continues, we hope the probability distribution will collapse to the specific location that we're in, or a small set of guesses.
(This is a narrative description of course; for the nitty gritty details there are many more precise materials on POMDPs! :) )
By the way, this is still a _Markov_ process: the trajectory of _how_ we got to some probability distribution doesn't matter, if those sequences of actions produced the same result they are treated as equivalent per Markov assumption.