Informed and robust decision making in the face of uncertainty is critical for robots that perform physical tasks alongside people. We formulate this as a Bayesian Reinforcement Learning problem over latent Markov Decision Processes (MDPs). While Bayes-optimality is theoretically the gold standard, existing algorithms do not scale well to continuous state and action spaces. We propose a scalable solution that builds on the following insight: in the absence of uncertainty, each latent MDP is easier to solve. We split the challenge into two simpler components. First, we obtain an ensemble of clairvoyant experts and fuse their advice to compute a baseline policy. Second, we train a Bayesian residual policy to improve upon the ensemble's recommendation and learn to reduce uncertainty. Our algorithm, Bayesian Residual Policy Optimization (BRPO), imports the scalability of policy gradient methods as well as the initialization from prior models. BRPO significantly improves the ensemble of experts and drastically outperforms existing adaptive RL methods. Robots operating in the real world must resolve uncertainty on a daily basis. Often times, a robot is uncertain about how the world around it evolves. For example, a self-driving car must drive safely around unpredictable actors like pedestrians and bicyclists. A robot arm must reason about occluded objects when reaching into a cluttered shelf. On other occasions, a robot is uncertain about the task it needs to perform. An assistive home robot must infer a human's intended goal by interacting with them. Both examples of uncertainty require simultaneous inference and decision making, which can be framed as Bayesian reinforcement learning (RL) over latent Markov Decision Processes (MDPs). Agents do not know which latent MDP they are interacting with, preventing them from acting optimally with respect to that MDP. Instead, Bayes optimality only requires that agents be optimal with respect to their current uncertainty over latent MDPs. The Bayesian RL problem can be viewed as solving a large continuous belief MDP, which is computationally infeasible to solve directly (Ghavamzadeh et al., 2015) . We build upon a simple yet recurring observation (Osband et al., 2013; Kahn et al., 2017; Choudhury et al., 2018) : while solving the belief MDP may be hard, solving individual latent MDPs is much more tractable. Given exact predictions for all actors, the self-driving car can invoke a motion planner to find a collision-free path. The robot arm can employ an optimal controller to dexterously retrieve an object given exact knowledge of all objects. Once the human's intended goal is discovered, the robot can provide assistance. Hence, the overall challenge boils down to solving two (perhaps) simpler sub-challenges: solving the latent MDPs and combining these solutions to solve the belief MDP. Let's assume we can approximately solve the latent MDPs to create an ensemble of policies as shown in Figure 1 . We can think of these policies as clairvoyant experts, i.e., experts that think they know the latent MDP and offer advice accordingly. A reasonable strategy is to weigh these policy proposals by the belief and combine them into a single recommendation to the agent. While this recommendation is good for some regimes, it can be misleading when uncertainty is high. The onus then is on the agent to disregard the recommendation and explore the space effectively to collapse uncertainty. This leads to our key insight. Learning Bayesian corrections on top of clairvoyant experts is a scalable strategy for solving complex reinforcement learning problems. While learning corrections echoes the philosophy of boosting (Freund & Schapire, 1999) , our agent goes one step beyond: it learns to take uncertainty-reducing actions that highlight which expert to boost. Our algorithm, Bayesian Residual Policy Optimization (BRPO), augments a belief-space batch policy optimization algorithm (Lee et al., 2019) with clairvoyant experts (Figure 1 ). The agent observes the experts' recommendation, belief over the latent MDPs, and state. It returns a correction over the expert proposal, including uncertainty-reducing sensing actions that experts never need to take. Our key contribution is the following: • We propose a scalable Bayesian RL algorithm to solve problems with complex latent rewards and dynamics. • We experimentally demonstrate that BRPO outperforms both the ensemble of experts and existing adaptive RL algorithms. In the real world, robots must deal with uncertainty, either due to complex latent dynamics or task specifics. Because uncertainty is an inherent part of these tasks, we can at best aim for optimality under uncertainty, i.e., Bayes optimality. Existing BRL algorithms or POMDP solvers do not scale well to problems with complex latent MDPs or a large (continuous) set of MDPs. We decompose BRL problems into two parts: solving each latent MDP and being Bayesian over the solutions. Our algorithm, Bayesian Residual Policy Optimization, operates on the residual belief-MDP space given an ensemble of experts. BRPO focuses on learning to explore, relying on the experts for exploitation. BRPO is capable of solving complex problems, outperforming existing BRL algorithms and improving on the original ensemble of experts. Although out of scope for this work, a few key challenges remain. First is an efficient construction of an ensemble of experts, which becomes particularly important for continuous latent spaces with infinitely many MDPs. Infinitely many MDPs do not necessarily require infinite experts, as many may converge to similar policies. An important future direction is subdividing the latent space and computing a qualitatively diverse set of policies (Liu et al., 2016) . Another challenge is developing an efficient Bayes filter, which is an active research area. In certain occasions, the dynamics of the latent MDPs may not be accessible, which would require a learned Bayes filter. Combined with a tractable, efficient Bayes filter and an efficiently computed set of experts, we believe that BRPO will provide an even more scalable solution for BRL problems. As discussed in Section 3.1, Bayesian reinforcement learning and posterior sampling address quite different problems. We present a toy problem to highlight the distinction between them. Consider a deterministic tree-like MDP ( Figure 6 ). Reward is received only at the terminal leaf states: one leaf contains a pot of gold (R = 100) and all others contain a dangerous tiger (R = −10). All non-leaf states have two actions, go left (L) and go right (R). The start state additionally has a sense action (S), which is costly (R = −0.1) but reveals the exact location of the pot of gold. Both algorithms are initialized with a uniform prior over the N = 2 d possible MDPs (one for each possible location of the pot of gold). To contrast the performance of the Bayes-optimal policy and posterior sampling, we consider the multi-episode setting where the agent repeatedly interacts with the same MDP. The MDP is sampled once from the uniform prior, and agents interact with it for T episodes. This is the setting typically considered by posterior sampling (PSRL) (Osband et al., 2013) . Before each episode, PSRL samples an MDP from its posterior over MDPs, computes the optimal policy, and executes it. After each episode, it updates the posterior and repeats. Sampling from the posterior determinizes the underlying latent parameter. As a result, PSRL will never produce sensing actions to reduce uncertainty about that parameter because the sampled MDP has no uncertainty. More concretely, the optimal policy for each tree MDP is to navigate directly to the gold without sensing; PSRL will never take the sense action. Thus, PSRL makes an average of N −1 2 mistakes before sampling the correct pot of gold location and the cumulative reward over T episodes is In the first episode, the Bayes-optimal first action is to sense. All subsequent actions in this first episode navigate toward the pot of gold, for an episode reward of −0.1 + 100. In the subsequent T − 1 episodes, the Bayes-optimal policy navigates directly toward the goal without needing to sense, for a cumulative reward of 100T − 0.1. The performance gap between the Bayes-optimal policy and posterior sampling grows exponentially with depth of the tree d. Practically, a naïve policy gradient algorithm (like BPO) would struggle to learn the Bayes-optimal policy: it would need to learn to both sense and navigate the tree to the sensed goal. BRPO can take advantage of the set of experts, which each navigate to their designated leaf. During training, the BRPO agent only needs to learn to balance sensing with navigation. As mentioned in Section 3.1, PSRL is an online learning algorithm and is designed to address domains where the posterior naturally updates as a result of multiple episodes of interactions with the latent MDP. PSRL is more focused on improving the performance over episodes, which is different from the average performance or zero-shot performance that we consider in this work.
We propose a scalable Bayesian Reinforcement Learning algorithm that learns a Bayesian correction over an ensemble of clairvoyant experts to solve problems with complex latent rewards and dynamics. This paper considers Bayesian Reinforcement Learning problem over latent Markov Decision Processes (MDPs) by making decisions with experts. In this paper, the authors motivate and propose a learning algorithm, called Bayesian Residual Policy Optimization (BRPO), for Bayesian reinforcement learning problems.