Indexed Bellman Information Complexity

• URL: http://arxiv.org/abs/2606.11171v2
• Date: Thu, 18 Jun 2026 16:16:05 GMT
• Title: Indexed Bellman Information Complexity
• Abstract summary: We develop a representation-level theory of interactive decision making centered on information indices and reference histories.<n>We show that DEC is best viewed as a one-step relaxation of indexed Bellman information complexity, not as a universally tight conversion mechanism.
• Score: 5.082462420126421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop indexed Bellman information complexity, a representation-level theory of interactive decision making centered on information indices and reference histories. The representation strips away problem-specific syntax and retains only the ingredients needed for dynamic programming and information accounting, thereby unifying the earlier framework of indexed algorithmic information ratios (AIR). On the upper-bound side, regret is controlled by Bellman supersolutions or potential identities whose gradient bracket is paid for by indexed information. Upper-confidence-bound (UCB), estimation-to-decision/decision-estimation-coefficient (E2D/DEC), and adaptive-minimax-sampling or exploration-by-optimization (AMS/EBO) methods appear as three relaxations of this same identity. On the lower-bound side, the posterior-reference trajectory supplies both the information telescope and the ghost quantile of small-regret trajectories. The resulting critical radius in the lower bound is an effective-dimension-scale quantity, as in Fano and local-prior-mass lower bounds, rather than the constant radius of a two-point Le Cam argument. The examples show that DEC is best viewed as a one-step relaxation of indexed Bellman information complexity, not as a universally tight conversion mechanism. We illustrate the framework through several applications, with particular emphasis on kernel bandits. In this setting, the active action marginal provides a concrete basis for comparing UCB, E2D, and AMS/EBO.

Related papers

• Towards Zero-Shot Point Cloud Registration Across Diverse Scales, Scenes, and Sensor Setups [41.033896572767496]
  We present BUFFER-X, a training-free registration framework that achieves zero-shot generalization.<n>Our approach employs hierarchical multi-scale matching to extract correspondences across local, middle, and global receptive fields.<n>For efficiency-critical applications, we introduce BUFFER-X-Lite, which reduces total time by 43%.
  arXiv  Detail & Related papers  (2026-01-06T06:51:24Z)
• Scalable Bayesian Tensor Ring Factorization for Multiway Data Analysis [24.04852523970509]
  We propose a novel BTR model that incorporates a nonparametric Multiplicative Gamma Process (MGP) prior.<n>To handle discrete data, we introduce the P'olya-Gamma augmentation for closed-form updates.<n>We develop an efficient Gibbs sampler for consistent posterior simulation, which reduces the computational complexity of previous VI algorithm by two orders.
  arXiv  Detail & Related papers  (2024-12-04T13:55:14Z)
• Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory [87.62730694973696]
  STEEL is the first provably sample-efficient algorithm for learning the controllable dynamics of an Exogenous Block Markov Decision Process from a single trajectory.<n>We prove that STEEL is correct and sample-efficient, and demonstrate STEEL on two toy problems.
  arXiv  Detail & Related papers  (2024-10-03T21:57:21Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Regret Minimization via Saddle Point Optimization [29.78262192683203]
  Decision-estimation coefficient (DEC) was shown to provide nearly tight lower and upper bounds on the worst-case expected regret in structured bandits and reinforcement learning. We derive an anytime variant of the Estimation-To-Decisions (E2D) algorithm. Our formulation leads to a practical algorithm for finite model classes and linear feedback models.
  arXiv  Detail & Related papers  (2024-03-15T15:09:13Z)
• Combating Bilateral Edge Noise for Robust Link Prediction [56.43882298843564]
  We propose an information-theory-guided principle, Robust Graph Information Bottleneck (RGIB), to extract reliable supervision signals and avoid representation collapse. Two instantiations, RGIB-SSL and RGIB-REP, are explored to leverage the merits of different methodologies. Experiments on six datasets and three GNNs with diverse noisy scenarios verify the effectiveness of our RGIB instantiations.
  arXiv  Detail & Related papers  (2023-11-02T12:47:49Z)
• Zero-shot Skeleton-based Action Recognition via Mutual Information Estimation and Maximization [26.721082316870532]
  Zero-shot skeleton-based action recognition aims to recognize actions of unseen categories after training on data of seen categories. We propose a new zero-shot skeleton-based action recognition method via mutual information (MI) estimation and estimation.
  arXiv  Detail & Related papers  (2023-08-07T23:41:55Z)
• KECOR: Kernel Coding Rate Maximization for Active 3D Object Detection [48.66703222700795]
  We resort to a novel kernel strategy to identify the most informative point clouds to acquire labels. To accommodate both one-stage (i.e., SECOND) and two-stage detectors, we incorporate the classification entropy tangent and well trade-off between detection performance and the total number of bounding boxes selected for annotation. Our results show that approximately 44% box-level annotation costs and 26% computational time are reduced compared to the state-of-the-art method.
  arXiv  Detail & Related papers  (2023-07-16T04:27:03Z)
• The Information Bottleneck's Ordinary Differential Equation: First-Order Root-Tracking for the IB [0.0]
  The Information Bottleneck (IB) is a method of lossy compression of relevant information. We exploit the dynamics underlying the IB's optimal tradeoff curve. We translate an understanding of IB bifurcations into a surprisingly accurate numerical algorithm.
  arXiv  Detail & Related papers  (2023-06-16T12:02:19Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Clustering with minimum spanning trees: How good can it be? [0.6883078440438425]
  We quantify the extent to which minimum spanning trees are meaningful in low-dimensional partitional data clustering tasks.<n>We review, study, extend, and generalise a few existing, state-of-the-art MST-based partitioning schemes.<n>Overall, the Genie and the information-theoretic methods often outperform the non-MST algorithms.
  arXiv  Detail & Related papers  (2023-03-10T03:18:03Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-means algorithm variants essentially fit a mixture of identical spherical Gaussians to data that vastly deviates from such a distribution. We develop more effective optimization algorithms for general GMMs, and we combine these algorithms with regularization strategies that avoid overfitting. These results shed new light on the current status quo between GMM and k-means methods and suggest the more frequent use of general GMMs for data exploration.
  arXiv  Detail & Related papers  (2023-02-05T18:22:29Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations. The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
  arXiv  Detail & Related papers  (2023-02-02T22:16:49Z)
• Adaptive Local-Component-aware Graph Convolutional Network for One-shot Skeleton-based Action Recognition [54.23513799338309]
  We present an Adaptive Local-Component-aware Graph Convolutional Network for skeleton-based action recognition. Our method provides a stronger representation than the global embedding and helps our model reach state-of-the-art.
  arXiv  Detail & Related papers  (2022-09-21T02:33:07Z)
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems [2.335152769484957]
  We derive and detail a theoretical analysis of an efficient consensus algorithm based on gradient proximal (PG) approach. The proposed algorithm is also applied to another particular convolutional problem for the anomaly detection task.
  arXiv  Detail & Related papers  (2020-11-19T20:52:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Robust Person Re-Identification through Contextual Mutual Boosting [77.1976737965566]
  We propose the Contextual Mutual Boosting Network (CMBN) to localize pedestrians. It localizes pedestrians and recalibrates features by effectively exploiting contextual information and statistical inference. Experiments on the benchmarks demonstrate the superiority of the architecture compared the state-of-the-art.
  arXiv  Detail & Related papers  (2020-09-16T06:33:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.