Attention-Based Learning for Combinatorial Optimization

Combinatorial optimization problems, such as the Traveling Salesman Problem (TSP), have been studied for decades. However, with the rise of reinforcement learning in recent years, many of these problems are being revisited as a way to gauge these new models in different environments. In this thesis, we explore the use of a new type of model, the Decision Transformer, which is a Self-Attention Transformer architecture that was recently developed for training on reinforcement learning problems. To analyze the model, we structure the Traveling Salesman problem as a reinforcement learning problem and, by continuously varying parameters of the environment, measure its generalizability and success in this environment. This thesis aims to conduct an initial study of applying Decision Transformers to combinatorial optimization problems.¹

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Smith, Carson

Advisor dc:contributor.advisor

• Balakrishnan, Hamsa

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/144893

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/144893