Exploration by Optimisation in Partial Monitoring
We provide a simple and efficient algorithm for adversarial $k$-action $d$-outcome non-degenerate locally observable partial monitoring game for which the $n$-round minimax regret is bounded by $6(d+1) k^{3/2} \sqrt{n \log(k)}$, matching the best known information-theoretic upper bound. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Bayesian Exploration Networks
Bayesian reinforcement learning (RL) offers a principled and elegant approach for sequential decision making under uncertainty. Most notably, Bayesian agents do not face an exploration/exploitation dilemma, a major patho…
Decision MakingDecision Making Under UncertaintyDensity EstimationNormalising Flows+3Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation
Optimisation of fleets of commercial vehicles with regards scheduling tasks from various locations to vehicles can result in considerably lower fleet traversal times. This has significant benefits including reduced expen…
SchedulingBeyond Optimism: Exploration With Partially Observable Rewards
Exploration in reinforcement learning (RL) remains an open challenge. RL algorithms rely on observing rewards to train the agent, and if informative rewards are sparse the agent learns slowly or may not learn at all. To …
BenchmarkingReinforcement Learning (RL)Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing a linear structure on both the losses and the observations. This setting can be vi…
MAGPIE: Machine Automated General Performance Improvement via Evolution of Software
Performance is one of the most important qualities of software. Several techniques have thus been proposed to improve it, such as program transformations, optimisation of software parameters, or compiler flags. Many auto…