{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110451"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110451","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Model-free reinforcement learning in non-stationary Markov Decision Processes","abstract":"Reinforcement learning (RL) studies the problem where an agent maximizes its cumulative reward through sequential interactions with an initially unknown environment, usually modeled by a Markov Decision Process (MDP). The classical RL literature typically assumes that the state transition functions and the reward functions of the MDP are time-invariant. Such a stationary model, however, cannot capture the dynamic nature of many sequential decision-making problems in practice. In this thesis, we consider the problem of reinforcement learning in \\emph{non-stationary} MDPs. In our setting, both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long as their cumulative variation magnitude does not exceed certain budgets. We propose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. We theoretically show that RestartQ-UCB outperforms existing solutions in terms of dynamic regret, a notion commonly utilized to measure the performance of an online learning algorithm in a non-stationary environment. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of $\\widetilde{O}(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H T^{\\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\\Delta>0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further show that our algorithm is nearly optimal by establishing an information-theoretical lower bound of $\\Omega(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H^{\\frac{2}{3}} T^{\\frac{2}{3}})$, which to the best of our knowledge is the first impossibility result that characterizes the fundamental limits of non-stationary RL in general. To the best of our knowledge, RestartQ-UCB is the first model-free algorithm for non-stationary RL. Compared with model-based solutions, our algorithm is more time- and space-efficient, flexible, and compatible with the model deep RL architectures. We empirically evaluate RestartQ-UCB on RL tasks with both abrupt and gradual types of non-stationarity. Simulation results validate the advantages of RestartQ-UCB in terms of cumulative rewards and computational efficiency. We further demonstrate the power of our results through a ``learning to collaborate'' example in the context of multi-agent RL, where non-stationarity is a key challenge.","abstract_html":"Reinforcement learning (RL) studies the problem where an agent maximizes its cumulative reward through sequential interactions with an initially unknown environment, usually modeled by a Markov Decision Process (MDP). The classical RL literature typically assumes that the state transition functions and the reward functions of the MDP are time-invariant. Such a stationary model, however, cannot capture the dynamic nature of many sequential decision-making problems in practice. In this thesis, we consider the problem of reinforcement learning in \\emph{non-stationary} MDPs. In our setting, both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long as their cumulative variation magnitude does not exceed certain budgets. We propose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. We theoretically show that RestartQ-UCB outperforms existing solutions in terms of dynamic regret, a notion commonly utilized to measure the performance of an online learning algorithm in a non-stationary environment. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of <span class=\"etd-inline-math\">\\widetilde{O}(S<sup>\\frac{1}{3}</sup> A<sup>\\frac{1}{3}</sup> \\Delta<sup>\\frac{1}{3}</sup> H T<sup>\\frac{2}{3}</sup>)</span>, where $S$ and $A$ are the numbers of states and actions, respectively, $\\Delta&gt;0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further show that our algorithm is nearly optimal by establishing an information-theoretical lower bound of <span class=\"etd-inline-math\">\\Omega(S<sup>\\frac{1}{3}</sup> A<sup>\\frac{1}{3}</sup> \\Delta<sup>\\frac{1}{3}</sup> H<sup>\\frac{2}{3}</sup> T<sup>\\frac{2}{3}</sup>)</span>, which to the best of our knowledge is the first impossibility result that characterizes the fundamental limits of non-stationary RL in general. To the best of our knowledge, RestartQ-UCB is the first model-free algorithm for non-stationary RL. Compared with model-based solutions, our algorithm is more time- and space-efficient, flexible, and compatible with the model deep RL architectures. We empirically evaluate RestartQ-UCB on RL tasks with both abrupt and gradual types of non-stationarity. Simulation results validate the advantages of RestartQ-UCB in terms of cumulative rewards and computational efficiency. We further demonstrate the power of our results through a ``learning to collaborate&#x27;&#x27; example in the context of multi-agent RL, where non-stationarity is a key challenge.","abstract_has_math":true,"creators":["Mao, Weichao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Başar, Tamer"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T01:10:43Z","date_published":"2021-09-17T01:10:43Z","updated_at":"2026-07-22T22:24:50Z","subjects":["reinforcement learning","Markov decision process","non-stationarity"],"languages":["en"],"rights":["Copyright 2021 Weichao Mao"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110451","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Başar, Tamer"]},{"key":"dc:creator","label":"Author","values":["Mao, Weichao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T01:10:43Z","2021-04-09","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["reinforcement learning","Markov decision process","non-stationarity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Weichao Mao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110451"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Reinforcement learning (RL) studies the problem where an agent maximizes its cumulative reward through sequential interactions with an initially unknown environment, usually modeled by a Markov Decision Process (MDP). The classical RL literature typically assumes that the state transition functions and the reward functions of the MDP are time-invariant. Such a stationary model, however, cannot capture the dynamic nature of many sequential decision-making problems in practice. In this thesis, we consider the problem of reinforcement learning in \\emph{non-stationary} MDPs. In our setting, both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long as their cumulative variation magnitude does not exceed certain budgets. We propose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. We theoretically show that RestartQ-UCB outperforms existing solutions in terms of dynamic regret, a notion commonly utilized to measure the performance of an online learning algorithm in a non-stationary environment. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of $\\widetilde{O}(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H T^{\\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\\Delta>0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further show that our algorithm is nearly optimal by establishing an information-theoretical lower bound of $\\Omega(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H^{\\frac{2}{3}} T^{\\frac{2}{3}})$, which to the best of our knowledge is the first impossibility result that characterizes the fundamental limits of non-stationary RL in general. To the best of our knowledge, RestartQ-UCB is the first model-free algorithm for non-stationary RL. Compared with model-based solutions, our algorithm is more time- and space-efficient, flexible, and compatible with the model deep RL architectures. We empirically evaluate RestartQ-UCB on RL tasks with both abrupt and gradual types of non-stationarity. Simulation results validate the advantages of RestartQ-UCB in terms of cumulative rewards and computational efficiency. We further demonstrate the power of our results through a ``learning to collaborate'' example in the context of multi-agent RL, where non-stationarity is a key challenge.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Weichao Mao, accepted the attached license on 2021-04-08 at 20:13.","The student, Weichao Mao, submitted this Thesis for approval on 2021-04-08 at 20:18.","This Thesis was approved for publication on 2021-04-09 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16261 on 2021-09-16 at 16:40:42","Made available in DSpace on 2021-09-17T01:10:43Z (GMT). No. of bitstreams: 2 MAO-THESIS-2021.pdf: 1405319 bytes, checksum: 40bc4ef969d3d8aef46140d66e24b610 (MD5) LICENSE.txt: 4208 bytes, checksum: ce55cb04417e517a8a7b4baceed445cf (MD5) Previous issue date: 2021-04-09"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Model-free reinforcement learning in non-stationary Markov Decision Processes"]}]}],"canonical_facts":{"dc:contributor":["Başar, Tamer"],"dc:creator":["Mao, Weichao"],"dc:date":["2021-09-17T01:10:43Z","2021-04-09","2021-05"],"dc:description":["Reinforcement learning (RL) studies the problem where an agent maximizes its cumulative reward through sequential interactions with an initially unknown environment, usually modeled by a Markov Decision Process (MDP). The classical RL literature typically assumes that the state transition functions and the reward functions of the MDP are time-invariant. Such a stationary model, however, cannot capture the dynamic nature of many sequential decision-making problems in practice. In this thesis, we consider the problem of reinforcement learning in \\emph{non-stationary} MDPs. In our setting, both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long as their cumulative variation magnitude does not exceed certain budgets. We propose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. We theoretically show that RestartQ-UCB outperforms existing solutions in terms of dynamic regret, a notion commonly utilized to measure the performance of an online learning algorithm in a non-stationary environment. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of $\\widetilde{O}(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H T^{\\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\\Delta>0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further show that our algorithm is nearly optimal by establishing an information-theoretical lower bound of $\\Omega(S^{\\frac{1}{3}} A^{\\frac{1}{3}} \\Delta^{\\frac{1}{3}} H^{\\frac{2}{3}} T^{\\frac{2}{3}})$, which to the best of our knowledge is the first impossibility result that characterizes the fundamental limits of non-stationary RL in general. To the best of our knowledge, RestartQ-UCB is the first model-free algorithm for non-stationary RL. Compared with model-based solutions, our algorithm is more time- and space-efficient, flexible, and compatible with the model deep RL architectures. We empirically evaluate RestartQ-UCB on RL tasks with both abrupt and gradual types of non-stationarity. Simulation results validate the advantages of RestartQ-UCB in terms of cumulative rewards and computational efficiency. We further demonstrate the power of our results through a ``learning to collaborate'' example in the context of multi-agent RL, where non-stationarity is a key challenge.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Weichao Mao, accepted the attached license on 2021-04-08 at 20:13.","The student, Weichao Mao, submitted this Thesis for approval on 2021-04-08 at 20:18.","This Thesis was approved for publication on 2021-04-09 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16261 on 2021-09-16 at 16:40:42","Made available in DSpace on 2021-09-17T01:10:43Z (GMT). No. of bitstreams: 2 MAO-THESIS-2021.pdf: 1405319 bytes, checksum: 40bc4ef969d3d8aef46140d66e24b610 (MD5) LICENSE.txt: 4208 bytes, checksum: ce55cb04417e517a8a7b4baceed445cf (MD5) Previous issue date: 2021-04-09"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110451"],"dc:language":["en"],"dc:rights":["Copyright 2021 Weichao Mao"],"dc:subject":["reinforcement learning","Markov decision process","non-stationarity"],"dc:title":["Model-free reinforcement learning in non-stationary Markov Decision Processes"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}