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.
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
Study excess logarithmic residues for foliations to bound invariant hypersurfaces and test log canonicity.
problem Bounding invariant hypersurfaces and testing log canonicity of singularities.
method Introduce excess logarithmic residues, prove residue formula, derive Poincaré-type bound, and use them to recover log discrepancies.
result Componentwise logarithmic residues of a lifted foliation along the exceptional divisor recover log discrepancies of singularities.
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
New bounds for Bayesian bandits show prior improves performance.
problem Improving regret bounds for Bayesian bandits.
method Upper confidence bound algorithm with finite-time logarithmic regret bounds.
result Derives O ( c Δ log n ) O(c_Δ\log n) O ( c Δ log n ) and O ( c h log 2 n ) O(c_h \log^2 n) O ( c h log 2 n ) upper bounds for Bayesian bandits. 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.
For word-equations in groups, we find a logarithmic bound on non-solutions.
problem Finding the length of non-solutions to word-equations in groups.
method Analyzing finite-rank free groups and applying results to broader classes of groups.
result Logarithmic bound on non-solutions for word-equations in groups.
This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistence, and e…
The systole of a hyperbolic surface is bounded by a logarithmic function of its genus. This bound is sharp, in that there exist sequences of surfaces with genera tending to infinity that attain logarithmically large systoles. These are constructed by taking congruence covers of arithmetic surfaces. In this article we p…
Directly proves logarithmic systolic growth for all hyperbolic surfaces.
problem Proving logarithmic systolic growth for all hyperbolic surfaces.
method Using original Brooks/Buser-Sarnak surfaces through a direct approach.
result Directly proves logarithmic systolic growth for all hyperbolic surfaces.
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.
This work improves policy evaluation and selection using logarithmic smoothing for pessimistic off-policy estimation.
problem Offline evaluation and selection of policies from past data.
method Develops novel concentration bounds and a logarithmically smoothed estimator (LS) for improved policy selection and learning.
result The logarithmically smoothed estimator (LS) provides tighter bounds and better policy selection and learning.
This paper tightens the law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
problem Developing nonasymptotic concentration bounds for empirical KL_inf with optimal constants and rates.
method Presenting a tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
result A tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
Sharp upper diameter limit found for Ricci solitons.
problem Bounding the diameter of compact shrinking Ricci solitons.
method Used a sharp logarithmic Sobolev inequality and Vitali-type covering argument.
result Sharp upper diameter bound established in terms of scalar curvature and entropy.
We give concentration bounds for martingales that are uniform over finite times and extend classical Hoeffding and Bernstein inequalities. We also demonstrate our concentration bounds to be optimal with a matching anti-concentration inequality, proved using the same method. Together these constitute a finite-time versi…
Optimizes quantile and semi-adversarial regret with novel root-logarithmic regularizers.
problem Minimizes regret in adversarial and semi-adversarial online learning.
method FTRL with root-logarithmic regularizers for quantile and semi-adversarial settings.
result Achieves minimax optimal regret bounds in both paradigms.
Study bounds for Brownian motion on manifolds with sticky boundary conditions.
problem Proving geometric bounds for Brownian motion on manifolds with sticky boundary conditions.
method Interpolation involving energy interactions between boundary and interior of the manifold.
result Explicit geometric bounds on Steklov eigenvalues, boundary trace operators, and boundary trace logarithmic Sobolev constants.
Upper bound established for the length of shortest closed geodesics in hyperbolic link complements.
problem Finding bounds on the length of shortest closed geodesics in hyperbolic link complements.
method Established an upper bound for the length of an nth shortest closed geodesic as a logarithmic function of the volume of the manifold.
result An upper bound of the length of an nth shortest closed geodesic is established as a logarithmic function of the volume of the manifold.
Finite-time queue peaks in stochastic networks have logarithmic scaling after geometric thresholds.
problem Queue peak laws in stochastic networks with geometric thresholds.
method Self-normalization mechanism
result Logarithmic scaling of queue peaks after geometric thresholds.
Bounding shears in ideal triangulations on hyperbolic surfaces.
problem Bounding shears in ideal triangulations on hyperbolic surfaces.
method Showing an ideal triangulation with bounded shear parameters on hyperbolic surfaces.
result An upper bound on shear parameters depends logarithmically on the surface's topology.
Study heat flow on changing surfaces, proving existence and uniqueness.
problem Existence and uniqueness of heat flow on time-varying manifolds.
method Establishes estimates for heat flow under minimal assumptions, focusing on logarithmic derivative of volume measure.
result Proves estimates hold for Ricci flow with scalar curvature bounded below, dependent only on initial data.
This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…
New Thompson sampling algorithm for stochastic partial monitoring achieves logarithmic regret.
problem Limited feedback in sequential learning problems.
method Developed a novel Thompson-sampling-based algorithm to sample from the posterior distribution exactly.
result Achieved logarithmic regret bound of O(log T) for a linearized variant of the problem.
We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the …
Proves upper bounds for heat kernels evolving on manifolds.
problem Bounding heat kernels on evolving manifolds.
method Logarithmic Sobolev inequalities and ultracontractivity estimates.
result Gaussian upper bounds for heat kernels are derived.
We develop a new theoretical framework, the \emph{envelope complexity}, to analyze the minimax regret with logarithmic loss functions and derive a Bayesian predictor that adaptively achieves the minimax regret over high-dimensional ℓ 1 \ell_1 ℓ 1 -balls within a factor of two. The prior is newly derived for achieving the mini…
New bounds for online portfolio selection without smoothness assumptions.
problem Online portfolio selection with non-Lipschitz, non-smooth losses.
method Data-dependent bounds using novel smoothness characterizations and FTRL with self-concordant regularizers.
result Achieves logarithmic regrets when data is 'easy' and sublinear worst-case regrets.
Method calculates systolic length of modular curves.
problem Computing upper bounds on systolic length of Riemann surfaces.
method Using congruence subgroups of hyperbolic triangle groups and traces of generators.
result Systolic length grows logarithmically with genus.
Ancient Ricci flows with asymptotic solitons have uniform bounds and inequalities.
problem Bounding and understanding ancient Ricci flows with asymptotic solitons.
method Analyzing asymptotic solitons, proving uniform bounds on Perelman's ν-functional, and showing Nash entropy bounds.
result Uniform bounds on Perelman's ν-functional and logarithmic/Sobolev inequalities for ancient solutions.
Adaptive gradient methods have become recently very popular, in particular as they have been shown to be useful in the training of deep neural networks. In this paper we have analyzed RMSProp, originally proposed for the training of deep neural networks, in the context of online convex optimization and show T \sqrt{T} T -…
The study improves bounds on the number of closed geodesics and logarithmic improvements in the Weyl law.
problem Estimating the number of closed geodesics and improving logarithmic bounds in the Weyl law.
method Study of non-degeneracy properties of nearly closed orbits for predominant sets of metrics.
result Logarithmic improvements in the Weyl law and exponential bounds on the number of closed geodesics.
We investigate optimal consumption problems for a Black-Scholes market under uniform restrictions on Value-at-Risk and Expected Shortfall for logarithmic utility functions. We find the solutions in terms of a dynamic strategy in explicit form, which can be compared and interpreted. This paper continues our previous wor…
Uniform heat kernel and diffusion bridge asymptotics for sub-Riemannian geometry.
problem Analyzing sub-Riemannian heat kernels and their derivatives on incomplete manifolds.
method Localized asymptotic analysis, focusing on minimizing geodesics and the non-abnormal cut locus.
result Uniform bounds and expansions for heat kernels and their derivatives on compacts, including the diffusion bridge measure.
Intertwining curvature bounds for graphs and quantum Markov semigroups verified.
problem Intertwining curvature bounds for graphs and quantum Markov semigroups.
method Introducing and verifying curvature bounds in various examples.
result Improved entropic curvature bounds for depolarizing semigroups and qubits.
Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
problem Near-optimal federated Q-learning with low communication cost.
method Reference-advantage decomposition for variance reduction, synchronization between agents and server, policy update.
result Achieves almost optimal regret and near-linear regret speedup compared to single-agent learning.
Paper analyzes and improves KL-regularized RL for LLMs with logarithmic regret.
problem Improving efficiency of RL fine-tuning for large language models.
method Optimism-based KL-regularized online contextual bandit algorithm with novel regret analysis.
result Achieves an O ( η log ( N R T ) ⋅ d R ) \mathcal{O}\big(η\log (N_{\mathcal R} T)\cdot d_{\mathcal R}\big) O ( η log ( N R T ) ⋅ d R ) logarithmic regret bound. Paper proves tight lower bounds for online multicalibration, separating it from marginal calibration.
problem Proving lower bounds for online multicalibration in relation to marginal calibration.
method Information-theoretic approach, constructing group families from orthonormal bases.
result Establishes tight lower bounds for online multicalibration, matching upper bounds up to logarithmic factors.
Logarithmic regret achieved in continuous-time linear-quadratic reinforcement learning.
problem Optimizing control actions in unknown continuous-time systems over a finite time horizon.
method Least-squares algorithm based on continuous-time observations and controls, with perturbation analysis and parameter estimation error analysis.
result Logarithmic regret bound of order O ( ( ln M ) ( ln ln M ) ) O((\ln M)(\ln\ln M)) O (( ln M ) ( ln ln M )) . We study the Seiberg-Witten equations on surfaces of logarithmic general type. First, we show how to construct irreducible solutions of the Seiberg-Witten equations for any metric which is "asymptotic" to a Poincaré type metric at infinity. Then we compute a lower bound for the L 2 L^{2} L 2 -norm of scalar curvature on these…
Random surfaces with long systoles created from graph theory ideas.
problem Finding surfaces with long systoles.
method Two constructions inspired by graph theory.
result Proved a new lower bound on systole length.
We give tight concentration bounds for mixtures of martingales that are simultaneously uniform over (a) mixture distributions, in a PAC-Bayes sense; and (b) all finite times. These bounds are proved in terms of the martingale variance, extending classical Bernstein inequalities, and sharpening and simplifying prior wor…
Logarithmic pruning simplifies lottery ticket hypothesis.
problem Finding efficient subnetworks in large neural networks.
method Logarithmic pruning approach to identify subnetworks.
result Randomly initialized subnetworks achieve comparable performance.
We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as T \sqrt{T} T unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitra…
Derives gradient estimate for a specific nonlinear parabolic equation on Finsler manifolds.
problem Derives gradient estimate for a nonlinear parabolic equation on Finsler manifolds.
method Leverages a new Laplacian comparison theorem to derive a Li-Yau type gradient estimate.
result Establishes a Li-Yau type gradient estimate for the Finslerian logarithmic Schrödinger equation.
Study sparsity benefits in infinite feature contextual bandits.
problem Minimizing regret in infinite feature contextual bandits.
method Novel reduction to multi-armed bandits, Feel-Good Thompson Sampling algorithm.
result Regret bounds match lower bounds up to logarithmic factors, logarithmic dependence on effective features.
New bounds on adaptivity cost in stochastic optimization.
problem Understanding the cost of changing strategies in stochastic optimization.
method Proving impossibility results for adaptivity in non-smooth stochastic convex optimization.
result Lower bounds on the price of adaptivity for different levels of uncertainty.
Study Kähler-Einstein potentials on stable varieties near singularities
problem Asymptotic behavior of Kähler-Einstein potentials on stable varieties near singularities
method Using iterated logarithmic functions and refined lower bounds
result Improved estimates for Kähler-Einstein potentials
Study rigidity of spectral gap on Finsler manifolds with specific curvature bounds.
problem Rigidity of spectral gap on Finsler manifolds with Ricci curvature bound.
method Analysis of spectral gap, splitting phenomena, and needle decomposition.
result Rigidity results for spectral gap, logarithmic Sobolev, and Bakry-Ledoux inequalities.