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 “Linear function approximation”

Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcs.LG

Entropy-regularized NPG converges linearly with linear function approximation.

problem Analyzing convergence of entropy-regularized NPG with function approximation.

method Established finite-time convergence analyses with entropy regularization and linear function approximation.

result Entropy-regularized NPG achieves linear convergence up to a function approximation error.

entropy regularization natural policy gradient linear function approximation reinforcement learning convergence analysis

2021-06-08abs ↗pdf ↗

A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationstat.ML

Study on distributional TD learning with linear approximations for better return estimation.

problem Estimating the return distribution of a policy in reinforcement learning.

method Finite-sample analysis of distributional TD learning with linear function approximation, using the linear-categorical Bellman equation and exponential stability arguments for products of random matrices.

result Sample complexity of linear distributional TD learning matches that of classic linear TD learning, indicating similar difficulty in estimating return distribution versus its expectation.

distributional reinforcement learning temporal difference learning linear function approximation return distribution Markov decision process

2025-02-20abs ↗pdf ↗

Accelerated Distributional Temporal Difference Learning with Linear Function Approximationstat.ML

New algorithms improve distributional TD learning with linear approximations.

problem Estimating return distributions in reinforcement learning.

method Fine-grained analysis of linear-categorical Bellman equation, variance reduction techniques.

result Tight sample complexity bounds for distributional TD learning with linear approximations.

reinforcement learning temporal difference learning distributional reinforcement linear function approximation variance reduction

2025-11-16abs ↗pdf ↗

Approximation of Nonlinear Functionals Using Deep ReLU Networksstat.ML

Study approximates nonlinear functionals using deep ReLU networks.

problem Approximating nonlinear continuous functionals with neural networks.

method Constructs continuous piecewise linear interpolation under simple triangulation, analyzes rates of approximation.

result Established rates of approximation for functional deep ReLU networks.

Deep ReLU networks Functional approximation Nonlinear functionals Rectified linear unit Triangulation

2023-04-10abs ↗pdf ↗

Global universality via discrete-time signaturesmath.PR

Global approximation for piecewise linear paths via signatures.

problem Global approximation theorems for piecewise linear paths.

method Using signatures of piecewise linear paths and their density in

L^p

-norms.

result Linear functionals of signatures are dense in

L^p

-norms under an integrability condition.

approximation theory piecewise linear paths signatures Brownian motion random ODEs

2026-03-10abs ↗pdf ↗

Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcs.LG

Papers learn from data to make decisions without interacting, improving on previous methods.

problem Achieving optimal decision-making from offline data with non-linear function approximation.

method Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) with three innovative components.

result Achieves minimax optimal instance-dependent regret for non-linear function approximation.

offline reinforcement learning non-linear function approximation value iteration regret bound minimax optimality

2023-10-02abs ↗pdf ↗

Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcs.LG

UCRL2-VTR achieves nearly optimal regret for learning MDPs with linear function approximation.

problem Learning infinite-horizon average-reward MDPs with linear function approximation.

method UCRL2-VTR algorithm with Bernstein-type bonus.

result Achieves a regret of

ilde{O}(d\sqrt{DT})

with matching lower bound.

reinforcement learning MDP average-reward linear function approximation UCRL2-VTR

2021-02-15abs ↗pdf ↗

Target Network and Truncation Overcome The Deadly Triad in

Q

-Learningcs.LG

New methods stabilize Q-learning with linear approximations.

problem Stabilizing

Q

-learning with linear function approximation.

method Target network and truncation.

result Provably stable

Q

-learning with linear function approximation.

Q-learning target network truncation linear function approximation finite-sample guarantees

2022-03-05abs ↗pdf ↗

Provably Efficient Reinforcement Learning with Linear Function Approximationcs.LG

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational …

2019-07-11abs ↗pdf ↗

Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcs.LG

Logarithmic regret achieved in RL with linear function approximation.

problem Achieving logarithmic regret in reinforcement learning with linear function approximation.

method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.

result Logarithmic regret bounds established for RL with linear function approximation.

reinforcement learning logarithmic regret linear function approximation linear MDP UCRL-VTR

2020-11-23abs ↗pdf ↗

Weighted universal approximation of differentiable maps on infinite-dimensional manifoldsmath.FA

Generalizes neural network approximation to infinite-dimensional manifolds and derivatives.

problem Approximating differentiable maps on infinite-dimensional manifolds.

method Proves a weighted Nachbin theorem to establish universal approximation for differentiable maps, including derivatives.

result Linear functions of the signature can approximate path space functionals including their derivatives.

universal approximation differentiable maps infinite-dimensional manifolds derivatives weighted Nachbin theorem

2026-06-08abs ↗pdf ↗

Efficient Planning in Large MDPs with Weak Linear Function Approximationcs.LG

Efficiently plans large MDPs with weak function approximations.

problem Planning in large MDPs with limited function approximation capabilities.

method Uses linear value function approximation with weak requirements and a generative oracle.

result Produces almost-optimal actions for any state with polynomial computation time.

Markov decision processes linear approximation weak function approximation generative oracle almost-optimal actions

2020-07-13abs ↗pdf ↗

Weighted universal approximation of differentiable maps on infinite-dimensional manifoldsmath.FA

Universal approximation theorem for differentiable maps on infinite-dimensional manifolds

problem Approximation of differentiable maps on infinite-dimensional manifolds

method Weighted universal approximation theorem

result Universal approximation theorem for differentiable maps

universal approximation differentiable maps infinite-dimensional manifolds

2026-06-08abs ↗pdf ↗

Piecewise-Linear Approximation for Feature Subset Selection in a Sequential Logit Modelstat.ME

This paper concerns a method of selecting a subset of features for a sequential logit model. Tanaka and Nakagawa (2014) proposed a mixed integer quadratic optimization formulation for solving the problem based on a quadratic approximation of the logistic loss function. However, since there is a significant gap between …

2015-10-19abs ↗pdf ↗

Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcs.LG

New algorithm FLUTE achieves uniform-PAC convergence in RL with linear approx.

problem RL with linear function approximation lacks uniform-PAC guarantees.

method FLUTE algorithm with minimax value function estimator and multi-level partition scheme.

result Uniform-PAC convergence to optimal policy with high probability.

reinforcement learning linear function approximation uniform-PAC minimax value function multi-level partition

2021-06-22abs ↗pdf ↗

Going Beyond Linear RL: Sample Efficient Neural Function Approximationcs.LG

This work improves sample efficiency in neural function approximation for reinforcement learning.

problem Improving sample efficiency in reinforcement learning with neural function approximation.

method Study of function approximation with two-layer neural networks (ReLU and polynomial activations) under generative and realizability models.

result Significant improvement in sample complexity compared to linear methods.

Reinforcement Learning Neural Networks Function Approximation Sample Efficiency Two-Layer Networks

2021-07-14abs ↗pdf ↗

Provably Correct Optimization and Exploration with Non-linear Policiescs.LG

ENIAC method optimizes and explores complex RL problems with non-linear policies.

problem Theoretical understanding of non-linear policies in RL with strategic exploration.

method ENIAC, an actor-critic method for non-linear function approximation.

result ENIAC finds near-optimal policies in polynomial exploration rounds under bounded eluder dimension.

Reinforcement Learning Policy Optimization Non-linear Function Approximation Strategic Exploration Actor-Critic

2021-03-22abs ↗pdf ↗

Provably Efficient

Q

-learning with Function Approximation via Distribution Shift Error Checking Oraclecs.LG

$Q$ -learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, approximating $Q$ -functions with linear functions, it is still an open problem on how to design a pr…

2019-06-14abs ↗pdf ↗

Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programscs.LG

Recently, Petrik et al. demonstrated that L1Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP's success primarily stems from the ability to solve the feature selection and va…

2012-10-16abs ↗pdf ↗

Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecs.LG

New algorithm for offline RL with linear approx in MDPs and MGs, nearly optimal.

problem Offline RL with linear function approximation in MDPs and MGs.

method Pessimism-based algorithm with uncertainty decomposition via reference function.

result Nearly minimax optimal performance in offline RL for MDPs and MGs.

Offline RL Linear function approximation MDP MG Pessimism

2022-05-31abs ↗pdf ↗

Nonstationary Reinforcement Learning with Linear Function Approximationcs.LG

New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.

problem Nonstationary reinforcement learning with evolving reward and state transition functions.

method Developed a new algorithm LSVI-UCB-Restart with periodic restart, and parameter-free Ada-LSVI-UCB-Restart for unknown variation budgets.

result First minimax dynamic regret lower bound for nonstationary linear MDPs and linear MDPs lower bound.

reinforcement learning nonstationary linear function approximation dynamic regret optimistic algorithms

2020-10-08abs ↗pdf ↗

On Gaussian approximation for entropy-regularized Q-learning with function approximationstat.ML

The paper analyzes the convergence rates of Q-learning with entropy regularization and linear function approximation.

problem Analyzing the convergence rates of Q-learning with entropy regularization and linear function approximation.

method The paper derives rates of convergence using the high-dimensional central limit theorem, linearization of the soft Bellman recursion, and Gaussian approximation for the leading martingale term.

result The algorithm's last iterate satisfies high-order moment bounds, with a Gaussian approximation bound of order

n^{-1/4}

Q-learning entropy regularization linear function approximation convergence rates Gaussian approximation

2026-05-17abs ↗pdf ↗

A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noisestat.ML

Stochastic differential equation approximation for linear TD(0) under Markovian noise

problem Temporal-difference learning with linear function approximation

method Stochastic differential equation approximation

result Explains the constant-stepsize error floor

TD learning linear function approximation Markovian noise stochastic differential equation

2026-06-16abs ↗pdf ↗

Growing axons: greedy learning of neural networks with application to function approximationcs.LG

We propose a new method for learning deep neural network models that is based on a greedy learning approach: we add one basis function at a time, and a new basis function is generated as a non-linear activation function applied to a linear combination of the previous basis functions. Such a method (growing deep neural …

2019-10-28abs ↗pdf ↗

An analysis of linear regression and neural networks approximation for the pricing of swing optionsq-fin.MF

This paper compares linear regression and neural networks for pricing swing options.

problem Pricing swing options using approximation methods.

method Linear regression and neural networks for approximating the continuation value and swing price.

result The approximation methods converge to the actual swing price as the number of functions or Monte Carlo samples increases.

swing options pricing linear regression neural networks approximation

2023-07-10abs ↗pdf ↗

Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationstat.ML

Improved gap-dependent bounds for reinforcement learning with linear approximations.

problem Achieving nearly minimax-optimal performance with linear function approximation.

method Developed and analyzed the LSVI-UCB++ algorithm and its concurrent variant.

result First gap-dependent regret bound for nearly minimax-optimal algorithm LSVI-UCB++.

reinforcement learning linear function approximation gap-dependent bounds LSVI-UCB++

2026-02-23abs ↗pdf ↗

Planning to avoid ambiguous states through Gaussian approximations to non-linear sensors in active inference agentseess.SY

Agents learn state ambiguity from non-linear sensor data using Gaussian approximations.

problem Learning state representation from non-linear sensor data.

method Second-order Taylor approximation of Gaussian distribution for non-linear measurement functions.

result Induces a preference for states based on inferability from observations.

active inference robot navigation state ambiguity Gaussian approximation Taylor expansion

2024-09-03abs ↗pdf ↗

Global universal approximation of functional input maps on weighted spacesstat.ML

Functional input neural networks approximate continuous functions on weighted spaces.

problem Approximating continuous functions on infinite-dimensional weighted spaces.

method Additive family mapping, non-linear activation, linear readouts, Stone-Weierstrass theorem.

result Global universal approximation of continuous functions on weighted spaces.

functional input neural networks weighted spaces Stone-Weierstrass theorem universal approximation path space functionals

2023-06-05abs ↗pdf ↗

On Reward-Free Reinforcement Learning with Linear Function Approximationcs.LG

New algorithm for reward-free RL with linear function approximation, reducing sample complexity.

problem Efficiently learning optimal policies without prior reward information in complex environments.

method Developed an algorithm for reward-free RL in linear Markov decision processes, proving sample complexity bounds.

result Polynomial sample complexity in feature dimension and planning horizon, independent of states and actions.

reinforcement learning reward-free linear function approximation Markov decision processes sample complexity

2020-06-19abs ↗pdf ↗

When Hardness of Approximation Meets Hardness of Learningcs.LG

This work connects hardness of approximation and learning.

problem Hardness of approximation and learnability in machine learning.

method Shows a single hardness property implying both approximation and learning hardness.

result Obtains new results on hardness of approximation and learnability of specific functions.

hardness of approximation hardness of learning supervised learning linear classifiers neural networks

2020-08-18abs ↗pdf ↗

High-probability sample complexities for policy evaluation with linear function approximationstat.ML

The paper analyzes the sample complexities for policy evaluation with linear function approximation.

problem Policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes.

method Investigates sample complexities for two policy evaluation algorithms: TD and TDC.

result Establishes high-probability sample complexity bounds for policy evaluation algorithms.

policy evaluation linear function approximation Markov decision processes temporal difference learning two-timescale linear TD

2023-05-30abs ↗pdf ↗

Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcs.LG

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.

regret bounds stochastic shortest path linear function approximation stationary policies

2021-05-04abs ↗pdf ↗

Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcs.LG

New algorithms for learning MDPs with linear approximations in infinite-horizon settings.

problem Learning infinite-horizon average-reward MDPs with linear function approximation.

method Optimism principle, adversarial linear bandits, Natural Policy Gradient.

result Efficient algorithms with optimal or near-optimal regret bounds.

Markov Decision Processes Linear Function Approximation Adversarial Linear Bandits Optimism Principle Natural Policy Gradient

2020-07-23abs ↗pdf ↗

Reparameterization invariance in approximate Bayesian inferencecs.LG

The paper addresses the invariance issue in Bayesian neural networks using linearized Laplace approximation.

problem Bayesian neural networks fail to maintain invariance under reparameterization, leading to different posterior densities for identical functions.

method Developed a geometric view of reparameterizations and a Riemannian diffusion process to extend reparameterization invariance to neural network predictive.

result Empirically improved posterior fit through approximate posterior sampling.

Bayesian neural networks reparameterization invariance linearized Laplace approximation Riemannian diffusion posterior sampling

2024-06-05abs ↗pdf ↗

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscs.LG

Polynomial-time RL algorithm for constant actions under linear Bellman completeness.

problem Efficient online reinforcement learning with few actions.

method Polynomial-time algorithm based on linear function approximation.

result First computationally efficient algorithm for RL with constant actions under linear Bellman completeness.

reinforcement learning online learning value iteration linear function approximation polynomial-time algorithm

2024-06-17abs ↗pdf ↗

Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcs.LG

The paper analyzes the sample complexity of offline RL with linear approximations, identifying a hard regime and providing an algorithm.

problem Sample complexity of policy evaluation in infinite-horizon offline reinforcement learning with linear function approximation.

method Identification of a hard regime and construction of hard instances; algorithm with sample complexity bound.

result An algorithm that guarantees approximation to the value function up to an additive error of ε with high probability.

offline reinforcement learning infinite-horizon sample complexity linear function approximation hard regime

2021-03-17abs ↗pdf ↗

Global universal approximation with Brownian signaturesmath.PR

Universal approximation for stochastic processes using Brownian motion.

problem Approximating stochastic processes with linear functionals.

method Establishing

L^p

-type universal approximation theorems for rough path spaces.

result Linear functionals on the signature of time-extended Brownian motion can approximate any

p

-integrable stochastic process.

universal approximation rough paths stochastic processes Brownian motion signature

2025-12-18abs ↗pdf ↗

SKOLR: Structured Koopman Operator Linear RNN for Time-Series Forecastingcs.LG

SKOLR uses linear RNNs to approximate Koopman operators for time-series forecasting.

problem Nonlinear dynamical system analysis and time-series forecasting with infinite-dimensional Koopman operators.

method Established a connection between Koopman operator approximation and linear RNNs, integrating learnable spectral decomposition and MLP.

result SKOLR delivers exceptional performance in various forecasting benchmarks and dynamical systems.

Koopman operator time-series forecasting Recurrent Neural Networks linear approximation spectral decomposition

2025-06-17abs ↗pdf ↗

Measuring Model Complexity of Neural Networks with Curve Activation Functionscs.LG

Paper proposes LANN to measure model complexity of neural networks with curve activation functions.

problem Measuring model complexity of neural networks with curve activation functions.

method Proposes LANN, a piecewise linear framework to approximate curve activation functions, and derives complexity measure based on the number of linear regions.

result Demonstrates positive correlation between overfitting and model complexity during training.

model complexity neural networks curve activation functions LANN overfitting

2020-06-16abs ↗pdf ↗

Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncs.LG

Paper develops efficient RL algorithm for general value function approximation.

problem Lack of theory for RL with general value function approximation.

method Provable efficient RL algorithm using bounded eluder dimension.

result Achieves a regret bound of

\widetilde{O}(\mathrm{poly}(dH)\sqrt{T})

Reinforcement Learning Value Function Approximation Regret Bound Bounded Eluder Dimension Model-Free Algorithm

2020-05-21abs ↗pdf ↗

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcs.LG

New algorithms for RL in Markov games with independent linear function approximation, breaking the curse of multiagents.

problem Tackles the challenge of learning Markov equilibria in large state space Markov games with multiple agents.

method Proposes independent linear Markov games and designs new algorithms for learning Markov coarse correlated equilibria and Markov correlated equilibria with polynomial sample complexity.

result Breaks the curse of multiagents by achieving sample complexity bounds that scale polynomially with each agent's function class complexity.

reinforcement learning Markov games multiagent systems function approximation Markov equilibria

2023-02-07abs ↗pdf ↗

Approximating maps into manifolds with lower curvature boundsmath.NA

Algorithm approximates functions into manifolds with curvature bounds.

problem Approximating functions into manifolds with lower curvature bounds.

method Algorithm using manifold exponential and logarithm, with error bounds based on sectional curvature.

result Error bounds for nonnegative sectional curvature are similar to linear space approximations.

manifold approximation curvature bounds Riemannian manifolds sectional curvature Julia package

2024-03-25abs ↗pdf ↗

Prior-dependent analysis of posterior sampling reinforcement learning with function approximationstat.ML

Enhances RL with function approximation, improving regret bounds.

problem Improving exploration in reinforcement learning with function approximation.

method Prior-dependent Bayesian regret bound for PSRL with linear mixture MDPs, using value-targeted model learning and variance reduction.

result Established an upper bound of

{\mathcal{O}}(d\sqrt{H^3 T \log T})

for PSRL.

reinforcement learning function approximation PSRL Bayesian regret linear mixture MDPs

2024-03-17abs ↗pdf ↗

Q

L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcs.LG

VO $Q$ L optimizes RL with sparse rewards using weighted bounds.

problem Sparse rewards and non-linear function approximation in RL.

method VO

Q

L combines

Q

-learning with weighted bounds for optimal regret.

result Achieves asymptotically optimal regret for linear function approximation.

Reinforcement Learning Optimal Regret Sparse Rewards Non-linear Approximation Weighted Bounds

2022-12-12abs ↗pdf ↗

Computational-Statistical Gaps in Reinforcement Learningcs.LG

New lower bound shows RL with linear approximations is computationally hard.

problem Computational hardness in reinforcement learning with linear function approximation.

method Reduction from Unique-Sat to MDPs with linear optimal value functions.

result No randomized polynomial time algorithm exists for RL with linear function approximation unless NP=RP.

reinforcement learning computational hardness linear function approximation NP=RP reduction

2022-02-11abs ↗pdf ↗

Converting MLPs into Polynomials in Closed Formcs.LG

Closed-form polynomial approximations replace MLPs in transformers, enabling new interpretability methods.

problem Replacing MLPs with polynomial approximations for transformer models.

method Theoretical derivation of closed-form least-squares approximations of MLPs and GLUs using polynomial functions.

result Polynomial approximations explain over 95% of MLP and GLU outputs' variance, enabling interpretability.

transformers MLP polynomial approximation interpretability SVD

2025-02-03abs ↗pdf ↗

Optimism in Reinforcement Learning with Generalized Linear Function Approximationstat.ML

We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closure," which is strictly weaker than assumptions from prior analyses for the linear setting. With opti…

2019-12-09abs ↗pdf ↗

Variance-Aware Off-Policy Evaluation with Linear Function Approximationcs.LG

VA-OPE improves OPE by incorporating variance information, achieving tighter error bounds.

problem Estimating value function of a target policy from offline data collected by a behavior policy.

method Proposes VA-OPE, an algorithm that reweights Bellman residual using estimated variance of the value function.

result Achieves a tighter error bound than the best-known result.

reinforcement learning off-policy evaluation linear function approximation variance-aware Fitted Q-Iteration

2021-06-22abs ↗pdf ↗