{"id":13762683,"date":"2020-07-21T10:59:11","date_gmt":"2020-07-21T16:59:11","guid":{"rendered":"http:\/\/hunch.net\/?p=13762683"},"modified":"2020-07-21T10:59:11","modified_gmt":"2020-07-21T16:59:11","slug":"homer-provable-exploration-in-reinforcement-learning","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=13762683","title":{"rendered":"HOMER: Provable Exploration in Reinforcement Learning"},"content":{"rendered":"\n

Last week at ICML 2020, Mikael Henaff<\/a>, Akshay Krishnamurthy<\/a>, John Langford<\/a> and I had a paper on a new reinforcement learning (RL) algorithm that solves three key problems in RL: (i) global exploration, (ii) decoding latent dynamics, and (iii) optimizing a given reward function. Our ICML poster is here<\/a>.<\/p>\n\n\n\n

The paper is a bit mathematically heavy in nature so this post is an attempt to distill the key findings. We will also be following up soon with a new codebase release (more on it later).<\/p>\n\n\n\n

Rich-observation RL landscape<\/strong><\/h1>\n\n\n\n

Consider the combination lock problem shown below. The agent starts in the state s1a<\/sub> or s1b<\/sub> with equal probability. After taking h-1 actions, the agent will be in either state sha<\/sub>, shb<\/sub>, or shc<\/sub>. The agent can take 10 different actions. The agent observes a high-dimensional observation (focus circle) instead of the underlying state which is latent. There is a big treasure chest that one can get after taking 100 actions. We view the states with subscript \u201ca\u201d or \u201cb\u201d as \u201cgood states<\/em>\u201d and one with subscript \u201cc\u201d as \u201cbad states<\/em>\u201d. You can reach the treasure chest at the end only if you remain in good states. If you reach any bad state, then you can never make it to the treasure chest.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The environment makes it difficult to reach the big treasure chest in three ways. First, the environmental dynamics are such that if you are in good states, then only 1 out of 10 possible actions will let you reach the two good states at the next time step with equal probability (the good action changes from state to state). Every other action in good states and all actions in bad states put you into bad states at the next time step, from which it is impossible to recover. Second, it misleads myopic agents by giving a small bonus for transitioning from a good state to a bad state (small treasure chest). This means that a locally optimal policy is transitions to one of the bad states as quickly as possible. Third, the agent never directly observes which state it is in. Instead, it receives a high-dimensional, noisy observation from which it must decode the true underlying state.<\/p>\n\n\n\n

It is easy to see that if we take actions uniformly at random, then the probability of reaching the big treasure chest at the end is 1\/10100<\/sup>. The number 10100<\/sup> is called Googol<\/a> and is larger than the current estimate of number of elementary particles in the universe. Furthermore, since transitions are stochastic one can show that no fixed sequence of actions performs well either.<\/p>\n\n\n\n

A key aspect of the rich-observation setting is that the agent receives observations instead of latent state. The observations are stochastically sampled from an infinitely<\/em> large space conditioned on the state. However, observations are rich-enough to enable decoding<\/em> the latent state which generates them.<\/p>\n\n\n\n

What does provable RL mean?<\/strong><\/h1>\n\n\n\n

A provable RL algorithm means that for any given numbers e<\/strong>, d<\/strong> in (0, 1); we can learn an e<\/em><\/strong>-optimal policy<\/em> with probability at least 1-d<\/strong> using a number of episodes which are polynomial in relevant quantities (state size, horizon, action space, 1\/e, 1\/d, etc.). By e<\/strong>-optimal policy we mean a policy whose value (expected total return) is at most e<\/strong> less than the optimal return.<\/p>\n\n\n\n

Thus, a provable RL algorithm is capable of learning a close to optimal policy with high probability (where the word high and close can be made arbitrarily more refined), provided the assumptions it makes are satisfied.<\/p>\n\n\n\n

Why should I care if my algorithm is provable?<\/strong><\/h1>\n\n\n\n

There are two main advantages of being able to show your algorithm is provable:<\/p>\n\n\n\n

  1. We can only test an algorithm on a finite number of environments (in practice somewhere between 1 and 20). Without guarantees, we don\u2019t know how they will behave in a new environment. This matters especially if failure in a new environment can result in high real-world costs (e.g., in health or financial domains).<\/li>
  2. If a provable algorithm fails to consistently give the desired result, this can be attributed to failure of at least one of its assumptions. A developer can then look at the assumptions and try to determine which ones are violated, and either intervene to fix them or determine that the algorithm is not appropriate for the problem.<\/li><\/ol>\n\n\n\n

    HOMER<\/strong><\/h1>\n\n\n\n

    Our algorithm addresses what is known as the Block MDP<\/a> setting. In this setting, a small number of discrete states generates a potentially infinite number of high dimensional observations.<\/p>\n\n\n\n

    For each time step, HOMER learns a state decoder function, and a set of exploration policies. The state decoder maps high-dimensional observations to a small set of possible latent states, while the exploration policies map observations to actions which will lead the agent to each of the latent states. We describe HOMER below.<\/p>\n\n\n\n