paper-with-me

홈 › Papers

Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek

2019-05-27 · Dong Quan Vu, Patrick Loiseau, Alonso Silva, Long Tran-Thanh

Resource allocation games such as the famous Colonel Blotto (CB) and Hide-and-Seek (HS) games are often used to model a large variety of practical problems, but only in their one-shot versions. Indeed, due to their extremely large strategy space, it remains an open question how one can efficiently learn in these games. In this work, we show that the online CB and HS games can be cast as path planning problems with side-observations (SOPPP): at each stage, a learner chooses a path on a directed acyclic graph and suffers the sum of losses that are adversarially assigned to the corresponding edges; and she then receives semi-bandit feedback with side-observations (i.e., she observes the losses on the chosen edges plus some others). We propose a novel algorithm, EXP3-OE, the first-of-its-kind with guaranteed efficient running time for SOPPP without requiring any auxiliary oracle. We provide an expected-regret bound of EXP3-OE in SOPPP matching the order of the best benchmark in the literature. Moreover, we introduce additional assumptions on the observability model under which we can further improve the regret bounds of EXP3-OE. We illustrate the benefit of using EXP3-OE in SOPPP by applying it to the online CB and HS games.

📄 PDF Abstract BibTeX arXiv:1905.11151

Code (2)

dongquan11/CB-HS.SOPPP 공식 구현
dongquan11/SOPPP_CB_and_HS_games

Tasks

Open-Ended Question Answering

Similar Papers 제목 키워드 기반

Learning Cognitive Maps from Transformer Representations for Efficient Planning in Partially Observed Environments

2024-01-11 · Antoine Dedieu, Wolfgang Lehrach, Guangyao Zhou, Dileep George 외

Despite their stellar performance on a wide range of tasks, including in-context tasks only revealed during inference, vanilla transformers and variants trained for next-token predictions (a) do not learn an explicit wor…

Joint Localization and Planning using Diffusion

2024-09-26 · L. Lao Beyer, S. Karaman

Diffusion models have been successfully applied to robotics problems such as manipulation and vehicle path planning. In this work, we explore their application to end-to-end navigation -- including both perception and pl…

Denoising

No-Regret Replanning under Uncertainty

2016-09-16 · Wen Sun, Niteesh Sood, Debadeepta Dey, Gireeja Ranade 외

This paper explores the problem of path planning under uncertainty. Specifically, we consider online receding horizon based planners that need to operate in a latent environment where the latent information can be modele…

Gaussian Processes

Pathfinding in stochastic environments: learning vs planning

2022-08-18 · PeerJ Computer Science 2022 8 · Alexey Skrynnik, Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov

Among the main challenges associated with navigating a mobile robot in complex environments are partial observability and stochasticity. This work proposes a stochastic formulation of the pathfinding problem, assuming th…

Graph Neural Networks for Decentralized Multi-Robot Path Planning

2019-12-12 · Qing-Biao Li, Fernando Gama, Alejandro Ribeiro, Amanda Prorok

Effective communication is key to successful, decentralized, multi-robot path planning. Yet, it is far from obvious what information is crucial to the task at hand, and how and when it must be shared among robots. To sid…

Decision MakingGraph Neural Network