More Like this

1. Rapid Discrete Optimization via Simulation with Gaussian Markov Random Fields

   https://doi.org/10.1287/ijoc.2020.0971  

   Semelhago, Mark; Nelson, Barry L.; Song, Eunhye; Wächter, Andreas (July 2021, INFORMS Journal on Computing)

   Inference-based optimization via simulation, which substitutes Gaussian process (GP) learning for the structural properties exploited in mathematical programming, is a powerful paradigm that has been shown to be remarkably effective in problems of modest feasible-region size and decision-variable dimension. The limitation to “modest” problems is a result of the computational overhead and numerical challenges encountered in computing the GP conditional (posterior) distribution on each iteration. In this paper, we substantially expand the size of discrete-decision-variable optimization-via-simulation problems that can be attacked in this way by exploiting a particular GP—discrete Gaussian Markov random fields—and carefully tailored computational methods. The result is the rapid Gaussian Markov Improvement Algorithm (rGMIA), an algorithm that delivers both a global convergence guarantee and finite-sample optimality-gap inference for significantly larger problems. Between infrequent evaluations of the global conditional distribution, rGMIA applies the full power of GP learning to rapidly search smaller sets of promising feasible solutions that need not be spatially close. We carefully document the computational savings via complexity analysis and an extensive empirical study. Summary of Contribution: The broad topic of the paper is optimization via simulation, which means optimizing some performance measure of a system that may only be estimated by executing a stochastic, discrete-event simulation. Stochastic simulation is a core topic and method of operations research. The focus of this paper is on significantly speeding-up the computations underlying an existing method that is based on Gaussian process learning, where the underlying Gaussian process is a discrete Gaussian Markov Random Field. This speed-up is accomplished by employing smart computational linear algebra, state-of-the-art algorithms, and a careful divide-and-conquer evaluation strategy. Problems of significantly greater size than any other existing algorithm with similar guarantees can solve are solved as illustrations. 

   more » « less
2. SEPARATING THE WORLD AND EGO MODELS FOR SELF-DRIVING

   Alfredo Canziani, Nicolas Carion (April 2022, ICLR 2022 workshop on Generalizable Policy Learning in the Physical World. 2022.)

   Training self-driving systems to be robust to the long-tail of driving scenarios is a critical problem. Model-based approaches leverage simulation to emulate a wide range of scenarios without putting users at risk in the real world. One promising path to faithful simulation is to train a forward model of the world to predict the future states of both the environment and the ego-vehicle given past states and a sequence of actions. In this paper, we argue that it is beneficial to model the state of the ego-vehicle, which often has simple, predictable and deterministic behavior, separately from the rest of the environment, which is much more complex and highly multimodal. We propose to model the ego-vehicle using a simple and differentiable kinematic model, while training a stochastic convolutional forward model on raster representations of the state to predict the behavior of the rest of the environment. We explore several configurations of such decoupled models, and evaluate their performance both with Model Predictive Control (MPC) and direct policy learning. We test our methods on the task of highway driving and demonstrate lower crash rates and better stability. The code is available at https://github.com/vladisai/pytorch-PPUU/tree/ICLR2022. 

   more » « less
3. One for All: Simultaneous Metric and Preference Learning over Multiple Users

   Canal, Gregory; Mason, Blake; Vinayak, Ramya Korlakai; Nowak, Robert (November 2022, Advances in Neural Information Processing Systems)

   This paper investigates simultaneous preference and metric learning from a crowd of respondents. A set of items represented by d -dimensional feature vectors and paired comparisons of the form item i is preferable to item j '' made by each user is given. Our model jointly learns a distance metric that characterizes the crowd's general measure of item similarities along with a latent ideal point for each user reflecting their individual preferences. This model has the flexibility to capture individual preferences, while enjoying a metric learning sample cost that is amortized over the crowd. We first study this problem in a noiseless, continuous response setting (i.e., responses equal to differences of item distances) to understand the fundamental limits of learning. Next, we establish prediction error guarantees for noisy, binary measurements such as may be collected from human respondents, and show how the sample complexity improves when the underlying metric is low-rank. Finally, we establish recovery guarantees under assumptions on the response distribution. We demonstrate the performance of our model on both simulated data and on a dataset of color preference judgements across a large number of users. 

   more » « less
4. The invariant measure of a walking droplet in hydrodynamic pilot–wave theory

   https://doi.org/10.1088/1361-6544/ad5f6f  

   Nguyen, Hung D; Oza, Anand U (July 2024, Nonlinearity)

   Abstract We study the long time statistics of a walker in a hydrodynamic pilot-wave system, which is a stochastic Langevin dynamics with an external potential and memory kernel. While prior experiments and numerical simulations have indicated that the system may reach a statistically steady state, its long-time behavior has not been studied rigorously. For a broad class of external potentials and pilot-wave forces, we construct the solutions as a dynamics evolving on suitable path spaces. Then, under the assumption that the pilot-wave force is dominated by the potential, we demonstrate that the walker possesses a unique statistical steady state. We conclude by presenting an example of such an invariant measure, as obtained from a numerical simulation of a walker in a harmonic potential. 

   more » « less
5. Finite-Sample Bounds for Adaptive Inverse Reinforcement Learning Using Passive Langevin Dynamics

   https://doi.org/10.1109/TIT.2025.3555479  

   Snow, Luke; Krishnamurthy, Vikram (June 2025, IEEE Transactions on Information Theory)

   This paper provides a finite-sample analysis of a passive stochastic gradient Langevin dynamics (PSGLD) algo- rithm. This algorithm is designed to achieve adaptive inverse reinforcement learning (IRL). Adaptive IRL aims to estimate the cost function of a forward learner performing a stochastic gradient algorithm (e.g., policy gradient reinforcement learning) by observing their estimates in real-time. The PSGLD algorithm is considered passive because it incorporates noisy gradients provided by an external stochastic gradient algorithm (forward learner), of which it has no control. The PSGLD algorithm acts as a randomized sampler to achieve adaptive IRL by reconstructing the forward learner’s cost function nonparametrically from the stationary measure of a Langevin diffusion. This paper analyzes the non-asymptotic (finite-sample) performance; we provide explicit bounds on the 2-Wasserstein distance between PSGLD algorithm sample measure and the stationary measure encoding the cost function, and provide guarantees for a kernel density estimation scheme which reconstructs the cost function from empirical samples. Our analysis uses tools from the study of Markov diffusion operators. The derived bounds have both practical and theoretical significance. They provide finite-time guarantees for an adaptive IRL mechanism, and substantially generalize the analytical framework of a line of research in passive stochastic gradient algorithms. 

   more » « less