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

• URL: http://arxiv.org/abs/2407.09905v1
• Date: Sat, 13 Jul 2024 14:45:08 GMT
• Title: Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods
• Authors: Riccardo De Santi, Manish Prajapat, Andreas Krause,
• Abstract summary: We introduce Global RL (GRL), where rewards are globally defined over trajectories instead of locally over states. By exploiting ideas from submodular optimization, we propose a novel algorithmic scheme that converts any GRL problem to a sequence of classic RL problems.
• Score: 42.04223902155739
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• COPO: Consistency-Aware Policy Optimization [17.328515578426227]
  Reinforcement learning has significantly enhanced the reasoning capabilities of Large Language Models (LLMs) in complex problem-solving tasks.<n>Recently, the introduction of DeepSeek R1 has inspired a surge of interest in leveraging rule-based rewards as a low-cost alternative for computing advantage functions and guiding policy optimization.<n>We propose a consistency-aware policy optimization framework that introduces a structured global reward based on outcome consistency.
  arXiv  Detail & Related papers  (2025-08-06T07:05:18Z)
• Maximizing Confidence Alone Improves Reasoning [48.83927980325788]
  RENT: Reinforcement Learning via Entropy Minimization is a fully unsupervised RL method that requires no external reward or ground-truth answers.<n>We find that by reinforcing the chains of thought that yield high model confidence on its generated answers, the model improves its reasoning ability.
  arXiv  Detail & Related papers  (2025-05-28T17:59:37Z)
• Vintix: Action Model via In-Context Reinforcement Learning [72.65703565352769]
  We present the first steps toward scaling ICRL by introducing a fixed, cross-domain model capable of learning behaviors through in-context reinforcement learning. Our results demonstrate that Algorithm Distillation, a framework designed to facilitate ICRL, offers a compelling and competitive alternative to expert distillation to construct versatile action models.
  arXiv  Detail & Related papers  (2025-01-31T18:57:08Z)
• MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization [91.80034860399677]
  Reinforcement learning algorithms aim to balance exploiting the current best strategy with exploring new options that could lead to higher rewards. We introduce a framework, MaxInfoRL, for balancing intrinsic and extrinsic exploration. We show that our approach achieves sublinear regret in the simplified setting of multi-armed bandits.
  arXiv  Detail & Related papers  (2024-12-16T18:59:53Z)
• Enhancing Spectrum Efficiency in 6G Satellite Networks: A GAIL-Powered Policy Learning via Asynchronous Federated Inverse Reinforcement Learning [67.95280175998792]
  A novel adversarial imitation learning (GAIL)-powered policy learning approach is proposed for optimizing beamforming, spectrum allocation, and remote user equipment (RUE) association ins. We employ inverse RL (IRL) to automatically learn reward functions without manual tuning. We show that the proposed MA-AL method outperforms traditional RL approaches, achieving a $14.6%$ improvement in convergence and reward value.
  arXiv  Detail & Related papers  (2024-09-27T13:05:02Z)
• Ancestral Reinforcement Learning: Unifying Zeroth-Order Optimization and Genetic Algorithms for Reinforcement Learning [0.8287206589886879]
  Ancestral Reinforcement Learning (ARL) combines the robust gradient estimation of ZOO with the exploratory power of Genetic Algorithms. We theoretically reveal that the populational search in ARL implicitly induces the KL-regularization of the objective function, resulting in the enhanced exploration.
  arXiv  Detail & Related papers  (2024-08-18T14:16:55Z)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  Reinforcement learning (RL) has become the de facto standard practice for sequential decision-making problems by improving future acting policies with feedback. Recent developments in large language models (LLMs) have showcased impressive capabilities in language understanding and generation, yet they fall short in exploration and self-improvement capabilities. We develop an algorithm named LINVIT that incorporates LLM guidance as a regularization factor in value-based RL, leading to significant reductions in the amount of data needed for learning.
  arXiv  Detail & Related papers  (2024-02-25T20:07:13Z)
• REBEL: A Regularization-Based Solution for Reward Overoptimization in Robotic Reinforcement Learning from Human Feedback [61.54791065013767]
  A misalignment between the reward function and user intentions, values, or social norms can be catastrophic in the real world. Current methods to mitigate this misalignment work by learning reward functions from human preferences. We propose a novel concept of reward regularization within the robotic RLHF framework.
  arXiv  Detail & Related papers  (2023-12-22T04:56:37Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX. textttMEX integrates estimation and planning components while balancing exploration exploitation automatically. It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
  arXiv  Detail & Related papers  (2023-05-29T17:25:26Z)
• Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare [38.42691031505782]
  We propose a form of linear Q-function decomposition induced by factored action spaces. Our approach can help an agent make more accurate inferences within underexplored regions of the state-action space.
  arXiv  Detail & Related papers  (2023-05-02T19:13:10Z)
• Cross-Trajectory Representation Learning for Zero-Shot Generalization in RL [21.550201956884532]
  generalize policies learned on a few tasks over a high-dimensional observation space to similar tasks not seen during training. Many promising approaches to this challenge consider RL as a process of training two functions simultaneously. We propose Cross-Trajectory Representation Learning (CTRL), a method that runs within an RL agent and conditions its encoder to recognize behavioral similarity in observations.
  arXiv  Detail & Related papers  (2021-06-04T00:43:10Z)
• FOCAL: Efficient Fully-Offline Meta-Reinforcement Learning via Distance Metric Learning and Behavior Regularization [10.243908145832394]
  We study the offline meta-reinforcement learning (OMRL) problem, a paradigm which enables reinforcement learning (RL) algorithms to quickly adapt to unseen tasks. This problem is still not fully understood, for which two major challenges need to be addressed. We provide analysis and insight showing that some simple design choices can yield substantial improvements over recent approaches.
  arXiv  Detail & Related papers  (2020-10-02T17:13:39Z)
• Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples [31.31937554018045]
  Deep reinforcement learning (RL) methods require intensive data from the exploration of the environment to achieve satisfactory performance. We propose a framework that enables an RL agent to reason over its exploration process and distill high-level knowledge for effectively guiding its future explorations. Specifically, we propose a novel RL algorithm that learns high-level knowledge in the form of a finite reward automaton by using the L* learning algorithm.
  arXiv  Detail & Related papers  (2020-06-28T21:13:08Z)
• Forgetful Experience Replay in Hierarchical Reinforcement Learning from Demonstrations [55.41644538483948]
  In this paper, we propose a combination of approaches that allow the agent to use low-quality demonstrations in complex vision-based environments. Our proposed goal-oriented structuring of replay buffer allows the agent to automatically highlight sub-goals for solving complex hierarchical tasks in demonstrations. The solution based on our algorithm beats all the solutions for the famous MineRL competition and allows the agent to mine a diamond in the Minecraft environment.
  arXiv  Detail & Related papers  (2020-06-17T15:38:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.