The notion of \emph{policy regret} in online learning is a well defined? performance measure for the common scenario of adaptive adversaries, which more traditional quantities such as external regret do not take into account. We revisit the notion of policy regret and first show that there are online learning settings …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “policy regret”
The paper tackles robust policy learning from multiple data sources.
problem Learning a policy that generalizes across diverse settings from multiple heterogeneous data sources.
method Proposes a minimax regret optimization objective and a policy learning algorithm combining doubly robust offline policy evaluation and no-regret learning.
result Achieves minimal worst-case mixture regret up to a moderated vanishing rate of the total data across all sources.
New algorithm reduces policy regret in tallying bandits.
problem Measuring online learning performance against adaptive adversaries.
method Tallying bandit model, efficient algorithm with complete policy regret guarantee.
result Achieves a complete policy regret guarantee of .
Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to a…
RANDomized-exploration policy Optimization via Multiple Importance Sampling with Truncation (RANDOMIST) for PO with mediator feedback.
problem Policy Optimization in continuous control tasks.
method RANDomized-exploration policy Optimization via Multiple Importance Sampling with Truncation (RANDOMIST) for regret minimization in PO.
result Achieving constant regret under certain circumstances in PO with mediator feedback.
A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Banditsstat.ML
New policy optimizes risk and optimality in stochastic bandits.
problem Optimizing risk in stochastic bandits with heavy-tailed risk.
method Designing policies with worst-case optimality for expected regret and light-tailed risk distribution.
result Achieves worst-case optimality for expected regret and light-tailed risk distribution.
The paper tackles personalized policy learning from diverse data sources in a federated setting.
problem Learning personalized decision policies from observational bandit feedback across multiple heterogeneous data sources.
method Introduces a novel regret analysis for distinguishing global and local regret, and presents a federated policy learning algorithm using local policies trained with doubly robust offline policy evaluation strategies.
result Establishes finite-sample upper bounds on global and local regret, characterizing them by source heterogeneity and distribution shift.
New algorithm reduces regret by allowing free exploration in multi-armed bandits.
problem Designing an adaptive policy to minimize regret with a free exploration budget.
method Introduced -probably saving policies and a two-phase algorithm UFE-KLUCB-H.
result UFE-KLUCB-H accumulates strictly less regret than non-free exploration policies.
Proposes a method to learn policies from offline data with reduced bias.
problem Learning policies from offline data with reduced bias and complexity constraints.
method Cross-fitted debiasing device for policy learning from offline data.
result Achieves regret for complex policy classes with a product-of-errors nuisance remainder.
Improves policy optimization with polylog(T) regret bounds for stochastic losses.
problem Improves theoretical guarantees for policy optimization in stochastic settings.
method Leverages Tsallis and Shannon entropy regularizers for polylog(T) regret, and log-barrier regularizer for adversarial settings.
result Achieves a first-order polylog(T) regret bound for policy optimization in stochastic settings.
The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regretcs.LG
Learning reward functions can lead to poor policy performance despite low error.
problem Low error in learned reward functions does not guarantee low regret in policy performance.
method Mathematical analysis of reward learning and policy optimization.
result A low expected test error of the reward model guarantees low worst-case regret, but error-regret mismatch can occur with certain data distributions.
Study shows certainty equivalent policy minimizes regret in continuous-time systems.
problem Minimizing regret in continuous-time stochastic linear-quadratic systems.
method Theoretical analysis of randomized certainty equivalent policy.
result Establishes square-root of time regret bounds and linear scaling with parameters.
New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.
The paper sets bounds on how much regret is unavoidable in adaptive LQR with unknown B-matrix.
problem Understanding the limits of adaptive LQR with unknown B-matrix.
method Local asymptotic minimax regret lower bounds using van Trees' inequality and Bellman error representation.
result Logarithmic regret is impossible if the parametrization induces an uninformative optimal policy.
Study on learning strategies in adaptive Markov games with policy regret as metric.
problem Learning in dynamic Markov games with adaptive opponents is challenging.
method Introduced policy regret as a new learning metric and developed algorithms for consistent adaptive adversaries.
result Achieved policy regret against certain adaptive adversaries.
New algorithm bounds regret in mediator feedback bandit problems.
problem Mediator feedback bandit game with policy sets.
method Adopting EXP4 algorithm, new regret bounds based on policy set capacity.
result Nearly-matching lower bounds for policy set families.
Short note on soft-max and policy gradients in bandit problems using Lyapunov functions.
problem Analyzing soft-max and policy gradient methods in bandit problems.
method Lyapunov function argument for soft-max and differential equations for policy gradient algorithms.
result Regret bounds for soft-max and a different policy gradient algorithm in bandit problems.
New model-free algorithm achieves similar LQR regret guarantees.
problem Model-free control of linear dynamical systems under quadratic costs.
method Online policy gradient scheme with policy space cost analysis.
result Achieves regret scaling with √T, matching model-based methods.
The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement amon…
N-discount optimality was introduced as a hierarchical form of policy- and value-function optimality, with Blackwell optimality lying at the top level of the hierarchy Veinott (1969); Blackwell (1962). We formalize notions of myopic discount factors, value functions and policies in terms of Blackwell optimality in MDPs…
Paper proposes OPF policy for fair resource allocation with sublinear regret.
problem Fair resource allocation in an online setting against an unrestricted adversary.
method Online Proportional Fair (OPF) policy achieving approximate sublinear regret.
result OPF policy achieves -approximate sublinear regret with .
Policy gradient methods with aggregated states can achieve better performance than approximate policy iteration.
problem Approximation errors in policy and value function approximations.
method State-aggregated representations and policy gradient methods.
result Policy gradient methods can achieve a per-period regret bounded by ε, while approximate policy iteration and value iteration have a higher regret.
Study on policy gradient for stochastic bandits using diffusion approximation.
problem Improving policy gradient methods for stochastic bandits with optimal regret bounds.
method Continuous-time diffusion approximation of policy gradient with learning rate analysis.
result Proved optimal regret bound of for .
New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves Bayesian regret for stochastic multi-armed bandits.
Study optimal policy regret in partially observable Markov games with adaptive opponents.
problem Optimal sequential decision-making in partially observable environments against strategic, adaptive opponents.
method An epoch-based optimistic maximum-likelihood algorithm that selects one policy per epoch using confidence sets built cumulatively from past data.
result Achieves policy regret for fixed problem parameters, with explicit dependence on horizon, adversary memory, confidence radius, and aggregate Eluder dimension.
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.
Study non-rectangular robust MDPs for average-reward, finding optimal policies and transient values.
problem Non-rectangular robust Markov decision processes under average-reward criterion.
method Proves history-dependent policies are robust-optimal, introduces transient-value framework, constructs epoch-based policy.
result Existence and properties of robust optimal policies, transient value bounds.
Paper proposes an -policy gradient for online pricing, reducing regret to .
problem Online pricing learning task
method Combines model-based and model-free reinforcement learning, using -greedy with gradient descent.
result Achieves expected regret of order .
In some reinforcement learning problems an agent may be provided with a set of input policies, perhaps learned from prior experience or provided by advisors. We present a reinforcement learning with policy advice (RLPA) algorithm which leverages this input set and learns to use the best policy in the set for the reinfo…
Study online control of unknown time-varying systems with negative and positive results.
problem Online control of time-varying systems with unknown dynamics.
method Algorithmic upper bounds and lower bounds for different policy classes.
result Sublinear adaptive regret bounds for Disturbance Response policies.
Algorithm minimizes regret and converges to equilibria in Markov games.
problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.
method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.
result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Riskstat.ML
Optimizes regret distribution in stochastic bandits for risk balance.
problem Balancing regret expectation and tail risk in stochastic bandits.
method Characterizes optimal regret tail probability for any threshold, proposes new policies.
result Discovers an intrinsic gap in optimal tail rate based on time horizon uncertainty.
New algorithm reduces best-in-class regret in contextual bandits.
problem Compete with the best policy in a class without model restrictions.
method Proposes an algorithm that updates policies by minimizing a pessimistic objective, including a clipped inverse-propensity estimate and variance penalty.
result Achieves fast best-in-class regret rates, including polylogarithmic rates in the parametric case.
One-bit feedback suffices for a bandit problem's optimal strategy.
problem Optimal strategy for multi-armed bandit problem with limited feedback.
method Coding and decoding schemes for one-bit feedback to mimic full-reward feedback.
result Regret ratio approaches 1 with one-bit feedback.
New algorithm reduces online learning regret in uninformed Markov games.
problem Achieving no external regret in uninformed Markov games is impossible.
method Empirical Nash-value regret, parameter-free algorithm, adaptive restart.
result Achieves regret bound.
New algorithms reduce dynamic regret in non-stationary RL environments.
problem Optimizing policies in environments that change over time.
method POWER and POWER++ algorithms for policy optimization with dynamic regret analysis.
result POWER++ improves dynamic regret by actively adapting to non-stationarity.
A classic setting of the stochastic K-armed bandit problem is considered in this note. In this problem it has been known that KL-UCB policy achieves the asymptotically optimal regret bound and KL-UCB+ policy empirically performs better than the KL-UCB policy although the regret bound for the original form of the KL-UCB…
New methods use vector search and nearest-neighbor matching for policy learning in causal inference.
problem Learning optimal policies in causal inference with limited data.
method RAG-based policy learning with vector search and nearest-neighbor matching.
result The methods bound the within-candidate choice regret and evaluate the one-step method directly as a policy.
Study shows how to learn optimal policies quickly in stochastic control problems.
problem Learning optimal policies in large, continuous state and action spaces with limited data.
method Analyzes three geometric exponents to quantify fast policy regret convergence.
result Shows that fast policy regret convergence is induced by specific geometric structures.
Study uses contextual bandits to optimize charity exposure in donation solicitation.
problem Optimizing charity exposure in donation solicitation using survey responses.
method Adaptive experiment design to balance cumulative regret minimization and simple regret minimization.
result Adaptive experimentation yields better policy learning outcomes than uniform randomization.
Study optimizes experimental design for best treatment arm identification.
problem Identifying the best treatment arm given contextual information.
method Adaptive Sampling-Policy Learning (PLAS) strategy for minimax rate optimality.
result PLAS strategy achieves minimax rate optimality in expected simple regret.
Algorithm reduces long-term policy regret in ML decision-making.
problem Capturing long-term impacts of ML decisions in communities.
method Modeling communities as arms in a multi-armed bandit problem, defining policy regret as a stronger metric than external regret.
result Algorithm achieves provably sub-linear policy regret for long time horizons.
Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
New RL algorithm reduces policy switching cost to loglog(T) with similar regret.
problem Low policy switching cost in real-life RL applications.
method Stage-wise exploration and adaptive policy elimination.
result Regret of with switching cost.
An important problem in sequential decision-making under uncertainty is to use limited data to compute a safe policy, i.e., a policy that is guaranteed to perform at least as well as a given baseline strategy. In this paper, we develop and analyze a new model-based approach to compute a safe policy when we have access …
New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.
problem Model-based policy learning in uncertain, time-varying dynamics.
method Planning regret metric and iterative algorithm for minimizing it.
result Empirical evidence shows the proposed algorithm outperforms existing methods.