{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/45071"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/45071","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Analysis of centralized and distributed temporal difference learning","abstract":"Temporal difference learning with linear function approximation is a popular method to obtain a low-dimensional approximation of the value function of a policy in a Markov Decision Process. This thesis provides an interpretation of this method in terms of a splitting of the gradient of an appropriately chosen function. As a consequence of this interpretation, convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. Beyond giving a fuller explanation of why temporal difference works, this interpretation also yields improved convergence times. This thesis also provides a new non-asymptotic analysis of distributed TD(0) with linear function approximation. The approach relies on \"one-shot averaging,\" where N agents run local copies of TD(0) and average the outcomes only once at the very end. This thesis considers two models: one in which the agents interact with an environment they can observe and whose transitions depend on all of their actions, which are referred to as the global state model; and one in which each agent can run a local copy of an identical Markov Decision Process, which is called the local state model. In the global state model, this thesis shows that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0), which is an improvement on the state-of-the-art. In the local state model, this thesis demonstrates a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of N faster than the convergence time of TD(0). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods.","abstract_html":"Temporal difference learning with linear function approximation is a popular method to obtain a low-dimensional approximation of the value function of a policy in a Markov Decision Process. This thesis provides an interpretation of this method in terms of a splitting of the gradient of an appropriately chosen function. As a consequence of this interpretation, convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. Beyond giving a fuller explanation of why temporal difference works, this interpretation also yields improved convergence times. This thesis also provides a new non-asymptotic analysis of distributed TD(0) with linear function approximation. The approach relies on &quot;one-shot averaging,&quot; where N agents run local copies of TD(0) and average the outcomes only once at the very end. This thesis considers two models: one in which the agents interact with an environment they can observe and whose transitions depend on all of their actions, which are referred to as the global state model; and one in which each agent can run a local copy of an identical Markov Decision Process, which is called the local state model. In the global state model, this thesis shows that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0), which is an improvement on the state-of-the-art. In the local state model, this thesis demonstrates a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of N faster than the convergence time of TD(0). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods.","abstract_has_math":false,"creators":["Liu, Rui"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Systems Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Olshevsky, Alexander"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-11-18T19:50:13Z","subjects":["Computer science"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0001-7333-6291"],"render_values":[{"text":"0000-0001-7333-6291","href":"https://orcid.org/0000-0001-7333-6291","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/45071","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/45071","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F45071","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Olshevsky, Alexander"]},{"key":"dc:creator","label":"Author","values":["Liu, Rui"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0001-7333-6291"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-31T19:07:49Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-31T19:07:49Z"]},{"key":"dc:date.issued","label":"Date","values":["2022"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2022-08-30T04:06:37Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/45071"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Temporal difference learning with linear function approximation is a popular method to obtain a low-dimensional approximation of the value function of a policy in a Markov Decision Process. This thesis provides an interpretation of this method in terms of a splitting of the gradient of an appropriately chosen function. As a consequence of this interpretation, convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. Beyond giving a fuller explanation of why temporal difference works, this interpretation also yields improved convergence times. This thesis also provides a new non-asymptotic analysis of distributed TD(0) with linear function approximation. The approach relies on \"one-shot averaging,\" where N agents run local copies of TD(0) and average the outcomes only once at the very end. This thesis considers two models: one in which the agents interact with an environment they can observe and whose transitions depend on all of their actions, which are referred to as the global state model; and one in which each agent can run a local copy of an identical Markov Decision Process, which is called the local state model. In the global state model, this thesis shows that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0), which is an improvement on the state-of-the-art. In the local state model, this thesis demonstrates a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of N faster than the convergence time of TD(0). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods."]},{"key":"dc:title","label":"Title","values":["Analysis of centralized and distributed temporal difference learning"]}]}],"canonical_facts":{"dc:contributor.advisor":["Olshevsky, Alexander"],"dc:creator":["Liu, Rui"],"dc:date.accessioned":["2022-08-31T19:07:49Z"],"dc:date.available":["2022-08-31T19:07:49Z"],"dc:date.issued":["2022"],"dc:date.updated":["2022-08-30T04:06:37Z"],"dc:description.abstract":["Temporal difference learning with linear function approximation is a popular method to obtain a low-dimensional approximation of the value function of a policy in a Markov Decision Process. This thesis provides an interpretation of this method in terms of a splitting of the gradient of an appropriately chosen function. As a consequence of this interpretation, convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. Beyond giving a fuller explanation of why temporal difference works, this interpretation also yields improved convergence times. This thesis also provides a new non-asymptotic analysis of distributed TD(0) with linear function approximation. The approach relies on \"one-shot averaging,\" where N agents run local copies of TD(0) and average the outcomes only once at the very end. This thesis considers two models: one in which the agents interact with an environment they can observe and whose transitions depend on all of their actions, which are referred to as the global state model; and one in which each agent can run a local copy of an identical Markov Decision Process, which is called the local state model. In the global state model, this thesis shows that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0), which is an improvement on the state-of-the-art. In the local state model, this thesis demonstrates a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of N faster than the convergence time of TD(0). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods."],"dc:identifier.orcid":["0000-0001-7333-6291"],"dc:identifier.uri":["https://hdl.handle.net/2144/45071"],"dc:language.iso":["en_US"],"dc:subject":["Computer science"],"dc:title":["Analysis of centralized and distributed temporal difference learning"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Systems Engineering"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T19:50:13Z"}