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,695 papers · 148 categories

Trend · papers per month

count % of corpus

48 results for “discounted regret”

Discounted Online Convex Optimization: Uniform Regret Across a Continuous Intervalcs.LG

Paper develops a discounted algorithm for online convex optimization that adapts to unknown discount factors.

problem Developing an algorithm that can adapt to an unknown discount factor in online convex optimization.

method Smoothed Online Gradient Descent (SOGD) with Discounted-Normal-Predictor (DNP).

result Achieves a uniform

O(\sqrt{\log T/1-λ})

discounted regret across a continuous interval of discount factors.

Online Convex Optimization Discounted Regret Adaptive Algorithms Smoothed Gradient Descent Discounted-Normal-Predictor

2025-05-26abs ↗pdf ↗

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscs.LG

UCBVI-γ algorithm minimizes regret in discounted MDPs.

problem Minimizing regret in discounted MDPs.

method Optimism in the face of uncertainty principle and Bernstein-type bonus.

result UCBVI-γ achieves nearly minimax optimal regret.

reinforcement learning Markov Decision Processes discounted MDPs UCBVI-γ regret minimization

2020-10-01abs ↗pdf ↗

On consistency of optimal pricing algorithms in repeated posted-price auctions with strategic buyercs.GT

We study revenue optimization learning algorithms for repeated posted-price auctions where a seller interacts with a single strategic buyer that holds a fixed private valuation for a good and seeks to maximize his cumulative discounted surplus. For this setting, first, we propose a novel algorithm that never decreases …

2017-07-17abs ↗pdf ↗

Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecs.LG

New algorithm learns optimal policies with minimal memory and time.

problem Learning optimal policies in discounted MDPs with short burn-in time.

method Variance reduction and adaptive policy switching.

result First regret-optimal model-free algorithm with low burn-in time.

reinforcement learning discounted MDPs regret minimization policy switching variance reduction

2023-05-24abs ↗pdf ↗

Online Linear Regression in Dynamic Environments via Discountingcs.LG

Optimal online linear regression in dynamic environments using discounted Vovk-Azoury-Warmuth forecaster.

problem Achieving optimal performance in dynamic online linear regression without prior knowledge.

method Developed a discounted variant of the Vovk-Azoury-Warmuth forecaster to achieve optimal dynamic regret guarantees.

result Achieved dynamic regret of the form $O\left(d\log(T)\vee \sqrt{dP_{T}^γ(\vec{u})T} ight)$, with a learnable discount factor.

online linear regression dynamic regret discounted forecaster Vovk-Azoury-Warmuth strongly-adaptive guarantees

2024-05-29abs ↗pdf ↗

Issues concerning realizability of Blackwell optimal policies in reinforcement learningcs.LG

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…

2019-05-20abs ↗pdf ↗

A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHScs.LG

New algorithm reduces online regression error in RKHS.

problem Online regression with time-varying functions in RKHS.

method Hierarchical Vovk-Azoury-Warmuth with discounting.

result Achieves optimal dynamic regret with

O(T^{2/3}P_T^{1/3} + \sqrt{T}\ln T)

regret bound.

online regression Reproducing Kernel Hilbert Space dynamic regret discounting random features

2025-06-27abs ↗pdf ↗

Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcs.LG

Paper proposes an efficient RL algorithm for discounted MDPs using feature mapping.

problem Efficient reinforcement learning for large state and action spaces.

method Uses feature mapping to represent states and actions in a low-dimensional space, proposing a novel algorithm with polynomial regret bound.

result Achieves a

O(d\sqrt{T}/(1-γ)^2)

regret bound, near-optimal up to a

(1-γ)^{-0.5}

factor.

Reinforcement Learning Discounted MDPs Feature Mapping Regret Bound Polynomial Complexity

2020-06-23abs ↗pdf ↗

Thompson Sampling for Infinite-Horizon Discounted Decision Processesstat.ML

This paper improves Thompson Sampling for complex decision-making problems.

problem Learning in infinite-horizon discounted decision processes with unknown parameters.

method Developed a general canonical probability space and new metrics for analyzing adaptive learning algorithms.

result Thompson Sampling achieves complete learning in complex decision-making problems.

Thompson Sampling Discounted MDPs Infinite Horizon Learning Algorithms Probability Space

2024-05-14abs ↗pdf ↗

Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPsstat.ML

New algorithm reduces reinforcement learning regret to sqrt(T) without strong dynamics assumptions.

problem Infinite-horizon average-reward reinforcement learning with linear MDPs.

method Approximate by discounted-reward MDPs and apply optimistic value iteration.

result Achieves O(sqrt(T)) regret with polynomial complexity.

Reinforcement Learning Average Reward Linear MDPs Optimistic Value Iteration Discounted Reward

2024-05-23abs ↗pdf ↗

Discounted Thompson Sampling for Non-Stationary Bandit Problemscs.LG

DS-TS adapts to abrupt and smooth changes in bandit problems.

problem Non-stationary multi-armed bandit problems with abrupt and smooth changes.

method Discounted Thompson Sampling with Gaussian priors.

result Achieves nearly optimal regret bound for both abrupt and smooth changes.

Discounted Thompson Sampling Non-stationary bandit Gaussian priors Regret bound Abrupt changes

2023-05-18abs ↗pdf ↗

Randomized Exploration for Non-Stationary Stochastic Linear Banditsstat.ML

We investigate two perturbation approaches to overcome conservatism that optimism based algorithms chronically suffer from in practice. The first approach replaces optimism with a simple randomization when using confidence sets. The second one adds random perturbations to its current estimate before maximizing the expe…

2019-12-11abs ↗pdf ↗

Approximation Benefits of Policy Gradient Methods with Aggregated Statescs.LG

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.

policy gradient approximate policy iteration state aggregation regret analysis discount factor

2020-07-22abs ↗pdf ↗

Mirror Descent Meets Fixed Share (and feels no regret)cs.LG

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds …

2012-02-15abs ↗pdf ↗

Regret Bounds for Discounted MDPscs.LG

Paper proposes new $γ$ -regret measure for non-episodic RL.

problem Measuring performance in non-episodic RL environments.

method Introduces

γ

-regret as a new performance measure and derives bounds.

result Closed the gap between lower and upper bounds for

γ

-regret.

Reinforcement Learning Non-Episodic RL Regret Discounted MDPs

2020-02-12abs ↗pdf ↗

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentstat.ML

New algorithm for nonstationary GLBs reduces computation and memory costs.

problem Nonstationary generalized linear bandits with unknown time-varying parameters.

method Discounted Online Mirror Descent (DOMD) for parameter estimation.

result Dynamic regret bounds of order

O(1)

per round in drifting and piecewise-stationary environments.

nonstationary GLBs discounted online mirror descent dynamic regret bounds non-convex projection computation efficiency

2026-05-25abs ↗pdf ↗

Discounted Adaptive Online Learning: Towards Better Regularizationcs.LG

Adaptive online learning algorithm improves history forgetting in nonstationary environments.

problem Adversarial nonstationary environments where future data can be very different from past data.

method Discounted regret in online convex optimization, FTRL-based algorithm, adaptive learning rate.

result Improves classical gradient descent with constant learning rate in online convex optimization.

online learning nonstationary environments discounted regret FTRL adaptive learning rate

2024-02-05abs ↗pdf ↗

Posterior Sampling for Continuing Environmentscs.LG

PSRL extension for continuing environments reduces regret.

problem Formalizing and analyzing resampling approach for reinforcement learning.

method Continuing PSRL maintains a model of the environment and replaces it with samples from the posterior distribution.

result Established an

ilde{O}(τS \sqrt{A T})

bound on Bayesian regret.

reinforcement learning PSRL continuing environments posterior sampling rewards

2022-11-29abs ↗pdf ↗

An Approximate Dynamic Programming Approach to Adversarial Online Learningcs.GT

We describe an approximate dynamic programming (ADP) approach to compute approximations of the optimal strategies and of the minimal losses that can be guaranteed in discounted repeated games with vector-valued losses. Such games prominently arise in the analysis of regret in repeated decision-making in adversarial env…

2016-03-16abs ↗pdf ↗

Multi-Armed Bandits with Network Interferencecs.LG

New algorithm minimizes regret in multi-armed bandits with network interference.

problem Minimizing regret in online experiments with network interference.

method Sparse network interference model, discrete Fourier analysis, linear regression-based algorithms.

result Provable low regret algorithms for sparse interference networks.

multi-armed bandits network interference sparse models regret minimization discrete Fourier analysis

2024-05-28abs ↗pdf ↗

Contextual Bandits with Knapsacks for a Conversion Modelcs.LG

Adaptive policies solve a linear program to maximize rewards while minimizing costs in sales with discounts.

problem Maximizing rewards in sales with discounts while considering costs.

method Solves a linear program based on upper-confidence estimates of conversion probabilities.

result Achieves a regret bound of the typical order (OPT/

B

)

\sqrt{T}

, where B is the total budget allowed.

contextual bandits knapsacks sales discounts regret bound

2022-06-01abs ↗pdf ↗

Q

-learning with Logarithmic Regretcs.LG

Logarithmic regret achieved in Q-learning with positive gap.

problem Achieving logarithmic cumulative regret in Q-learning with positive sub-optimality gap.

method Optimistic Q-learning with logarithmic regret bound.

result Logarithmic cumulative regret bound proven for optimistic Q-learning.

Q-learning logarithmic regret reinforcement learning sub-optimality gap

2020-06-16abs ↗pdf ↗

Fatigue-aware Bandits for Dependent Click Modelscs.LG

A new model considers fatigue in online content recommendation systems.

problem Fatigue in users due to overexposure and boredom from similar recommendations.

method Proposed a fatigue-aware Dependent Click Model (DCM) and two learning algorithms.

result Developed algorithms with regret bounds for learning content relevance and fatigue effects.

recommender systems online learning user fatigue content recommendation regret bounds

2020-08-22abs ↗pdf ↗

Gap-Dependent Bounds for Two-Player Markov Gamescs.LG

The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.

problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.

method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.

result The proposed bounds match theoretical lower bounds up to a logarithmic term.

Q-learning Markov Games Cumulative Regret Nash Q-learning Logarithmic Bounds

2021-07-01abs ↗pdf ↗

Delegative Reinforcement Learning: learning to avoid traps with a little helpcs.LG

Most known regret bounds for reinforcement learning are either episodic or assume an environment without traps. We derive a regret bound without making either assumption, by allowing the algorithm to occasionally delegate an action to an external advisor. We thus arrive at a setting of active one-shot model-based reinf…

2019-07-19abs ↗pdf ↗

Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycs.LG

Improved model-free RL algorithm with reduced sample complexity.

problem Learning optimal policies in discounted MDPs efficiently.

method Proposes new algorithms with improved sample complexity bounds.

result Achieves better sample complexity than existing methods.

Reinforcement Learning Model-Free Sample Complexity Markov Decision Process Pseudo-Regret

2020-06-06abs ↗pdf ↗

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscs.LG

Improved online Q-learning for MDPs with concentration bounds.

problem Online Q-learning in infinite-horizon discounted MDPs with sublinear regret for large gaps.

method Smoothed

ε_n

-Greedy exploration scheme combining

ε_n

-greedy and Boltzmann exploration, analyzed using concentration bounds for contractive Markovian stochastic approximation.

result Near-

ilde{O}(N^{9/10})

regret bound for Smoothed

ε_n

-Greedy exploration scheme.

online Q-learning Markov decision processes regret bounds stochastic approximation concentration inequalities

2026-02-18abs ↗pdf ↗

On the Minimax Regret in Online Ranking with Top-k Feedbackcs.LG

Paper characterizes minimax regret rates for online ranking with top-k feedback.

problem Analyzing online ranking with partial feedback.

method Developed techniques from partial monitoring to characterize minimax regret rates.

result Full characterization of minimax regret rates for Precision@n.

online ranking partial feedback minimax regret top-k feedback ranking performance measures

2023-09-05abs ↗pdf ↗

Fast Rates for the Regret of Offline Reinforcement Learningcs.LG

Paper analyzes faster convergence rates for reinforcement learning from offline data.

problem Analyzing faster convergence rates for reinforcement learning from offline data.

method Fine analysis of reinforcement learning from offline data, providing fast rates for regret convergence.

result The paper provides fast rates for the regret convergence, showing that the level of exponentiation depends on the noise in the decision-making problem.

reinforcement learning offline data regret analysis fast rates Markov decision process

2021-01-31abs ↗pdf ↗

Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescs.LG

Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-r…

2019-10-15abs ↗pdf ↗

A Reduction from Reinforcement Learning to No-Regret Online Learningcs.LG

We present a reduction from reinforcement learning (RL) to no-regret online learning based on the saddle-point formulation of RL, by which "any" online algorithm with sublinear regret can generate policies with provable performance guarantees. This new perspective decouples the RL problem into two parts: regret minimiz…

2019-11-14abs ↗pdf ↗

A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescs.LG

KeRNS tackles non-stationary reinforcement learning in metric spaces.

problem Non-stationary reinforcement learning in metric spaces.

method KeRNS uses time-dependent kernels to model non-stationary Markov Decision Processes (MDPs).

result KeRNS achieves a regret bound that scales with the covering dimension and total variation of the MDP.

reinforcement learning non-stationary metric spaces kernel-based episodic

2020-07-09abs ↗pdf ↗

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescs.LG

New RL algorithm for linear MDPs with nearly optimal regret.

problem Optimizing reinforcement learning for linear mixture Markov decision processes.

method Proposed a new Bernstein-type concentration inequality for self-normalized martingales and a computationally efficient algorithm UCRL-VTR+.

result UCRL-VTR+ achieves nearly minimax optimal regret of

ilde O(dH\sqrt{T})

reinforcement learning Markov decision processes linear function approximation minimax optimality Bernstein inequality

2020-12-15abs ↗pdf ↗

Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcs.LG

Algorithm POLO learns low-rank MDPs with adversarial changes in full-info feedback.

problem Learning low-rank MDPs with adversarial changes and unknown transition probabilities.

method Policy optimization-based algorithm POLO with regret guarantee.

result POLO achieves sublinear regret guarantee with no dependence on state space size.

Adversarial MDPs Low-rank MDPs Policy Optimization Regret Minimization Oracle-Efficiency

2023-11-14abs ↗pdf ↗

Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcs.LG

New RL method tackles dynamic MDPs with evolving rewards and states.

problem Dynamic MDPs with evolving rewards and states.

method Sliding Window Upper-Confidence bound for Reinforcement Learning (SWUCRL2-CW) and Bandit-over-Reinforcement Learning (BORL).

result Achieves dynamic regret bound for non-stationary MDPs.

Reinforcement Learning Markov Decision Processes Non-Stationarity Dynamic Regret Confidence Widening

2020-06-24abs ↗pdf ↗

Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximizationcs.LG

Efficiently selects seed nodes to maximize content influence in unknown social networks.

problem Maximizing content spread in social networks with unknown network model.

method Formulated as an infinite-horizon discounted MDP, uses model-based reinforcement learning to select seed users adaptively.

result Established a regret bound of

\widetilde O(\sqrt{T})

for the algorithm.

Reinforcement Learning Influence Maximization Social Networks Adaptive Optimization Discounted MDP

2022-06-29abs ↗pdf ↗

Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertaintycs.LG

Paper develops a new RL method for MDPs with uncertainty, achieving better regret bounds.

problem Online reinforcement learning in environments with both endogenous and exogenous uncertainty.

method Developed a VB-UCRL algorithm that restarts based on variation schedules.

result Established a regret bound of saving at most

\sqrt{S}

S^{\frac{1}{6}}T^{\frac{1}{12}}

Reinforcement Learning Markov Decision Processes Uncertainty Regret Bound Variation Aware

2021-06-15abs ↗pdf ↗

The Decision Geometry of Covariance Estimation for the Global Minimum-Variance Portfolio under Heavy Tailsstat.ML

The study analyzes how covariance estimation errors affect the global minimum-variance portfolio under heavy-tailed distributions.

problem The impact of covariance estimation errors on the global minimum-variance portfolio under heavy-tailed distributions.

method Characterization of covariance-estimation error's effect on GMVP suboptimality, derivation of regret identity and bound, application to heavy-tailed returns.

result The decision geometry of GMVP regret is invariant to a (p-1)-dimensional projection of the error matrix, with invariance to the covariance-scale direction as an exact special case.

covariance estimation global minimum-variance portfolio heavy-tailed returns decision-focused learning regret analysis

2026-06-25abs ↗pdf ↗

Non-Linear Discounting and Default Compensation: Valuation of Non-Replicable Value and Damage: When the Social Discount Rate may become Negativeq-fin.MF

Paper introduces non-linear discounting models for default compensation and climate valuation.

problem Valuation of non-replicable value and damage under default risk.

method Develops two models: one for risk-neutralising discounting and another for survival probability dependent discounting.

result Non-decaying discount factors (negative discount rates) are possible under certain scenarios.

discounting default compensation non-replicable value climate valuation non-linear models

2020-07-13abs ↗pdf ↗

Fitted Occupancy-Ratio Evaluation without Bellman Completenessstat.ML

FORE evaluates occupancy ratios without requiring Bellman completeness.

problem Offline reinforcement learning occupancy ratio estimation.

method Fitted occupancy-ratio evaluation (FORE) using adjoint Bellman recursion.

result FORE achieves convergence in KL without Bellman completeness.

occupancy-ratio reinforcement learning fixed-point method density-ratio KL divergence

2026-07-06abs ↗pdf ↗

Business analytics meets artificial intelligence: Assessing the demand effects of discounts on Swiss train ticketsecon.GN

Study analyzes how discounts affect train ticket purchases and rescheduling in Switzerland.

problem Understanding how discounts influence train ticket buying and rescheduling behavior.

method Machine learning techniques, including causal machine learning, to analyze survey data.

result Increasing a discount rate by 1% increases the rescheduled trip share by 0.16% among always buyers.

train tickets discounts machine learning Switzerland rescheduling

2021-05-04abs ↗pdf ↗

Iterated risk measures for risk-sensitive Markov decision processes with discounted costcs.GT

We demonstrate a limitation of discounted expected utility, a standard approach for representing the preference to risk when future cost is discounted. Specifically, we provide an example of the preference of a decision maker that appears to be rational but cannot be represented with any discounted expected utility. A …

2012-02-14abs ↗pdf ↗

The Sign of Risk for Present Value of Future Lossesq-fin.GN

Proves lower discount rates are needed for future losses.

problem Determining appropriate discount rates for future losses.

method Analyzes climate change and discount rates debate.

result Risk requires a lower, not higher, discount rate.

discount rates climate change future losses risk assessment

2022-08-15abs ↗pdf ↗

Hyperbolic Discounting and Learning over Multiple Horizonsstat.ML

Reinforcement learning (RL) typically defines a discount factor as part of the Markov Decision Process. The discount factor values future rewards by an exponential scheme that leads to theoretical convergence guarantees of the Bellman equation. However, evidence from psychology, economics and neuroscience suggests that…

2019-02-19abs ↗pdf ↗

Repo convexityq-fin.PR

There is an observed basis between repo discounting, implied from market repo rates, and bond discounting, stripped from the market prices of the underlying bonds. Here, this basis is explained as a convexity effect arising from the decorrelation between the discount rates for derivatives and bonds. Using a Hull-White …

2019-05-08abs ↗pdf ↗

Discount Modelsq-fin.MF

Proposes a new framework for discount models.

problem Arbitrage-free dynamic framework for discount models.

method Derives general consistency conditions for factor models.

result Alternative to Heath--Jarrow--Morton framework for forward rates.

discount models arbitrage-free dynamic framework factor models forward rates

2023-06-29abs ↗pdf ↗

Learning to Lead: Incentivizing Strategic Agents in the Darkcs.LG

Algorithm learns optimal coordination for strategic agents in uncertain settings.

problem Optimizing rewards for strategic agents with private types and actions.

method Combines delaying mechanism, reward angle estimation, and LinUCB algorithm.

result Near optimal regret bound of

\tilde{O}(\sqrt{T})

for learning optimal policy.

online learning principal-agent problem strategic agents private types rewards

2025-06-10abs ↗pdf ↗

Optimal Spatio-Temporal Decoupling for Bayesian Conformal Predictioncs.LG

SA-BCP combines long-term and local evidence for efficient, adaptive online prediction.

problem Balancing fast adaptation and stable coverage in online prediction.

method State-Adaptive Bayesian Conformal Prediction (SA-BCP) using gated convex combination of temporal inertia and spatial evidence.

result SA-BCP achieves at-or-above-nominal coverage with substantially sharper intervals compared to discounted Bayesian CP.

Bayesian Conformal Prediction Spatio-Temporal Decoupling Online Prediction Volatility Forecasting Kernel Density Estimate

2026-05-01abs ↗pdf ↗