{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/105018"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/105018","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Tensor decomposition and parallelization of Markov Decision Processes","abstract":"Markov Decision Processes (MDPs) with large state spaces arise frequently when applied to real world problems. Optimal solutions to such problems exist, but may not be computationally tractable, as the required processing scales exponentially with the number of states. Unsurprisingly, investigating methods for efficiently determining optimal or near-optimal policies has generated substantial interest and remains an active area of research. A recent paper introduced an MDP representation as a tensor composition of a set of smaller component MDPs, and suggested a method for solving an MDP by decomposition into its tensor components and solving the smaller problems in parallel, combining their solutions into one for the original problem. Such an approach promises an increase in solution efficiency, since each smaller problem could be solved exponentially faster than the original. This paper develops this MDP tensor decomposition and parallelization algorithm, and analyzes both its computational performance and the optimality of its resultant solutions.","abstract_html":"Markov Decision Processes (MDPs) with large state spaces arise frequently when applied to real world problems. Optimal solutions to such problems exist, but may not be computationally tractable, as the required processing scales exponentially with the number of states. Unsurprisingly, investigating methods for efficiently determining optimal or near-optimal policies has generated substantial interest and remains an active area of research. A recent paper introduced an MDP representation as a tensor composition of a set of smaller component MDPs, and suggested a method for solving an MDP by decomposition into its tensor components and solving the smaller problems in parallel, combining their solutions into one for the original problem. Such an approach promises an increase in solution efficiency, since each smaller problem could be solved exponentially faster than the original. This paper develops this MDP tensor decomposition and parallelization algorithm, and analyzes both its computational performance and the optimality of its resultant solutions.","abstract_has_math":false,"creators":["Smart, David P. (David Paul)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Computation for Design and Optimization Program.","school":null,"contributors":[],"advisors":["Olivier de Weck."],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-07-22T22:21:55Z","subjects":["Computation for Design and Optimization Program."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/105018","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Olivier de Weck."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."]},{"key":"dc:creator","label":"Author","values":["Smart, David P. (David Paul)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-10-25T19:49:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-10-25T19:49:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2016"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computation for Design and Optimization Program."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/105018"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2016.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 85-81)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Markov Decision Processes (MDPs) with large state spaces arise frequently when applied to real world problems. Optimal solutions to such problems exist, but may not be computationally tractable, as the required processing scales exponentially with the number of states. Unsurprisingly, investigating methods for efficiently determining optimal or near-optimal policies has generated substantial interest and remains an active area of research. A recent paper introduced an MDP representation as a tensor composition of a set of smaller component MDPs, and suggested a method for solving an MDP by decomposition into its tensor components and solving the smaller problems in parallel, combining their solutions into one for the original problem. Such an approach promises an increase in solution efficiency, since each smaller problem could be solved exponentially faster than the original. This paper develops this MDP tensor decomposition and parallelization algorithm, and analyzes both its computational performance and the optimality of its resultant solutions."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Tensor decomposition and parallelization of Markov Decision Processes"]}]}],"canonical_facts":{"dc:contributor.advisor":["Olivier de Weck."],"dc:contributor.department":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."],"dc:contributor.other":["Massachusetts Institute of Technology. Computation for Design and Optimization Program."],"dc:creator":["Smart, David P. (David Paul)"],"dc:date.accessioned":["2016-10-25T19:49:36Z"],"dc:date.available":["2016-10-25T19:49:36Z"],"dc:date.issued":["2016"],"dc:description":["Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2016.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 85-81)."],"dc:description.abstract":["Markov Decision Processes (MDPs) with large state spaces arise frequently when applied to real world problems. Optimal solutions to such problems exist, but may not be computationally tractable, as the required processing scales exponentially with the number of states. Unsurprisingly, investigating methods for efficiently determining optimal or near-optimal policies has generated substantial interest and remains an active area of research. A recent paper introduced an MDP representation as a tensor composition of a set of smaller component MDPs, and suggested a method for solving an MDP by decomposition into its tensor components and solving the smaller problems in parallel, combining their solutions into one for the original problem. Such an approach promises an increase in solution efficiency, since each smaller problem could be solved exponentially faster than the original. This paper develops this MDP tensor decomposition and parallelization algorithm, and analyzes both its computational performance and the optimality of its resultant solutions."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/105018"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Computation for Design and Optimization Program."],"dc:title":["Tensor decomposition and parallelization of Markov Decision Processes"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:55Z"}