Parameterized sequential decision making problems

Srivastava, Amber

Permalink

https://hdl.handle.net/2142/114034 Copy

Description

Title

Parameterized sequential decision making problems

Author(s)

Srivastava, Amber

Issue Date

2021-07-29

Director of Research (if dissertation) or Advisor (if thesis)

Salapaka, Srinivasa

Doctoral Committee Chair(s)

Salapaka, Srinivasa

Committee Member(s)

• Ferriera, Placid
• West, Matthew
• Milenkovic, Olgica
• Srikant, Rayadurgam

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2021-12

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/114034

Copyright and License Information

Copyright 2021 Amber Srivastava

Owning Collections