In this paper, we consider learning scenarios where the learned model is evaluated under an unknown test distribution which potentially differs from the training distribution (i.e. distribution shift). The learner has access to a family of weight functions such that the test distribution is a reweighting of the training distribution under one of these functions, a setting typically studied under the name of Distributionally Robust Optimization (DRO). We consider the problem of deriving regret bounds in the classical learning theory setting, and require that the resulting regret bounds hold uniformly for all potential test distributions. We show that the DRO formulation does not guarantee uniformly small regret under distribution shift. We instead propose an alternative method called Minimax Regret Optimization (MRO), and show that under suitable conditions this method achieves uniformly low regret across all test distributions. We also adapt our technique to have stronger guarantees when the test distributions are heterogeneous in their similarity to the training data. Given the widespead optimization of worst case risks in current approaches to robust machine learning, we believe that MRO can be a strong alternative to address distribution shift scenarios.

We introduce L0Learn: an open-source package for sparse regression and classification using L0 regularization. L0Learn implements scalable, approximate algorithms, based on coordinate descent and local combinatorial optimization. The package is built using C++ and has a user-friendly R interface. Our experiments indicate that L0Learn can scale to problems with millions of features, achieving competitive run times with state-of-the-art sparse learning packages. L0Learn is available on both CRAN and GitHub.

We consider the combinatorial bandits problem with semi-bandit feedback under finite sampling budget constraints, in which the learner can carry out its action only for a limited number of times specified by an overall budget. The action is to choose a set of arms, whereupon feedback for each arm in the chosen set is received. Unlike existing works, we study this problem in a non-stochastic setting with subset-dependent feedback, i.e., the semi-bandit feedback received could be generated by an oblivious adversary and also might depend on the chosen set of arms. In addition, we consider a general feedback scenario covering both the numerical-based as well as preference-based case and introduce a sound theoretical framework for this setting guaranteeing sensible notions of optimal arms, which a learner seeks to find. We suggest a generic algorithm suitable to cover the full spectrum of conceivable arm elimination strategies from aggressive to conservative. Theoretical questions about the sufficient and necessary budget of the algorithm to find the best arm are answered and complemented by deriving lower bounds for any learning algorithm for this problem scenario.

In his 1997 paper on solving Rubik's Cube optimally using IDA* and pattern database heuristics (PDBs), Rich Korf conjectured that there was an inverse relationship between the size of a PDB and the amount of time required for IDA* to solve a problem instance on average. In the current paper, I examine the implications of this relationship, in particular how it limits the ability of abstraction-based heuristic methods, such as PDBs, to scale to larger problems. My overall conclusion is that abstraction will play an important, but auxiliary role in heuristic search systems of the future, in contrast to the primary role it played in Korf's Rubik's Cube work and in much work since.

Pattern databases (PDBs) have been widely used as heuristics for many types of search spaces,but they have always been computed so as to fit in the main memory of the machine usingthe PDB. This paper studies the how external-memory PDBs can be used. It presentsresults of both using hard disk drives and solid-state drives directly to access the data, and of justloading a portion of the PDB into RAM. For the time being, all of these approaches are inferiorto building the largest PDB that fits into RAM.

Recent work has raised the challenge of efficient automated troubleshooting in domains where repairing a set of components in a single repair action is cheaper than repairing each of them separately. This corresponds to cases where there is a non-negligible overhead to initiating a repair action and to testing the system after a repair action. The problem can be formalized as a combinatorial search problem, propose a new objective function to optimize, and investigate several search frameworks to solve it. The resulting search space is not monotone, but we are able to devise an admissible heuristic for it that enables solving it optimally in some cases with A*.

Bidirectional search algorithms interleave a search forward from the start state (start) and a search backward (i.e. using reverse operators) from the goal state (goal). We say that the two searches "meet in the middle" if neither search expands a node whose g-value (in the given direction) exceeds C*/2, where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM's priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe's correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

Many AI systems, such as robots, must plan under time constraints. The most popular search approach applied in robotics so far is anytime search, in which the algorithm quickly finds a suboptimal plan, and then continues to find better and better plans as time passes, until eventually converging on an optimal plan. However, the time until the first plan is returned is not controllable, so such methods inherently involve idling the system's operation before real' execution can begin. Real-time search methods provide hard real-time bounds on action selection time, yet to our knowledge, they have not yet been demonstrated for robotic systems. In this work, we compare anytime and real-time heuristic search methods in their ability to allow agents to achieve goals quickly.Our results suggest that real-time search is more broadly applicable and often achieves goals faster than anytime search, while anytime search finds shorter plans and does not suffer from dead-ends.

Heuristic search is a core area of Artificial Intelligence with applications to planning, scheduling and game playing. Real-time heuristic search applies to search problems where plan execution needs to start before a complete solution can be computed. Since the inception of real-time heuristic search in the early 1990s a great number of algorithms have been proposed and evaluated. In this paper we break them down into building blocks and conduct a search in the space of such building blocks. Even simple tabulated and iterative searches find new real-time heuristic search algorithms outperforming manually crafted contemporary algorithms.

Machine teaching (MT) studies the task of designing a training set. Specifically, given a learner (e.g., an artificial neural network or a human) and a target model, a teacher aims to create a training set which results in the target model being learned. MT applications include optimal education design for human learners and computer security where adversaries aim to attack learning-based systems. In this work, we formulate pool-based MT as a state space search problem. We discuss the properties and challenges of the resulting problem and highlight opportunities for novel search techniques. In our preliminary study we use a beam search approach, and find that training and evaluating empirical risk of models dominate the run time of the search. Toward the goal of better search techniques for future work, we develop optimizations ranging from implementation details for specific learners to algorithm changes applicable to general blackbox learners. We conclude with a discussion of open problems and research directions.