Files in this item



application/pdfSRIVASTAVA-DISSERTATION-2021.pdf (8MB)Restricted Access
(no description provided)PDF


Title:Parameterized sequential decision making problems
Author(s):Srivastava, Amber
Director of Research:Salapaka, Srinivasa
Doctoral Committee Chair(s):Salapaka, Srinivasa
Doctoral Committee Member(s):Ferriera, Placid; West, Matthew; Milenkovic, Olgica; Srikant, Rayadurgam
Department / Program:Mechanical Sci & Engineering
Discipline:Mechanical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Sequential Decisions, Markov Decision Processes, Reinforcement Learning, Maximum Entropy Principle, Clustering, Markov chain
Abstract:This thesis addresses a class of optimization problems that deals with the two-fold objective of making sequential decisions, and simultaneously determining the unknown problem parameters such that the associated cost function gets minimized. We refer to these problems as parameterized Sequential Decision Making (para-SDM) problems. The application areas are plenty; for instance, network design problems, job-shop scheduling, industrial process optimization, last mile delivery, vehicle routing, sensor networks, clustering and classification. In this work, we develop a combinatorial optimization viewpoint for these problems - where the viewpoint is facilitated by the combinatorially large number of possible sequences of decisions - and use Maximum Entropy Principle (MEP) based framework to address them. The optimization problems considered in this thesis have been shown to be NP-hard, accompanied by a non-convex cost function whose surface that is riddled by multiple poor local minima. The combinatorially large number of possible sequences of decisions on top of the above mentioned challenges render para-SDM as a difficult class of optimization problems. Our proposed MEP-based framework is designed to overcome the aforesaid challenges in para-SDM. For instance, we employ annealing from a suitable convex function to the non-convex cost function to avoid getting stuck in a poor local minima. Additionally, we utilize the problem structures (such as the law of optimality of the paths) to represent the combinatorial number of possibilites using much smaller decision variable space. The proposed framework is flexible to incorporating application-specific capacity, inclusion-exclusion, and dynamic constraints. Our framework also extends to the class of problems where the information about the underlying model is lacking, and we develop suitable stochastic iterative updates that interacts with the underlying system to simultaneously learn the sequences and the parameter values. A peculiar characteristic of the annealing process in our MEP-based frameworks is the phase transition phenomenon. In particular, these are the specific instances in the annealing procedure at which the solution undergoes significant changes. We demonstrate the utility of these phase transitions in determining certain design hyperparamters in para-SDMs, and in general, in combinatorial optimization problems; for instance, estimating the true number of clusters in a data set, or determining the appropriate choice of the sparsity level in sparse linear regression problems.
Issue Date:2021-07-29
Rights Information:Copyright 2021 Amber Srivastava
Date Available in IDEALS:2022-04-29
Date Deposited:2021-12

This item appears in the following Collection(s)

Item Statistics