Does knowing everything about your environment yield any major shortcuts to finding the optimal policy, in a Markov Decision Process with a very large (finite) number of states?

Mere planning clearly requires less effort than reinforcement learning for smaller state spaces; in many cases we can just calculate the policy or value function from the transition diagram using backward induction (dynamic programming). However, when the state space becomes too large to solve, or perhaps even to represent, are we stuck with the trial-and-error methods of reinforcement learning anyhow, or are there easier algorithms to implement for large scale planning?

  • $\begingroup$ What is there besides trial and error? $\endgroup$ – Neil G Jan 13 '17 at 6:17
  • $\begingroup$ Knowing your environment makes your backups much more efficient since you your estimate of the return usually depends on the future states you will be in. $\endgroup$ – Neil G Jan 13 '17 at 6:18

How human beings make daily decisions, which usually involve huge search spaces? We do abstraction, we think hierarchically, we divide and conquer, we search for a solution guided by heuristics that allow us to focus our search in directions that appear most promising.

I believe to deal with huge search spaces, the planning algorithms should have the same mechanisms mentioned above.

Reinforcement learning is nothing but dynamic programming (sth very basic to planning guys) plus function approximation. If anyone thinks DP+function fitting means strong intelligence that is going to solve complex planning problems, good luck!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.