In complex tasks, such as those with large combinatorial action spaces, random exploration may be too inefficient to achieve meaningful learning progress. In this work, we use a curriculum of progressively growing action spaces to accelerate learning. We assume the environment is out of our control, but that the agent …
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 “Large Action Spaces”
Simplifies large action space bandits by selecting representative actions.
problem Efficiently managing large action spaces with correlated outcomes.
method Random sampling and solving of bandit instances to identify representative actions.
result The algorithm selects a smaller set of representative actions that perform nearly as well as the full action space.
Practical algorithm for contextual bandits with large action spaces.
problem Efficient algorithms for decision making in large, continuous action spaces.
method Uses computational oracles for supervised learning and optimization over the action space.
result Achieves sample complexity, runtime, and memory independent of the size of the action space.
Proposes MDR estimator for unbiased OPE with large action spaces.
problem Severe bias and variance tradeoffs in OPE with large action spaces.
method Marginalized Doubly Robust (MDR) estimator, reducing variance and bias.
result MDR estimator is unbiased under weaker assumptions than MIPS.
Introduces Conditional Action Trees to simplify RL action spaces.
problem Challenges in RL with large, complex action spaces.
method Structures action spaces and reduces complexity through Conditional Action Trees.
result Demonstrates effectiveness in reducing action space and improving decision making.
Solves action selection for large spaces in RL, achieving near-optimal performance.
problem Selecting a small, representative subset of actions from a large, shared action space.
method Extends meta-bandit approach to MDPs, using a relaxed sub-Gaussian process model.
result Achieves performance comparable to full action space, with theoretical guarantees.
Unified Bayesian framework for efficient off-policy evaluation and learning in large action spaces.
problem Efficient off-policy evaluation and learning in systems with correlated actions.
method Unified Bayesian framework with structured priors and sDM approach.
result sDM leverages action correlations without compromising computational efficiency.
New OPE estimator improves offline policy evaluation for large action spaces.
problem Existing OPE estimators fail with large action spaces, leading to extreme bias and variance.
method Proposes a new estimator using marginalized importance weights and action embeddings.
result Empirical performance improvement enables reliable OPE even with many actions.
New method minimizes decision errors in large treatment spaces.
problem Improving decision-making in large treatment spaces with biased observational data.
method Loss minimizes classification error of actions in large action space.
result Proves improved decision-making performance in large combinatorial action spaces.
This work tackles large action spaces in RL by binarizing actions.
problem Large action spaces in reinforcement learning cause significant challenges.
method Sequentializing actions and binarizing the action space.
result Binarizing the action space can significantly improve RL algorithms and reduce state space size.
This paper optimizes slate decision systems for large action spaces.
problem Optimizing large-scale decision systems with arbitrary reward functions.
method A policy optimization framework with a novel relaxation of decision functions.
result Demonstrates the effectiveness of the proposed method on large action spaces.
Stochastic Q-learning tackles large action spaces with reduced computation.
problem Effective decision-making in complex environments with large discrete action spaces.
method Stochastic value-based RL approaches that consider a sublinear number of actions in each iteration.
result Stochastic Q-learning achieves near-optimal returns with significantly reduced computation time.
POTEC tackles off-policy learning in large action spaces, improving effectiveness.
problem Existing OPL methods fail in large discrete action spaces due to bias or variance issues.
method Two-stage algorithm: cluster selection via policy-based approach, action selection via regression-based approach.
result POTEC provides substantial improvements in off-policy learning effectiveness, especially in large and structured action spaces.
New findings show optimization is crucial for OPL in large action spaces.
problem Challenges in optimizing policies for large action spaces in offline contextual bandits.
method Weighed log-likelihood objectives and estimator-aware policy parametrization.
result Simple weighted log-likelihood objectives enjoy better optimization properties and recover competitive policies.
New method reduces bias and variance in OPE for large action spaces.
problem High bias and variance in OPE for large, combinatorial action spaces.
method Factored action spaces and decomposed importance sampling.
result Decomposed IS estimators have less variance than non-decomposed versions.
Interactive Fiction games are text-based simulations in which an agent interacts with the world purely through natural language. They are ideal environments for studying how to extend reinforcement learning agents to meet the challenges of natural language understanding, partial observability, and action generation in …
Most model-free reinforcement learning methods leverage state representations (embeddings) for generalization, but either ignore structure in the space of actions or assume the structure is provided a priori. We show how a policy can be decomposed into a component that acts in a low-dimensional space of action represen…
New RL method reduces sample complexity for large state-action spaces.
problem Handling large state-action spaces in RL with general Q-functions.
method Nonparametric Q-learning using kernel ridge regression.
result Sample complexity is order optimal with respect to ε and kernel complexity.
New estimator improves off-policy evaluation for large action spaces.
problem Conventional importance-weighting approaches suffer from excessive variance in off-policy evaluation for large discrete action spaces.
method Proposes OffCEM estimator based on conjunct effect model (CEM), applying importance weighting only to action clusters and using model-based reward estimation for residual effects.
result Proposed estimator is unbiased under local correctness condition, providing substantial improvements in OPE especially with many actions.
New RL method handles large state-action spaces with complex models.
problem Complex models and large state-action spaces in reinforcement learning.
method π-KRVI, an optimistic modification of least-squares value iteration using kernel ridge regression.
result First order-optimal regret guarantees under general settings, improving over state of the art.
Efficient algorithms for contextual bandits with smooth regret in continuous action spaces.
problem Efficient learning in large or continuous action spaces.
method Smooth regret notion and efficient algorithms for general function approximation.
result Statistically and computationally efficient algorithms for contextual bandits with smooth regret.
Being able to reason in an environment with a large number of discrete actions is essential to bringing reinforcement learning to a larger class of problems. Recommender systems, industrial plants and language models are only some of the many real-world tasks involving large numbers of discrete actions for which curren…
The paper shows how contracting elements in groups lead to large quotients with specific growth rates.
problem Understanding the growth rates of group actions with contracting elements.
method Using extension lemma, rotating families theory, and quasi-tree construction.
result There exist sequences of quotient groups with growth rates approaching the original group's growth rate.
Gromov showed that for fixed, arbitrarily large C, any uniformly C-Lipschitz affine action of a random group in his graph model on a Hilbert space has a fixed point. We announce a theorem stating that more general affine actions of the same random group on a Hilbert space have a fixed point. We discuss some aspects of …
We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parame…
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
Survey of group actions on hyperbolic spaces, focusing on mapping class groups and Out(F_n).
problem Understanding the large scale geometry of mapping class groups and Out(F_n) using their actions on hyperbolic spaces.
method Analysis of hyperbolic groups and construction of projection complexes.
result Significant understanding of Out(F_n) lags behind mapping class groups.
This paper proves that there are no compact forms for a large class of homogeneous spaces admitting actions by higher-rank semisimple Lie groups. It builds on Zimmer's approach for studying such spaces using cocycle superrigidity. The proof involves cocycle superrigidity, measure rigidity for unipotent flows, technique…
Word metrics from large balls in injective spaces are exponentially generic and growth tight.
problem Understanding genericity and growth in word metrics from injective spaces.
method Geometric arguments and large ball considerations.
result Exponential genericity and growth tightness for word metrics.
Study boundary actions on CAT(0) spaces, proving topological freeness.
problem Understanding boundary actions on CAT(0) spaces.
method Verification of freeness of Myrberg points on boundaries.
result Large class of boundary actions are topologically free.
Reinforcement learning (RL) has recently been introduced to interactive recommender systems (IRS) because of its nature of learning from dynamic interactions and planning for long-run performance. As IRS is always with thousands of items to recommend (i.e., thousands of actions), most existing RL-based methods, however…
ZoomRL learns efficient strategies for large state-action spaces using a metric.
problem Handling large state-action spaces in reinforcement learning.
method ZoomRL leverages continuous bandits to adaptively discretize the joint space.
result Achieves worst-case regret of $ ilde{O}(H^{ rac{5}{2}} K^{ rac{d+1}{d+2}})$.
Interactive machine learning improves learning efficiency with user input.
problem Expensive, time-consuming, or risky acquisition of labeled data and decision-making.
method Develops new algorithms for active learning, sequential decision making, and model selection under partial feedback.
result First efficient algorithms achieving exponential label savings and independent of action space size.
For a discrete metric space (or more generally a large scale space) and an action of a group on by coarse equivalences, we define a type of coarse quotient space , which agrees up to coarse equivalence with the orbit space when is finite. We then restrict our attention to what we call coarsel…
New method reduces bias in learning from large action spaces using selective importance sampling.
problem Learning from large-scale recommendation systems with bandit feedback and supervised labels.
method Selective Importance Sampling (sIS) and Policy Optimization for eXtreme Models (POXM) algorithm.
result POXM method significantly outperforms existing methods in learning from bandit feedback on XMC tasks.
Study finite group actions on exotic aspherical space forms.
problem Classify finite group actions on where is a closed aspherical space form and is an exotic -sphere.
method Combines geometric and topological rigidity results with smoothing theory and spectral sequence computations.
result Classification of free actions of finite groups on when is 7-dimensional.
We explain how to adapt a construction of M. Sageev's to construct a proper action on a CAT(0) cube complex starting from a proper action on a wall space, and use this to deduce that if G is a group containing an amenable subgroup H of super-polynomial growth and G acts properly on a space with walls then there are arb…
We consider the Markov Decision Process (MDP) of selecting a subset of items at each step, termed the Select-MDP (S-MDP). The large state and action spaces of S-MDPs make them intractable to solve with typical reinforcement learning (RL) algorithms especially when the number of items is huge. In this paper, we present …
New RL method reduces sample complexity for large policy spaces.
problem Large-scale RL with unknown optimal policies and state/action spaces.
method Introduces eluder dimension for policy space, proving near-optimal sample complexity.
result Near-optimal sample complexity upper bound that depends linearly on eluder dimension.
PSI-LinUCB improves scalability for large recommender systems.
problem Efficiently training and inferring for large action spaces in recommender systems.
method Represent inverse design matrix as diagonal + low-rank correction, derive stable rank-1 and batched updates, use projector-splitting integrator.
result Demonstrated effectiveness on recommender system datasets, achieving scalable training and inference.
Efficient algorithms for planning in cooperative multi-agent reinforcement learning with combinatorial action spaces.
problem Planning in cooperative multi-agent reinforcement learning with a combinatorial action space.
method Efficient algorithms using local access to a simulator and linear function approximation, with improvements for additive feature decomposition and kernelized settings.
result Polynomial compute and query complexity in relevant problem parameters.
Contextual bandit methods fail with deficient support data.
problem Learning from support-deficient data in contextual bandits.
method Three approaches to IPS-based learning: action space restriction, reward extrapolation, and policy space restriction.
result Systematic analysis and empirical evaluation of approaches to IPS-based learning.
We rigorously define the Liouville action functional for finitely generated, purely loxodromic quasi-Fuchsian group using homology and cohomology double complexes naturally associated with the group action. We prove that the classical action - the critical point of the Liouville action functional, considered as a funct…
Study boundary actions of CAT(0) spaces and their -algebras.
problem Investigate boundary actions of CAT(0) spaces and their associated -algebras.
method Topological dynamics and -algebras, focusing on actions of specific groups and their properties.
result Established (strongly) pure infiniteness results for reduced crossed product -algebras of boundary actions.
RODE learns roles to simplify multi-agent tasks.
problem Efficiently discovering roles for complex multi-agent tasks.
method Clustering actions based on effects, bi-level learning hierarchy, integrating action effects into role policies.
result RODE outperforms state-of-the-art MARL algorithms on StarCraft II benchmarks.
CAEL-MIPS learns embeddings to improve MIPS for better OPE in contextual bandits.
problem High variance in IPS weighting for OPE in large action spaces.
method Context-Action Embedding Learning (CAEL) for MIPS to minimize MSE.
result CAEL-MIPS outperforms baselines in MSE for OPE in contextual bandits.
We show that the Gromov boundary of the free factor graph for the free group Fn with n>2 generators is the space of equivalence classes of minimal very small indecomposable projective Fn-trees without point stabilizer containing a free factor equipped with a quotient topology. Here two such trees are equivalent if the …
Adaptive discretization improves model-based RL in large spaces.
problem Efficient model-based reinforcement learning in large state-action spaces.
method Optimistic one-step value iteration with adaptive discretization.
result Adaptive discretization leads to better performance and lower memory usage.