Q-Search Trees: An Information-Theoretic Approach Towards Hierarchical Abstractions for Agents with Computational Limitations
In this paper, we develop a framework to obtain graph abstractions for decision-making by an agent where the abstractions emerge as a function of the agent's limited computational resources. We discuss the connection of the proposed approach with information-theoretic signal compression, and formulate a novel optimization problem to obtain tree-based abstractions as a function of the agent's computational resources. The structural properties of the new problem are discussed in detail, and two algorithmic approaches are proposed to obtain solutions to this optimization problem. We discuss the quality of, and prove relationships between, solutions obtained by the two proposed algorithms. The framework is demonstrated to generate a hierarchy of abstractions for a non-trivial environment.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingSimilar Papers 제목 키워드 기반
A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions
In this chapter, an integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, environment abstractions for resource-constrained autonomous agents is presented. The formulation l…
Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming
In this paper, a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents is presented. The formulation leverages conce…
Discovering State Equivalences in UCT Search Trees By Action Pruning
One approach to enhance Monte Carlo Tree Search (MCTS) is to improve its sample efficiency by grouping/abstracting states or state-action pairs and sharing statistics within a group. Though state-action pair abstractions…
Reasoning with shapes: profiting cognitive susceptibilities to infer linear mapping transformations between shapes
Visual information plays an indispensable role in our daily interactions with environment. Such information is manipulated for a wide range of purposes spanning from basic object and material perception to complex gestur…
Scene UnderstandingWhen Do Skills Help Reinforcement Learning? A Theoretical Analysis of Temporal Abstractions
Skills are temporal abstractions that are intended to improve reinforcement learning (RL) performance through hierarchical RL. Despite our intuition about the properties of an environment that make skills useful, a preci…
Reinforcement Learning (RL)