Exploratory combinatorial optimization with reinforcement learning

AAAI 2020 - 34th AAAI Conference on Artificial Intelligence (2020) 3243-3250

Authors:

TD Barrett, WR Clements, JN Foerster, AI Lvovsky

Abstract:

Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient heuristic methods to tackle these problems can be learned. Previous works construct the solution subset incrementally, adding one element at a time, however, the irreversible nature of this approach prevents the agent from revising its earlier decisions, which may be necessary given the complexity of the optimization task. We instead propose that the agent should seek to continuously improve the solution by learning to explore at test time. Our approach of exploratory combinatorial optimization (ECODQN) is, in principle, applicable to any combinatorial problem that can be defined on a graph. Experimentally, we show our method to produce state-of-the-art RL performance on the Maximum Cut problem. Moreover, because ECO-DQN can start from any arbitrary configuration, it can be combined with other search methods to further improve performance, which we demonstrate using a simple random search.

Interferobot: Aligning an optical interferometer by a reinforcement learning agent

Advances in Neural Information Processing Systems 2020-December (2020)

Authors:

D Sorokin, A Ulanov, E Sazhina, A Lvovsky

Abstract:

Limitations in acquiring training data restrict potential applications of deep reinforcement learning (RL) methods to the training of real-world robots. Here we train an RL agent to align a Mach-Zehnder interferometer, which is an essential part of many optical experiments, based on images of interference fringes acquired by a monocular camera. The agent is trained in a simulated environment, without any hand-coded features or a priori information about the physics, and subsequently transferred to a physical interferometer. Thanks to a set of domain randomizations simulating uncertainties in physical measurements, the agent successfully aligns this interferometer without any fine tuning, achieving a performance level of a human expert.

Exploratory Combinatorial Optimization with Reinforcement Learning

THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE 34 (2020) 3251-3258

Authors:

Thomas D Barrett, William R Clements, Jakob N Foerster, AI Lvovsky

Quantum-inspired annealers as Boltzmann generators for machine learning and statistical physics

(2019)

Authors:

Alexander E Ulanov, Egor S Tiunov, AI Lvovsky

Entanglement of macroscopically distinct states of light

Optica Optical Society of America 6:11 (2019) 1425-1430

Authors:

DV Sychev, VA Novikov, KK Pirov, C Simon, AI Lvovsky

Abstract:

Schrödinger’s famous Gedankenexperiment has inspired multiple generations of physicists to think about apparent paradoxes that arise when the logic of quantum physics is applied to macroscopic objects. The development of quantum technologies enabled us to produce physical analogues of Schrödinger’s cats, such as superpositions of macroscopically distinct states as well as entangled states of microscopic and macroscopic entities. Here we take one step further and prepare an optical state which, in Schrödinger’s language, is equivalent to a superposition of two cats, one of which is dead and the other alive, but it is not known in which state each individual cat is. Specifically, the alive and dead states are, respectively, the displaced single photon and displaced vacuum (coherent state), with the magnitude of displacement being on a scale of 10^8 photons. These two states have significantly different photon statistics and are therefore macroscopically distinguishable.