Graph Learning Under Partial Observability
Many optimization, inference and learning tasks can be accomplished efficiently by means of decentralized processing algorithms where the network topology (i.e., the graph) plays a critical role in enabling the interactions among neighboring nodes. There is a large body of literature examining the effect of the graph structure on the performance of decentralized processing strategies. In this article, we examine the inverse problem and consider the reverse question: How much information does observing the behavior at the nodes of a graph convey about the underlying topology? For large-scale networks, the difficulty in addressing such inverse problems is compounded by the fact that usually only a limited fraction of the nodes can be probed, giving rise to a second important question: Despite the presence of unobserved nodes, can partial observations still be sufficient to discover the graph linking the probed nodes? The article surveys recent advances on this challenging learning problem and related questions.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationGraph LearningSimilar Papers 제목 키워드 기반
Graph Learning over Partially Observed Diffusion Networks: Role of Degree Concentration
This work examines the problem of graph learning over a diffusion network when data can be collected from a limited portion of the network (partial observability). The main question is to establish technical guarantees o…
ClusteringGraph LearningFrom Bandits to Experts: A Tale of Domination and Independence
We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir. Our main result is a characterization of regret in the directed observability model in terms of the dominating and ind…
Multi-Armed BanditsA General Learning Framework for Open Ad Hoc Teamwork Using Graph-based Policy Learning
Open ad hoc teamwork is the problem of training a single agent to efficiently collaborate with an unknown group of teammates whose composition may change over time. A variable team composition creates challenges for the …
Graph Neural NetworkR2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability
Computing worst-case robust strategies in pursuit-evasion games (PEGs) is time-consuming, especially when real-world factors like partial observability are considered. While important for general security purposes, real-…
Zero-shot GeneralizationReinforcement LearningGraph Neural NetworkBenchmarking Partial Observability in Reinforcement Learning with a Suite of Memory-Improvable Domains
Mitigating partial observability is a necessary but challenging task for general reinforcement learning algorithms. To improve an algorithm's ability to mitigate partial observability, researchers need comprehensive benc…
General Reinforcement Learning