Approximate dynamic programming

What Hacker News says

1. verdatelAug 2011
   The theory of multi-armed bandits arises from the study of Markov decision processes (MDP). This field is also closely studied in and related to Stochastic Control and Dynamic Programming. A good book on MDP's is "Markov Decision Processes: Discrete Stochastic Dynamic Programming by Martin Puterman". It's fairly mathematical and is for grad-level learning. An alternative is another superb book "Dynamic Programming and Optimal Control" by Dimitri Bersekas.

   A more accessible book is "Approximate Dynamic Programming" by Warren Powell.

   I'm not sure if you know what a Markov chain is? Very roughly, any kind of data which changes its value (sometimes referred to as "state") and jumps to a new value is a Markov chain. The value that the chain jumps to is determined probabilistically using some distribution over all the states. When there are several Markov chains in parallel and each of them contribute to a certain reward and we are faced with the problem of which Markov chain to "control" or influence.. then it becomes a multi-armed bandit problem. They are not very easy to solve, except when certain simplifying assumptions are made. You can get a good start by looking at some MATLAB code from Prof. Kevin Murphy at UBC : http://www.cs.ubc.ca/~murphyk/Software/MDP/mdp.html

   Show morethread
2. shooSep 2015
   UCB bandit algorithms are quite simple to understand, and the generalisation of them by the UCT algorithm to tree search spaces seems like a pretty clean idea.

   I had a go at using UCT to explore a search space earlier this year (not games, but selecting a good sequence of decisions inside a simulation).

   The problem I ran into with this approach was that the algorithm has no way to generalise or lift experience from one explored state to other similar / unexplored states, and my search space was large. So having to evaluate each state at least once was prohibitive.

   This isn't really a criticism of how well UCT can tackle the problem as framed, but more a criticism of how much better one might be able to do with a bit more structure -- e.g. perhaps with the addition of some kind of similarity metric between states, along with some bounds or assumptions on how the values of "similar" states should relate to each other.

   It seems like combining some machine learning / statistical / approximation techniques to approximate the true state->value function with a UCT-like approach to guide exploration could be very effective for the right problem, but getting it to work well might be more of an art than a science.

   If anyone has any pointers to reading about this kind of thing, I'd be most grateful! I have previously read about "approximate dynamic programming" techniques, e.g. [1]

   [1] http://castlelab.princeton.edu/Papers/Powell-NRLWhat%20you%2...

   Show morethread