File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning

TitleComputational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning
Authors
Issue Date2022
Citation
Journal of Artificial Intelligence Research, 2022, v. 73, p. 847-896 How to Cite?
AbstractMany goal-reaching reinforcement learning (RL) tasks have empirically verified that rewarding the agent on subgoals improves convergence speed and practical performance. We attempt to provide a theoretical framework to quantify the computational benefits of rewarding the completion of subgoals, in terms of the number of synchronous value iterations. In particular, we consider subgoals as one-way intermediate states, which can only be visited once per episode and propose two settings that consider these one-way intermediate states: the one-way single-path (OWSP) and the one-way multi-path (OWMP) settings. In both OWSP and OWMP settings, we demonstrate that adding intermediate rewards to subgoals is more computationally efficient than only rewarding the agent once it completes the goal of reaching a terminal state. We also reveal a trade-off between computational complexity and the pursuit of the shortest path in the OWMP setting: adding intermediate rewards significantly reduces the computational complexity of reaching the goal but the agent may not find the shortest path, whereas with sparse terminal rewards, the agent finds the shortest path at a significantly higher computational cost. We also corroborate our theoretical results with extensive experiments on the MiniGrid environments using Q-learning and some popular deep RL algorithms.
Persistent Identifierhttp://hdl.handle.net/10722/327783
ISSN
2023 Impact Factor: 4.5
2023 SCImago Journal Rankings: 1.614

 

DC FieldValueLanguage
dc.contributor.authorZhai, Yuexiang-
dc.contributor.authorBaek, Christina-
dc.contributor.authorZhou, Zhengyuan-
dc.contributor.authorJiao, Jiantao-
dc.contributor.authorMa, Yi-
dc.date.accessioned2023-05-08T02:26:46Z-
dc.date.available2023-05-08T02:26:46Z-
dc.date.issued2022-
dc.identifier.citationJournal of Artificial Intelligence Research, 2022, v. 73, p. 847-896-
dc.identifier.issn1076-9757-
dc.identifier.urihttp://hdl.handle.net/10722/327783-
dc.description.abstractMany goal-reaching reinforcement learning (RL) tasks have empirically verified that rewarding the agent on subgoals improves convergence speed and practical performance. We attempt to provide a theoretical framework to quantify the computational benefits of rewarding the completion of subgoals, in terms of the number of synchronous value iterations. In particular, we consider subgoals as one-way intermediate states, which can only be visited once per episode and propose two settings that consider these one-way intermediate states: the one-way single-path (OWSP) and the one-way multi-path (OWMP) settings. In both OWSP and OWMP settings, we demonstrate that adding intermediate rewards to subgoals is more computationally efficient than only rewarding the agent once it completes the goal of reaching a terminal state. We also reveal a trade-off between computational complexity and the pursuit of the shortest path in the OWMP setting: adding intermediate rewards significantly reduces the computational complexity of reaching the goal but the agent may not find the shortest path, whereas with sparse terminal rewards, the agent finds the shortest path at a significantly higher computational cost. We also corroborate our theoretical results with extensive experiments on the MiniGrid environments using Q-learning and some popular deep RL algorithms.-
dc.languageeng-
dc.relation.ispartofJournal of Artificial Intelligence Research-
dc.titleComputational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1613/JAIR.1.13326-
dc.identifier.scopuseid_2-s2.0-85128186467-
dc.identifier.volume73-
dc.identifier.spage847-
dc.identifier.epage896-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats