We consider reinforcement learning and bandit structured prediction problems with very sparse loss feedback: only at the end of an episode. We introduce a novel algorithm, RESIDUAL LOSS PREDICTION (RESLOPE), that solves such problems by automatically learning an internal representation of a denser reward function. RESLOPE operates as a reduction to contextual bandits, using its learned loss representation to solve the credit assignment problem, and a contextual bandit oracle to trade-off exploration and exploitation. RESLOPE enjoys a no-regret reduction-style theoretical guarantee and outperforms state of the art reinforcement learning algorithms in both MDP environments and bandit structured prediction settings. Current state of the art learning-based systems require enormous, costly datasets on which to train supervised models. To progress beyond this requirement, we need learning systems that can interact with their environments, collect feedback (a loss or reward), and improve continually over time. In most real-world settings, such feedback is sparse and delayed: most decisions made by the system will not immediately lead to feedback. Any sort of interactive system like this will face at least two challenges: the credit assignment problem (which decision(s) did the system make that led to the good/bad feedback? ); and the exploration/exploitation problem (in order to learn, the system must try new things, but these could be bad).We consider the question of how to learn in an extremely sparse feedback setting: the environment operates episodically, and the only feedback comes at the end of the episode, with no incremental feedback to guide learning. This setting naturally arises in many classic reinforcement learning problems ( §4): a barista robot will only get feedback from a customer after their cappuccino is finished 1 . It also arises in the context of bandit structured prediction BID41 BID9 ( §2.2), where a structured prediction system must produce a single output (e.g., translation) and observes only a scalar loss.We introduce a novel reinforcement learning algorithm, RESIDUAL LOSS PREDICTION (RESLOPE) ( § 3), which aims to learn effective representations of the loss signal. By effective we mean effective in terms of credit assignment. Intuitively, RESLOPE attempts to learn a decomposition of the episodic loss into a sum of per-time-step losses. This process is akin to how a person solving a task might realize before the task is complete when and where they are likely to have made suboptimal choices. In RESLOPE, the per-step loss estimates are conditioned on all the information available up to the current point in time, allowing it to learn a highly non-linear representation for the episodic loss (assuming the policy class is sufficiently complex; in practice, we use recurrent neural network policies). When the system receives the final episodic loss, it uses the difference between the observed loss and the cumulative predicted loss to update its parameters.Algorithmically, RESLOPE operates as a reduction ( §3.3) to contextual bandits (Langford & Zhang, 2008) , allowing the bandit algorithm to handle exploration/exploitation and focusing only on the credit assignment problem. RESIDUAL LOSS PREDICTION is theoretically motivated by the need for variance reduction techniques when estimating counterfactual costs (Dudík et al., 2014) and enjoys a no-regret bound ( §3.3) when the underlying bandit algorithm is no-regret. Experimentally, we show the efficacy of RESLOPE on four benchmark reinforcement problems and three bandit structured prediction problems ( § 5.1), comparing to several reinforcement learning algorithms: Reinforce, Proximal Policy Optimization and Advantage Actor-Critic. RESIDUAL LOSS PREDICTION builds most directly on the bandit learning to search frameworks LOLS BID9 and BLS BID40 . The "bandit" version of LOLS was analyzed theoretically but not empirically in the original paper; BID40 found that it failed to learn empirically.They addressed this by requiring additional feedback from the user, which worked well empirically but did not enjoy any theoretical guarantees. RESLOPE achieves the best of both worlds: a strong regret guarantee, good empirical performance, and no need for additional feedback. The key ingredient for making this work is using the residual loss structure together with strong base contextual bandit learning algorithms.A number of recent algorithms have updated "classic" learning to search papers with deep learning underpinnings BID48 BID21 . These aim to incorporate sequencelevel global loss function to mitigate the mismatch between training and test time discrepancies, but only apply in the fully supervised setting. Mixing of supervised learning and reinforcement signals has become more popular in structured prediction recently, generally to do a better job of tuning for a task-specific loss using either Reinforce BID35 or Actor-Critic BID2 . The bandit variant of the structured prediction problem was studied by BID41 , who proposed a reinforce method for optimizing different structured prediction models under bandit feedback in a log-linear structured prediction model.A standard technique for dealing with sparse and episodic reward signals is reward shaping BID31 : supplying additional rewards to a learning agent to guide its learning process, beyond those supplied by the underlying environment. Typical reward shaping is hand-engineered; RESLOPE essentially learns a good task-specific reward shaping automatically. The most successful baseline approach we found is Proximal Policy Optimization (PPO, BID39 ), a variant of Trust Region Policy Optimization (TRPO, BID38 ) that is more practical.Experimentally we have seen RESLOPE to typically learn more quickly than PPO. Theoretically both have useful guarantees of a rather incomparable nature.Since RESLOPE operates as a reduction to a contextual bandit oracle, this allows it to continually improve as better contextual bandit algorithms become available, for instance work of Syrgkanis et al. (2016b) and BID0 . Although RESLOPE is quite effective, there are a number of shortcomings that need to be addressed in future work. For example, the bootstrap sampling algorithm is prohibitive in terms of both memory and time efficiency. One approach for tackling this would be using the amortized bootstrap approach by BID27 , which uses amortized inference in conjunction with implicit models to approximate the bootstrap distribution over model parameters. There is also a question of whether the reduction to contextual bandits creates "reasonable" contextual bandit problems in conjunction with RNNs. While some contextual bandit algorithms assume strong convexity or linearity, the ones we employ operate on arbitrary policy classes, provided a good cost-sensitive learner exists. The degree to which this is true will vary by neural network architecture, and what can be guaranteed (e.g., no regret full-information online neural learning). A more significant problem in the multi-deviation setting is that as RESLOPE learns, the residual costs will change, leading to a shifting distribution of costs; in principle this could be addressed using CB algorithms that work in adversarial settings BID43 BID16 , but largely remains an open challenge. RESLOPE is currently designed for discrete action spaces. Extension to continuous action spaces BID22 BID23 remains an open problem.
We present a novel algorithm for solving reinforcement learning and bandit structured prediction problems with very sparse loss feedback.
{"src": "scitldr-AIC_train", "paper_id": "HJNMYceCW"}