We use the combinatorial harmonic map theory to study the isometric actions of discrete groups on Hadamard spaces. Given a finitely generated group acting by automorphisms, properly discontinuously and cofinitely on a simplicial complex and its isometric action on a Hadamard space, we formulate criterions for the actio…
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,922 papers · 148 categories
Trend · papers per month
48 results for “combinatorial actions”
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.
The paper tackles combinatorial pure exploration with various feedback structures and proposes efficient algorithms.
problem Identifying the optimal action in a combinatorial space with limited feedback and nonlinear rewards.
method Designs polynomial-time adaptive algorithms for CPE-BL and CPE-PL, providing sample complexity analyses.
result The proposed algorithms achieve sample complexity close to lower bounds and outperform existing methods.
We consider the problem of online combinatorial optimization under semi-bandit feedback, where a learner has to repeatedly pick actions from a combinatorial decision set in order to minimize the total losses associated with its decisions. After making each decision, the learner observes the losses associated with its a…
Math verifies Aganagic's proposal for Khovanov homology.
problem Recovering Khovanov homology from braid group action on Fukaya-Seidel categories.
method Direct calculation of containment between combinatorially defined braid group actions.
result Mathematical verification of Aganagic's proposal for Khovanov homology.
This paper extends combinatorial semi-bandits to graph feedback, improving regret bounds.
problem Adversarial combinatorial semi-bandits with graph feedback.
method Introduced graph feedback in combinatorial semi-bandits, using convexified actions and online stochastic mirror descent.
result Optimal regret scales as , interpolating between full and semi-bandit feedback.
In many practical problems, a learning agent may want to learn the best action in hindsight without ever taking a bad action, which is significantly worse than the default production action. In general, this is impossible because the agent has to explore unknown actions, some of which can be bad, to learn better action…
Homologically trivial symplectic cyclic actions need not extend to Hamiltonian circle actionsmath.SG
We give examples of symplectic actions of a cyclic group, inducing a trivial action on homology, on four-manifolds that admit Hamiltonian circle actions, and show that they do not extend to Hamiltonian circle actions. Our work applies holomorphic methods to extend combinatorial tools developed for circle actions to stu…
Paper tackles combinatorial reinforcement learning with preference feedback.
problem Modeling long-term user engagement in scenarios like recommender systems and online advertising.
method Assumes a contextual MNL preference model with linear mean utilities and approximates item values. Proposes MNL-VQL algorithm.
result Achieves nearly minimax-optimal regret for linear MDPs with preference feedback.
A framework for reinforcement learning tackles CVRP with competitive results.
problem Optimizing routes for vehicles with limited capacity.
method Formulates action selection as a mixed-integer optimization problem, uses policy iteration to improve policies.
result Achieves an average gap of 1.7% with state-of-the-art OR methods on CVRP instances.
Deep RL learns to construct objects from 2D images by avoiding brick overlaps.
problem Learning to construct objects from partial 2D images with constraints.
method Combination of reinforcement learning and action validity prediction.
result Successfully constructs unseen objects from 2D images.
KG-A2C agent learns natural language IF games by reasoning and constraining action spaces.
problem Challenges of natural language understanding, partial observability, and combinatorially large action spaces in IF games.
method Builds a dynamic knowledge graph while exploring, constraining actions using templates.
result Outperforms current IF agents across various games with larger action spaces.
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
We describe an algorithm for the enumeration of (candidates of) vertex-transitive combinatorial -manifolds. With an implementation of our algorithm, we determine, up to combinatorial equivalence, all combinatorial manifolds with a vertex-transitive automorphism group on vertices. With the exception of act…
Algorithm optimizes bandit decisions with changing action sets using Gaussian processes.
problem Optimizing decisions in a bandit problem with time-varying action sets.
method Proposes an algorithm called O'CLOK-UCB using Gaussian processes to handle changing action sets and contexts.
result Achieves regret bound of with high probability.
New algorithm identifies optimal actions in large reward spaces efficiently.
problem Finding the best action from a large set of options with minimal trials.
method GenTS-Explore algorithm for real-valued combinatorial pure exploration.
result Achieves optimal sample complexity for large action sets.
The paper surveys some new results and open problems connected with such fundamental combinatorial concepts as polytopes, simplicial complexes, cubical complexes, and subspace arrangements. Particular attention is paid to the case of simplicial and cubical subdivisions of manifolds and, especially, spheres. We describe…
The paper studies quaternionic structures on GKM graphs and their relation to torus actions on quaternionic projective spaces.
problem Understanding quaternionic structures on GKM graphs and their implications for torus actions.
method Introducing quaternionic structures on GKM graphs and analyzing their properties in the context of torus actions.
result Abstract GKM graphs with specific 2-face structures correspond to torus actions on quaternionic projective spaces or Grassmannians.
A transitive smooth action of a connected Lie group G on a manifold M is called almost primitive (resp. primitive) if G doesn't contain any proper subgroup (resp. any proper normal subgroup) whose induced action on M is transitive as well. The aim of the present work is to investigate some combinatory properties of sym…
Deep RL solves combinatorial selection problems with large item spaces.
problem Solving MDPs with large state and action spaces, especially for combinatorial selection.
method Convert S-MDP to IS-MDP, use weight-shared Q-networks to manage state space explosion.
result Our approach effectively handles large item spaces and scales to diverse environments.
We give a complete classification of irreducible symmetric spaces for which there exist proper SL(2,R)-actions as isometries, using the criterion for proper actions by T. Kobayashi [Math. Ann. '89] and combinatorial techniques of nilpotent orbits. In particular, we classify irreducible symmetric spaces that admit surfa…
This paper has been withdrawn by the author. Improved versions (arXiv:1109.5548 and arXiv:0708.4190) are accepted.
New method for evaluating and learning in complex decision-making scenarios.
problem Evaluating and learning from policies in contextual combinatorial bandits with high bias and variance.
method Factored action space decomposition and importance sampling-based estimator (OPCB).
result OPCB achieves superior performance in OPE and OPL compared to conventional methods.
A deep Q-learning strategy optimizes portfolio trading efficiency.
problem Optimizing dynamic portfolio allocation schemes.
method Formulated a Markov decision process model with deep Q-learning for discrete combinatorial actions.
result Outperforms benchmark strategies in real-world trading simulations.
We present in this article a family of new combinatorial identities via purely differential/complex geometry methods, which include as a speical case a unified and explicit formula for Chern numbers of all complex flag manifolds. Our strategy is to construct concrete circle actions with isolated fixed points on these m…
One can define what it means for a compact manifold with corners to be a "contractible manifold with contractible faces." Two combinatorially equivalent, contractible manifolds with contractible faces are diffeomorphic if and only if their 4-dimensional faces are diffeomorphic. It follows that two simple convex polytop…
Improved statistical efficiency of Thompson Sampling for combinatorial semi-bandits.
problem Efficiency of policies in stochastic combinatorial multi-armed bandits with semi-bandit feedback.
method Analysis of Combinatorial Thompson Sampling (CTS) using Beta and Gaussian priors for mutually independent and multivariate sub-Gaussian outcomes.
result CTS provides an efficient policy with optimal asymptotic regret for both mutually independent and multivariate sub-Gaussian outcomes.
Let X=G/P be a homogeneous space of a complex semisimple Lie group G equipped with a hermitian metric. We study the action of the Hodge star operator on the space of harmonic differential forms on X. We obtain explicit combinatorial formulas for this action when X is an irreducible hermitian symmetric space of compact …
Paper solves no-swap regret minimization for combinatorial bandits with polylogarithmic dependence on N.
problem Design efficient no-swap regret algorithms for combinatorial bandits with exponentially large action space.
method Introduces a no-swap-regret learning algorithm with polylogarithmic dependence on N and demonstrates efficient implementation.
result Achieves no-swap regret with polylogarithmic dependence on N, resolving an open problem.
SRL embeds combinatorial optimization into RL for better decision-making.
problem Challenges of standard RL in complex, structured decision-making problems.
method Structured Reinforcement Learning (SRL) with combinatorial optimization layers in actor neural network.
result SRL outperforms unstructured RL and imitation learning by up to 92% on dynamic problems.
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
We address online combinatorial optimization when the player has a prior over the adversary's sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based on the information ratio, resulting in optimal worst-case regret bounds. In this paper we introduce…
Combinatorial Neural Banditsstat.ML
New algorithms for neural bandits learn from context and arm features.
problem Learning from context and arm features in combinatorial bandit problems.
method Proposed algorithms CN-UCB and CN-TS using deep neural networks.
result Achieved regret guarantees for the first time in combinatorial neural bandits.
Growing action spaces accelerates learning in complex tasks.
problem Efficient learning in tasks with large combinatorial action spaces.
method Curriculum of progressively growing action spaces, off-policy reinforcement learning, data transfer.
result Efficacy demonstrated in control tasks and large-scale StarCraft tasks.
A small cover was introduced by Davis and Januszkiewicz as an -dimensional closed manifold with a locally standard -action such that its orbit space is a simple convex polytope. There exist a one-to-one correspondence between small covers and -colored polytopes. In this paper we study a construction…
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.
Deep network predicts action sequences for complex tasks from a scene image.
problem Scalable task and motion planning from initial scene images.
method Deep convolutional recurrent neural network that predicts action sequences.
result Predicts promising action sequences, reducing motion planning problems.
CRB tackles rising rewards in combinatorial online learning.
problem Rising rewards in combinatorial online learning.
method CRB framework and CRUCB algorithm.
result Empirical and theoretical validation of CRUCB's effectiveness.
Fixed point sets of certain group actions are contractible.
problem Fixed point sets of group actions on specific types of complexes.
method Analyzing group actions on diagrammatically reducible complexes with fine 1-skeleton.
result Fixed point sets are contractible under certain conditions.
We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses. This naturally models several situations where the losses of different actions are related, and knowing the loss of one action p…
This paper contains some more results on the topology of a nondegenerate action of on a compact connected -manifold when the action is totally hyperbolic (i.e. its toric degree is zero). We study the -action generated by a fixed vector of , that provides some results on t…
Study of group actions on CAT(0) cube complexes, focusing on marked length spectra.
problem Comparing marked length spectra of group actions on CAT(0) cube complexes.
method Use of finite-state automata and thermodynamic formalism for suspension flows over subshifts of finite type.
result Prove that the Manhattan curve is analytic and convex, and a straight line if and only if marked length spectra are homothetic.
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.
We describe a pair of invariants for actions of finite groups on shifts of finite type, the left-reduced and right-reduced shifts. The left-reduced shift was first constructed by U. Fiebig, who showed that its zeta function is an invariant, and in fact equal to the zeta function of the quotient dynamical system. We als…
Researchers compute spin structures on hyperelliptic curves using braid groups.
problem Understanding spin structures on hyperelliptic curves of genus g.
method Action of the Artin braid group B_{2g+2} on spin structures, combinatorial computation of orbits and isotropy groups.
result Purely combinatorial computation of S_{2g+2}-orbits and isotropy groups of spin structures.
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.
The fundamental 2-form of an invariant almost Hermitian structure on a 6-dimensional Lie group is described in terms of an action by SO(4)xU(1) on complex projective 3-space. This leads to a combinatorial description of the classes of almost Hermitian structures on the Iwasawa and other nilmanifolds.
We introduce a new online learning framework where, at each trial, the learner is required to select a subset of actions from a given known action set. Each action is associated with an energy value, a reward and a cost. The sum of the energies of the actions selected cannot exceed a given energy budget. The goal is to…