Comprehensive Exam of CMSE Gabriel Maliakal
Department of Computational Mathematics, Science & Engineering
Michigan State University
Comprehensive Exam Notice
Nov 25th 2024
CMSE 1502 – 2:30 PM
Zoom link: https://msu.zoom.us/j/92390841042
Passcode: 408443
Reinforcement Learning-based Algorithms for Image Reconstruction and Graph Problems
By Gabriel Maliakal
Abstract:
MaxCut is a well-known NP-Complete problem, significant for numerous applications
in graph theory and optimization. This research introduces a Reinforcement Learning
(RL) approach aiming to improve the Goemans-Williamson (GW) algorithm's approximation
ratio for MaxCut. By formulating the problem as a Markov Decision Process (MDP), an
agent learns to optimize cut values through trajectory sampling and policy updates
using Proximal Policy Optimization (PPO). Empirical evaluations were conducted on
Erdős–Rényi (ER) graphs and Gset benchmarks, comparing performance against uniform
random sampling. Results indicate that agents trained with larger neural network hidden
dimensions and longer trajectories can surpass average performance benchmarks of both
GW and uniform sampling methods. However, training is computationally intensive, and
the agent's adaptability to new graph instances remains challenging. Future directions
include theoretical analysis of gradient flows, reward sampling, and improving agent
reusability across diverse graph distributions. Insights from this would be used for
optimal sensor placement for personalized dosimetry as well as analyze the bias in
convergence to optimal weights when implementing reinforcement learning as opposed
to supervised learning in image reconstruction.
Committee:
Adam Alessio (Co-chair)
Saiprasad Ravishankar (Co-chair)
Longxiu Huang
Dirk Colbry
Alvaro Velasquez
