Learning to Search via Retrospective Imitation
We study the problem of learning a good search policy for combinatorial search spaces. We propose retrospective imitation learning, which, after initial training by an expert, improves itself by learning from \textit{retrospective inspections} of its own roll-outs. That is, when the policy eventually reaches a feasible solution in a combinatorial search tree after making mistakes and backtracks, it retrospectively constructs an improved search trace to the solution by removing backtracks, which is then used to further train the policy. A key feature of our approach is that it can iteratively scale up, or transfer, to larger problem sizes than those solved by the initial expert demonstrations, thus dramatically expanding its applicability beyond that of conventional imitation learning. We showcase the effectiveness of our approach on a range of tasks, including synthetic maze solving and combinatorial problems expressed as integer programs.
Code (0)
등록된 구현이 없습니다.
Tasks
Imitation LearningSimilar Papers 제목 키워드 기반
Transdisciplinary AI Observatory -- Retrospective Analyses and Future-Oriented Contradistinctions
In the last years, AI safety gained international recognition in the light of heterogeneous safety-critical and ethical issues that risk overshadowing the broad beneficial impacts of AI. In this context, the implementati…
counterfactualDescriptiveRetrospective Causal Inference with Machine Learning Ensembles: An Application to Anti-Recidivism Policies in Colombia
We present new methods to estimate causal effects retrospectively from micro data with the assistance of a machine learning ensemble. This approach overcomes two important limitations in conventional methods like regress…
BIG-bench Machine LearningCausal InferenceregressionReinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories
Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILPs by con…
Imitation Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Clinical Trial Active Learning
This paper presents a novel approach to active learning that takes into account the non-independent and identically distributed (non-i.i.d.) structure of a clinical trial setting. There exists two types of clinical trial…
Active LearningTemporal Leakage in Search-Engine Date-Filtered Web Retrieval: A Retrospective Forecasting Case Study
Search-engine date filters are widely used to enforce pre-cutoff retrieval in retrospective evaluations of search-augmented forecasters. We show this approach is unreliable across two major search engines: auditing Googl…