This work shows how approximate reward models can significantly improve inference-time scaling.
problem Improving the efficiency of inference for large language models.
method Identifying the Bellman error of approximate reward models and using Sequential Monte Carlo (SMC) for inference.
result Approximate reward models can reduce computational complexity from exponential to polynomial in T T T . Study scaling laws of reward model overoptimization in reinforcement learning.
problem Reward model overoptimization hinders true performance in reinforcement learning.
method Synthetic setup with fixed gold reward model; optimization using RL or best-of- n n n sampling; analysis of scaling laws. result Scaling laws of reward model overoptimization differ based on optimization method and scale smoothly with model parameters.
This work provides a thorough study on how reward scaling can affect performance of deep reinforcement learning agents. In particular, we would like to answer the question that how does reward scaling affect non-saturating ReLU networks in RL? This question matters because ReLU is one of the most effective activation f…
New method predicts and optimizes test-time scaling for LLMs.
problem Lack of principled guidance on scaling LLMs efficiently.
method Tail-guided search to predict and allocate compute.
result SLG Search achieves higher rewards with less compute.
Reinforcement learning algorithms rely on carefully engineering environment rewards that are extrinsic to the agent. However, annotating each environment with hand-designed, dense rewards is not scalable, motivating the need for developing reward functions that are intrinsic to the agent. Curiosity is a type of intrins…
SA-GFN corrects biases in GFlowNets due to graph symmetries.
problem Systematic biases in state transition probability computations.
method Incorporates symmetry corrections into the learning process through reward scaling.
result Eliminates need for explicit state transition computations.
The paper enhances preference learning by incorporating response time data.
problem Lack of temporal information in user decision-making for reward model learning.
method Integrates response time alongside binary choice data using the EZ model and Neyman-orthogonal loss functions.
result Response time-augmented approach reduces error rates from exponential to polynomial scaling, improving sample efficiency.
The abstract explores connections between reinforcement learning, scaling, and diffusion.
problem Aligning reinforcement learning with human feedback and scaling techniques.
method Clarifying connections between reinforcement learning, scaling, and diffusion.
result Introducing a resampling approach for alignment and reward-directed diffusion models.
New algorithm improves inference-time alignment without reward hacking.
problem Improving quality of responses from language models with limited compute.
method Inference-time alignment, focusing on e x t t t I n f e r e n c e T i m e P e s s i m i s m exttt{InferenceTimePessimism} e x ttt I n f er e n ce T im e P ess imi s m algorithm. result Optimal performance and scaling-monotonicity of e x t t t I n f e r e n c e T i m e P e s s i m i s m exttt{InferenceTimePessimism} e x ttt I n f er e n ce T im e P ess imi s m . Improves generative models by optimizing rewards and sample editing.
problem Efficiently generating high-reward samples with structural constraints.
method Introduces MDM-VGB, a discrete diffusion sampler that augments unmasking generation with reward-guided remasking.
result MDM-VGB achieves quadratic complexity and robustness to noise, outperforming heuristics like best-of- N N N . Reward-free RL in linear MDPs is as hard as reward-aware RL.
problem Reward-free RL in linear MDPs without access to the reward function during exploration.
method Developed a computationally efficient algorithm with sample complexity O ~ ( d 2 H 5 / ε 2 ) \widetilde{\mathcal{O}}(d^2 H^5/ε^2) O ( d 2 H 5 / ε 2 ) . result Achieved optimal d d d dependence in linear MDPs for reward-free RL, matching the reward-aware RL setting. Learning reward functions from data is a promising path towards achieving scalable Reinforcement Learning (RL) for robotics. However, a major challenge in training agents from learned reward models is that the agent can learn to exploit errors in the reward model to achieve high reward behaviors that do not correspond …
Unified algorithm for optimizing rewards in stochastic path problems.
problem Optimizing rewards in stochastic path problems with unknown reward scales.
method A simple optimistic algorithm with regret guarantees.
result Regret bound matches best known results for SSP with all non-positive rewards.
One obstacle to applying reinforcement learning algorithms to real-world problems is the lack of suitable reward functions. Designing such reward functions is difficult in part because the user only has an implicit understanding of the task objective. This gives rise to the agent alignment problem: how do we create age…
Improves RLHF sample efficiency by scaling reward complexity polynomially.
problem Exponential sample complexity in RLHF algorithms for skewed preferences.
method SE-POPO, an online RLHF algorithm that achieves polynomial sample complexity.
result SE-POPO outperforms existing algorithms in sample efficiency.
Paper proposes RRD to learn proxy rewards for sparse delayed rewards in episodic reinforcement learning.
problem Learning from sparse and delayed rewards in reinforcement learning.
method Randomized Return Decomposition (RRD) algorithm to redistribute rewards.
result Substantial improvement over baseline algorithms in experiments.
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
Reinforcement learning usually makes use of numerical rewards, which have nice properties but also come with drawbacks and difficulties. Using rewards on an ordinal scale (ordinal rewards) is an alternative to numerical rewards that has received more attention in recent years. In this paper, a general approach to adapt…
New model for display advertising with stochastic and adversarial components.
problem Display advertising with stochastic and adversarial click-through-rates.
method Adversarial scaling model; two algorithms tested: action elimination and mirror descent.
result Two algorithms are robust to adversarial scaling.
Adaptive exploration scheme for evaluating multiple policies with different rewards.
problem Online multi-reward multi-policy evaluation.
method Adapted ( ε , δ ) (ε,δ) ( ε , δ ) -PAC perspective and MR-NaS exploration scheme to minimize sample complexity. result Demonstrated effectiveness of adaptive exploration in tabular domains.
New algorithm uses GNNs to optimize rewards in graph-structured data.
problem Optimizing rewards in molecule design with graph-structured data.
method Embedding permutation invariance into GNNs and using GNTK for regret bounds.
result First GNN confidence bound and phased-elimination algorithm with sublinear regret.
Bayesian reward learning from demonstrations enables rigorous safety and uncertainty analysis when performing imitation learning. However, Bayesian reward learning methods are typically computationally intractable for complex control problems. We propose Bayesian Reward Extrapolation (Bayesian REX), a highly efficient …
Imitation Learning describes the problem of recovering an expert policy from demonstrations. While inverse reinforcement learning approaches are known to be very sample-efficient in terms of expert demonstrations, they usually require problem-dependent reward functions or a (task-)specific reward-function regularizatio…
The paper develops a robust algorithm for contextual bandits with heavy-tailed rewards.
problem Contextual bandits with heavy-tailed rewards.
method Develops an algorithm based on Catoni's estimator for robust statistics, applying it to contextual bandits with general function approximation.
result Establishes regret bounds that depend on cumulative reward variance and logarithmically on the reward range and number of rounds.
We introduce a framework to study the effective objectives at different time scales of financial market microstructure. The financial market can be regarded as a complex adaptive system, where purposeful agents collectively and simultaneously create and perceive their environment as they interact with it. It has been s…
Best-of-Majority improves inference performance in Pass@ k k k settings.
problem Inference in difficult tasks often underperforms with single-shot selection methods.
method Combining majority voting and Best-of-N, Best-of-Majority restricts candidates to high-frequency responses.
result Best-of-Majority achieves minimax optimal regret and outperforms other methods.
Study quantile reward identification with 1-bit feedback constraints.
problem Best arm identification with quantile reward and 1-bit communication.
method Proposes an algorithm using noisy binary search for quantile reward estimation.
result Derives upper and lower bounds on sample complexity for 1-bit feedback.
A new UCB policy improves reward-cost ratio estimation in budgeted MAB.
problem Maximizing reward-cost ratio under budget constraints.
method ω-UCB policy with asymmetric confidence intervals.
result Logarithmic regret and superior performance in various settings.
Two novel methods identify influential features in CMABs for better reward distribution.
problem Suboptimal features degrade rewards, interpretability, and efficiency in CMABs.
method Heterogeneous Incremental Effect (HIE) and Heterogeneous Distribution Divergence (HDD) methods.
result Consistent ability to identify influential HTE features, enhancing CMAB performance.
PRISM integrates diverse rewards in MORL, improving sample efficiency and Pareto coverage.
problem Heterogeneous MORL where dense objectives dominate, leading to poor sample efficiency.
method PRISM uses reflectional symmetry and ReSymNet to reconcile temporal-frequency mismatches and accelerate exploration.
result PRISM consistently outperforms sparse-reward baselines and oracles, achieving significant Pareto gains.
Reinforcement learning with sparse rewards is still an open challenge. Classic methods rely on getting feedback via extrinsic rewards to train the agent, and in situations where this occurs very rarely the agent learns slowly or cannot learn at all. Similarly, if the agent receives also rewards that create suboptimal m…
Optimizes reward learning design for complex tasks using nonparametric methods.
problem Challenges in specifying reward functions for complex tasks.
method Models rewards and policies as nonparametric functions in RKHSs, derives risk bounds, and optimizes query design.
result Derives non-asymptotic excess risk bounds and finite sample statistical rates for reward learning.
New algorithm for multi-player bandits without needing lower bounds or scaling inversely.
problem Multi-player bandits without collision sensing information.
method Proposes a novel algorithm that circumvents two problems of existing algorithms.
result Proves a theoretical regret upper bound and shows superior performance in practice.
BERT embeddings improve sequence quality metrics.
problem Measuring the quality of generated sequences against references.
method Employ contextual BERT embeddings for sequence-level reward.
result Contextual embeddings provide a more effective learning signal.
We consider Markov Decision Processes (MDPs) where the rewards are unknown and may change in an adversarial manner. We provide an algorithm that achieves state-of-the-art regret bound of O ( τ ( ln ∣ S ∣ + ln ∣ A ∣ ) T ln ( T ) ) O( \sqrt{τ(\ln|S|+\ln|A|)T}\ln(T)) O ( τ ( ln ∣ S ∣ + ln ∣ A ∣ ) T ln ( T )) , where S S S is the state space, A A A is the action space, τ τ τ is the mixing time of the MDP, and $…
Calibrated PRMs improve inference efficiency for LLMs by dynamically adjusting compute budgets.
problem Poor calibration of PRMs leads to overestimation of success probabilities in partial reasoning steps.
method Quantile regression for calibration, instance-adaptive scaling (IAS) framework.
result Calibrated PRMs reduce inference costs while maintaining accuracy, especially on confident problems.
Robust Q-learning algorithm resists corrupted rewards.
problem Non-ideal environments with corrupted rewards.
method Developed a novel robust Q-learning algorithm using historical data.
result Finite-time convergence rate matches state-of-the-art bounds.
We propose a new method for learning from a single demonstration to solve hard exploration tasks like the Atari game Montezuma's Revenge. Instead of imitating human demonstrations, as proposed in other recent works, our approach is to maximize rewards directly. Our agent is trained using off-the-shelf reinforcement lea…
Method uses ANN to estimate incentive salience from large behavioral data.
problem Estimating incentive salience in naturalistic settings.
method Artificial Neural Networks (ANNs) for latent state approximation.
result ANNs produce better representations for predicting future behaviour.
A new policy for contextual bandits adapts to reward vector shifts.
problem Learning under reward vector shifts with ordered rewards.
method Adaptive-discretization and optimistic elimination policy.
result Established upper bounds on preference-based regret.
Improved inference-time alignment using Best-of-N and smoothing.
problem Reward overoptimization in Best-of-N (BoN) due to poor proxy reward models.
method Introduced Soft Best-of-N (SBoN) and analyzed its performance through KL divergence and regret analysis.
result Smoothing helps SBoN mitigate reward overoptimization, especially when proxy reward quality is low.
This work compares human feedback methods for reward learning in bandits.
problem Understanding how human feedback affects the performance of reward learning methods.
method Theoretical comparison of human feedback approaches in offline contextual bandits.
result Human bias and uncertainty in feedback modeling impact the theoretical guarantees of reward learning methods.
Optimal strategy proposed for maximizing cumulative reward in continuum-armed bandits.
problem Maximizing cumulative reward in a scenario with limited resources and unknown stochastic rewards.
method Proposed an optimal strategy for a nonparametric setting with side information on actions.
result Optimal regret scales as \(O(T^{1/3})\) up to poly-logarithmic factors when \(T\) is proportional to \(N\).
We consider stochastic multi-armed bandit problems with complex actions over a set of basic arms, where the decision maker plays a complex action rather than a basic arm in each round. The reward of the complex action is some function of the basic arms' rewards, and the feedback observed may not necessarily be the rewa…
New algorithms reduce contextual bandits' regret without knowing reward noise variances.
problem Reducing regret in contextual bandits with unknown reward noise variances.
method Developed new algorithms based on the optimism principle.
result Regret scales as the square root of the sum of measurement variances, not the time horizon.
Improves text-to-image diffusion models using GFlowNets.
problem Aligning diffusion models with text descriptions.
method Post-training diffusion models with GFlowNets to generate high-reward images.
result Effective alignment of large-scale text-to-image diffusion models with reward information.
Thompson Sampling fails to perform well in high dimensions.
problem Thompson Sampling's suboptimality in high-dimensional combinatorial semi-bandits.
method Analysis of TS for combinatorial semi-bandits, including non-linear and linear reward functions, with Bernoulli rewards and uniform priors.
result TS's regret scales exponentially in the ambient dimension and minimax regret scales almost linearly in high dimensions.
The paper analyzes the reward improvement of aligned policies in large language models.
problem Optimizing policies in large language models while staying close to a reference policy.
method Information-theoretic analysis and reduction to exponential order statistics.
result Information-theoretic upper bounds on reward improvement are derived.