Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods

2024-07-13 · Riccardo De Santi, Manish Prajapat, Andreas Krause

In classic Reinforcement Learning (RL), the agent maximizes an additive objective of the visited states, e.g., a value function. Unfortunately, objectives of this type cannot model many real-world applications such as experiment design, exploration, imitation learning, and risk-averse RL to name a few. This is due to the fact that additive objectives disregard interactions between states that are crucial for certain tasks. To tackle this problem, we introduce Global RL (GRL), where rewards are globally defined over trajectories instead of locally over states. Global rewards can capture negative interactions among states, e.g., in exploration, via submodularity, positive interactions, e.g., synergetic effects, via supermodularity, while mixed interactions via combinations of them. By exploiting ideas from submodular optimization, we propose a novel algorithmic scheme that converts any GRL problem to a sequence of classic RL problems and solves it efficiently with curvature-dependent approximation guarantees. We also provide hardness of approximation results and empirically demonstrate the effectiveness of our method on several GRL instances.

📄 PDF Abstract BibTeX arXiv:2407.09905

Code (0)

등록된 구현이 없습니다.

Tasks

Imitation LearningReinforcement Learning (RL)

Variational Policy Gradient Method for Reinforcement Learning with General Utilities

2020-07-04 · NeurIPS 2020 12 · Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari 외

In recent years, reinforcement learning (RL) systems with general goals beyond a cumulative sum of rewards have gained traction, such as in constrained problems, exploration, and acting upon prior experiences. In this pa…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Variational Monte Carlo

Neural Temporal-Difference Learning Converges to Global Optima

2019-12-01 · NeurIPS 2019 12 · Qi Cai, Zhuoran Yang, Jason D. Lee, Zhaoran Wang

Temporal-difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, due to the nonlinearity in value function approximation, such a coup…

Deep Reinforcement Learning Q-Learning Reinforcement Learning Reinforcement Learning (RL)

Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima

2019-05-24 · NeurIPS 2019 12 · Qi Cai, Zhuoran Yang, Jason D. Lee, Zhaoran Wang

Deep Reinforcement Learning Q-Learning Reinforcement Learning

Policy Poisoning in Batch Reinforcement Learning and Control

2019-10-13 · NeurIPS 2019 12 · Yuzhe Ma, Xuezhou Zhang, Wen Sun, Xiaojin Zhu

We study a security threat to batch reinforcement learning and control where the attacker aims to poison the learned policy. The victim is a reinforcement learner / controller which first estimates the dynamics and the r…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors

2025-08-10 · Mohamad Louai Shehab, Alperen Tercan, Necmiye Ozay arxiv

In this paper, we consider the problem of recovering time-varying reward functions from either optimal policies or demonstrations coming from a max entropy reinforcement learning problem. This problem is highly ill-posed…

Reinforcement Learning