Markov Decision Processes and Sparse Linear Regression: A Combinatorial Optimization Viewpoint

Sunday, April 26, 2020 - 8:30am - 9:00am
Keller 3-180
Srinivasa Salapaka (University of Illinois at Urbana-Champaign)
Many physical systems in nature pose combinatorial resource allocation problems that involve a huge number of particles on the order of Avogadro’s number, that is, about particles. Statistical Physics provides methods and tools that make it possible to analyze such large systems. There have been many efforts that transfer these tools to large-scale data analysis. This work is one such effort. This talk will present methods and algorithms that mimic free-energy principle from statistical physics to address a class of combinatorial optimization problems. In fact, this principle is viewed as maximum entropy principle (MEP) propounded by E.T. Jaynes. We present a MEP based framework that gives a common viewpoint to a range of seemingly dissimilar problems that include combinatorial resource allocation problems, data clustering, aggregation and partitioning of large graphical networks, routing and scheduling, and variants of traveling salesman problem. In particular, we view Markov Decision Processes (MDPs) and Reinforcement Learning (RL) problems as combinatorial optimization problems
and present MEP based framework for solving them. We show that these methods can accommodate parameterized MDP and RL problems, where the cost function and the states are parameterized by additional decision variables. We also present how this framework can be used to solve another problem – the sparse regression problem. Again this problem is viewed as a combinatorial optimization problem and MEP based approach is used to solve it.