Reasoning without Regret

2025/04/14 by Chitra, Tarun
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2504.09777

Abstract

Chain-of-thought reasoning enables large language models to solve multi-step tasks by framing problem solving as sequential decision problems. Outcome-based rewards, which provide feedback only on final answers, show impressive success, but face challenges with credit assignment and slow convergence. In contrast, procedure-based rewards offer efficient step-level feedback, but typically require costly human supervision. We introduce Backwards Adaptive Reward Shaping (BARS), a no-regret framework that converts sparse outcomes-based rewards into effective procedure-based signals. BARS uses sparse rewards generated from terminal-state priors and cover trees to scale rewards while preventing exploitation. With Bellman contraction and (Δ, ε)-gap rewards, our backward Euler solver achieves ε-accuracy in O((R_max/Δ)log(1/ε)) iterations with O(log T) dynamic regret over T rounds. Our analysis, based on generic chaining, continuous scaling limits, and non-linear Feynman-Kac bounds, connects recent outcome-based methods' empirical successes with the benefits of intermediate supervision. Combined, this provides the first rigorous no-regret algorithm for outcome reward shaping, providing a theoretical foundation for the empirical success of DeepSeek's R1.

Citations

• Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning
• Q\sharp: Provably Optimal Distributional RL for LLM Post-Training
• The Relationship Between Reasoning and Performance in Large Language Models -- o3 (mini) Thinks Harder, Not Longer
• Process Reward Models for LLM Agents: Practical Framework and Directions
• Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective
• Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search
• Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
• Early External Safety Testing of OpenAI's o3-mini: Insights from the Pre-Deployment Evaluation
• DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning
• Towards Large Reasoning Models: A Survey of Reinforced Reasoning with Large Language Models
• Optimal Design for Reward Modeling in RLHF
• Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning
• Recursive Introspection: Teaching Language Model Agents How to Self-Improve
• RLHF Workflow: From Reward Modeling to Online RLHF
• Do LLM Agents Have Regret? A Case Study in Online Learning and Games
• Can large language models explore in-context?
• Improving Reinforcement Learning from Human Feedback Using Contrastive Rewards
• InfoRM: Mitigating Reward Hacking in RLHF via Information-Theoretic Reward Modeling
• BioXP-0.5B: Explainable Medical-AI via RL-GRPO
• DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence
• Secrets of RLHF in Large Language Models Part II: Reward Modeling
• Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations
• A Survey of Temporal Credit Assignment in Deep Reinforcement Learning
• Confronting Reward Model Overoptimization with Constrained RLHF
• Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiency
• Comparison of viscosity solutions for a class of second order PDEs on the Wasserstein space
• Comparison of viscosity solutions for a class of second-order PDEs on the Wasserstein space
• Let's Verify Step by Step
• What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization
• Tree of Thoughts: Deliberate Problem Solving with Large Language Models
• DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
• Solving math word problems with process- and outcome-based feedback
• STaR: Bootstrapping Reasoning With Reasoning
• Training language models to follow instructions with human feedback
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• PDE-Based Optimal Strategy for Unconstrained Online Learning
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts
• Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting
• Malicious Experts versus the multiplicative weights algorithm in online prediction
• Optimal anytime regret with two experts
• Prediction with Expert Advice: a PDE Perspective
• RUDDER: Return Decomposition for Delayed Rewards
• Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
• Size-Independent Sample Complexity of Neural Networks
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Proximal Policy Optimization Algorithms
• Spectrally-normalized margin bounds for neural networks
• Coin Betting and Parameter-Free Online Learning
• The Benefit of Multitask Representation Learning
• Trust Region Policy Optimization
• Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
• Multi-Armed Bandits in Metric Spaces
• Adapted solution of a backward stochastic differential equation
• Asymptotically efficient adaptive allocation rules
• OpenAI o1 System Card
• A PDE approach for regret bounds under partial monitoring
• Reinforcement Learning: An Introduction

Related

• Linking Process to Outcome: Conditional Reward Modeling for LLM Reasoning
• Let's reward step by step: Step-Level reward model as the Navigators for Reasoning
• Learn to Reason Efficiently with Adaptive Length-based Reward Shaping
• Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning
• Think-RM: Enabling Long-Horizon Reasoning in Generative Reward Models