Study on natural actor-critic for POMDPs with finite memory.
problem Learning in partially observed Markov decision processes with noisy observations.
method Finite actor-critic method with multi-step temporal difference learning.
result First non-asymptotic global convergence for POMDPs with function approximation.
State-regularized RNNs improve interpretability and performance on long-term memory tasks.
problem RNNs struggle with long-term memory and lack of interpretability.
method Introduce a stochastic state transition mechanism to limit state transitions to a finite set.
result State-regularized RNNs perform better on tasks requiring long-term memory.
The paper simplifies multi-agent RL dynamics in finite-state Markov games using homogenization.
problem Approximating complex multi-agent reinforcement learning dynamics in finite-state Markov games.
method Rescaling learning process by reducing learning rate and increasing update frequency, proving convergence to an ODE.
result The rescaled process converges to an ODE that approximates the agent's learning dynamics.
Extends effect variable concept to finite states for web search evaluation.
problem Finding effect of variant variables in changes of observable variables.
method Theoretical analysis and simultaneous distribution decomposition.
result States of extreme effect variable are minimally affected by variant and highly different in observable variable.
Finite presentations for skein algebras linked to gauge field theory.
problem Understanding finite presentations for skein algebras and their relationship to gauge field theory.
method Provided finite presentations and deduced properties of stated skein algebras.
result Stated skein algebras are Koszul and isomorphic to quantum moduli algebras in gauge field theory.
Center identified in stated skein algebra for quantum traces.
problem Understanding the center of the stated skein algebra.
method Analyzing the algebra as a generalization of Kauffman bracket skein algebra, focusing on the case when the quantum parameter is a root of unity.
result Simple description and dimension calculation of the center over the center module.
For finite networks, Bouchaud-Mézard model's steady state is lognormal and quasi-stationary.
problem Finite network effects on steady state distribution in Bouchaud-Mézard model.
method Analysis of Bouchaud-Mézard model with finite number of nodes.
result Time-dependent lognormal mean and quasi-stationary inverse gamma distribution.
Paper modifies automata learning to improve interpretability.
problem Lack of clear interpretation for automata models.
method Proposes a state-merging approach to modify finite state automata.
result Demonstrates applicability of key properties in various sequential data contexts.
We obtain an index of the complexity of a random sequence by allowing the role of the measure in classical probability theory to be played by a function we call the generating mechanism. Typically, this generating mechanism will be a finite automata. We generate a set of biased sequences by applying a finite state auto…
We extend a recent synchronization analysis of exact finite-state sources to nonexact sources for which synchronization occurs only asymptotically. Although the proof methods are quite different, the primary results remain the same. We find that an observer's average uncertainty in the source state vanishes exponential…
A new layer learns abstract relations from graph structure using finite-state automata.
problem Learning abstract relations from graph structure for program analysis.
method Relaxing the problem into learning finite-state automata policies on a graph-based POMDP and training these policies using implicit differentiation.
result GFSA layer finds shortcuts in grid-world graphs and reproduces simple static analyses on Python programs.
Recurrent neural networks trained on regular languages exhibit stable states that can recover from noise.
problem Stability of internal states in recurrent neural networks trained on regular languages.
method Empirical study with analysis of network activation and transitions between states.
result Recurrent neural networks trained on regular languages can recover from random perturbations and maintain stable states.
New method predicts state evolution for non-first-order algorithms on nonconvex problems.
problem Analyzing nonconvex optimization problems with random data.
method Developed a state evolution for a broader class of algorithms including first-order and saddle point updates.
result Established rigorous state evolution predictions and finite-sample guarantees for non-first-order methods.
We analyze how an observer synchronizes to the internal state of a finite-state information source, using the epsilon-machine causal representation. Here, we treat the case of exact synchronization, when it is possible for the observer to synchronize completely after a finite number of observations. The more difficult …
Quantizes Toda systems using geometric methods.
problem Quantizing Toda systems with geometric quantization.
method Geometric quantization of Toda systems as a coadjoint orbit of a group of matrices.
result Found unitary and non-unitary finite dimensional quantum Hilbert spaces.
Estimates Markov chain parameters from a single long sequence, analyzing complexity based on mixing properties.
problem Estimating parameters of a discrete-state Markov chain kernel from a single long sequence of observations.
method Characterizes minimax sample complexity in finite and countably infinite cases, focusing on mixing properties.
result Sample complexity is governed by mixing properties, with finite-sample estimators available for finite-state cases.
Quantum states associated with subsets of product manifolds are separable.
problem Characterizing quantum states associated with subsets of product manifolds.
method Using holomorphic sections of quantum line bundles and restriction maps.
result Quantum states associated with finite unions of products are separable.
Reservoir computers and RNNs fall short of optimal prediction for stochastic PDFA.
problem Predicting stochastic processes generated by probabilistic deterministic finite-state automata.
method Generalized linear models, Reservoir computers, and Long Short-Term Memory (LSTM) RNNs were tested.
result Each method can fall short of maximal predictive accuracy by up to 50% after training.
In this paper, we first establish the reflected backward stochastic difference equations with finite state (FS-RBSDEs for short). Then we explore the Existence and Uniqueness Theorem as well as the Comparison Theorem by "one step" method. The connections between FS-RBSDEs and optimal stopping time problems are investig…
Algorithm estimates human decision-making in high-dimensional states with finite-time guarantees.
problem Estimating optimal policies and measures of fit in dynamic decision models with high-dimensional state spaces.
method Single-loop estimation algorithm with stochastic gradient steps for reward maximization.
result Algorithm converges to a stationary solution with finite-time guarantees and approximates maximum likelihood sublinearly.
In 1968, Milnor conjectured that a complete noncompact manifold with nonnegative Ricci curvature has a finitely generated fundamental group. The author applies the Excess Theorem of Abresch and Gromoll (1990), to prove two theorems. The first states that if such a manifold has small linear diameter growth then its fund…
Method learns latent states from rich observations to improve RL exploration.
problem Improving RL performance with rich observations and latent states.
method Estimates latent states from observations through regression and clustering, providing finite-sample guarantees.
result Exponential improvement over Q-learning with naïve exploration. Study learns state representations from observations for control, proving guarantees.
problem Learning state representations from high-dimensional observations for control.
method Cost-driven approach, learning latent state model to predict costs.
result Proves finite-sample guarantees for near-optimal state representation and controller.
In his 2011 work, Maas has shown that the law of any time-reversible continuous-time Markov chain with finite state space evolves like a gradient flow of the relative entropy with respect to its stationary distribution. In this work we show the converse to the above by showing that if the relative law of a Markov chain…
We consider 1-qubit mixed quantum state estimation by adaptively updating measurements according to previously obtained outcomes and measurement settings. Updates are determined by the average-variance-optimality (A-optimality) criterion, known in the classical theory of experimental design and applied here to quantum …
New approach to understand recurrent policies as FSMs without minimization.
problem Minimization of FSMs obscures the semantics of policy decisions.
method Start with unminimized FSM, apply interpretable reductions, use attention tool.
result Reveals insights into policy decisions not previously noticed.
Simple algorithm controls unknown systems with optimal regret.
problem Online reinforcement learning for unknown systems with arbitrary state and action spaces.
method Upper-confidence reinforcement learning algorithm using optimistic Q functions.
result Regret bound of $O(HL(KH)^{ rac{d-1}{d}})$ for finite horizon control systems.
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, O(H3K2d/(2d+1)). The paper develops a Hoeffding inequality for Markov chains and applies it to bandit problems.
problem Developing a Hoeffding inequality for Markov chains and applying it to bandit problems.
method Developed a Hoeffding inequality for the partial sums of an irreducible Markov chain on a finite state space.
result Demonstrated the inequality's effectiveness in identifying approximately best Markovian arms and minimizing regret in Markovian bandits.
We solve POMDPs by approximating them as finite-state MDPs.
problem Computational challenges in learning optimal policies for POMDPs.
method Transform POMDP into a Superstate MDP, apply TD-learning and policy optimization.
result Finite-time bounds on TD-learning error for non-Markovian dynamics.
Study properties of self-similar continua with finite intersection property.
problem Characterize self-similar continua with finite intersection property.
method Prove intersection graph criterion, finite order theorem, and parameter matching theorem.
result All Jordan arcs starting from a intersection point in such continuum on a plane should have the same slope parameter at that point.
Compute central extension of mapping class group from stated skein algebra
problem Compute central extension of mapping class group from stated skein algebra
method Compute central extension of mapping class group from stated skein algebra
result Compute central extension of mapping class group from stated skein algebra
New method uses Cantor embeddings and Wasserstein distances to analyze predictive states in time series data.
problem Analyzing predictive states in stochastic processes using time series data.
method Wasserstein distances for detecting predictive equivalences in symbolic data, using Cantor embeddings for finite-dimensional representation.
result Exploratory analysis of temporal structure in various processes reveals insights.
In this paper, it is shown that there are no nonconstant Goussarov-Polyak-Viro finite-type invariants that are invariant under the virtualization move. As an immediate corollary, we obtain the theorem which states none of the Birman coefficients of the Jones-Kauffman polynomial are of GPV finite type.
The paper explores geometric calculations on probability manifolds derived from master equations.
problem Understanding geometric properties of probability manifolds from master equations.
method Deriving geometric quantities like Levi-Civita connection, gradient, Hessian, parallel transport, and curvatures on probability manifolds.
result Calculation of geometric quantities in probability manifolds, including curvatures and connections.
New framework interprets deep nets via finite-state distributions.
problem Understanding the functionality of neural networks.
method Introduces a new framework based on finite-state distributions.
result Exact computation of information-theoretic quantities possible.
A new method approximates Laplacian eigenvectors for RL efficiently.
problem Efficiently learning state representations in RL.
method General and scalable approach to approximating Laplacian eigenvectors.
result Empirically shows improved performance in RL tasks.
Method infers causal structure from system behaviors using RKHS and kernel ε-machines.
problem Discovering causal structure in systems with varying external and measurement noise.
method Combines causal states and RKHS for efficient representation and inference of causal structure.
result Robustly estimates causal structure in high-dimensional data with varying noise.
Two neural network methods solve the master equation for MFGs.
problem Approximating Nash equilibria in stochastic, finite-agent games.
method Backward induction and direct PDE tackling neural networks.
result Neural networks can approximate the master equation's solution.
We present a comprehensive study of utility function of the minority game in its efficient regime. We develop an effective description of state of the game. For the payoff function $g(x)=\sgn (x)$ we explicitly represent the game as the Markov process and prove the finitness of number of states. We also demonstrate bou…
Paper introduces a technique to simplify RNN policies for better understanding and analysis.
problem Difficulty in explaining and analyzing RNN policies due to continuous-valued memory vectors and observation features.
method Quantized Bottleneck Insertion technique to learn finite representations of RNN vectors and features.
result Finite representations of RNN policies can be as small as 3 discrete memory states and 10 observations, improving interpretability.
Method extracts weighted automata from RNNs using state space regression.
problem Extracting weighted automata from RNNs for better model understanding.
method Regression on RNN state space to prioritize counterexample candidates.
result Quantitative/weighted extension of DFA extraction.
This is a survey on old and new results as well as an introduction to various related basic notions and concepts, based on two talks given at the International Workshop on Geometry and Analysis in Kemerovo (Sobolev Institute of Mathematics, Kemerovo State University) and at the University of Krasnojarsk in June 2011. W…
Study cost-driven state representation learning for control from partial observations.
problem Learning state representation for control from partial and high-dimensional observations.
method Cost-driven state representation learning via predicting cumulative costs.
result Established finite-sample guarantees for near-optimal representation and controller.
Abstract: Geometrically reformulates estimation theory for finite-dimensional C*-algebras.
problem Estimation theory for finite-dimensional C*-algebras.
method Geometrical formulation of estimation theory.
result Derivation of Cramer-Rao and Helstrom bounds.
Theoretical justification for asymmetric actor-critic algorithms in reinforcement learning.
problem Lack of precise theoretical justification for asymmetric actor-critic algorithms in reinforcement learning.
method Adapting a finite-time convergence analysis to the asymmetric actor-critic setting with linear function approximators.
result A finite-time bound reveals that the asymmetric critic eliminates aliasing errors in the agent state.
Framework for differentiating WFSTs for structured loss functions.
problem Training dynamic structured loss functions in neural networks.
method Automatic differentiation with WFSTs, combining pruning and back-off.
result Demonstrated learning over WFST latent phrase decomposition.
We publish a table of primitive finite-type invariants of order less than or equal to six, for knots of ten or fewer crossings. We note certain mod-2 congruences, one of which leads to a chirality criterion in the Alexander polynomial. We state a computational result on mod-2 finite-type invariants of 2-strand string l…