PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient learning by implicit exploration in bandit problems with side observations

Tomas Kocak, Gergely Neu, Michal Valko, Remi Munos

arXiv:2604.24555v1cs.LGstat.ML

TL;DR

Online learning with partial feedback needs to use information between bandit and full-information feedback, including losses revealed through directed observation systems. The paper develops implicit-exploration algorithms for these settings, including a computationally efficient algorithm for combinatorial problems. It reports near-optimal regret guarantees without prior knowledge of the observation system for the simpler setting.

  • Problem

    Partial-observation learning needs to model feedback between bandit and full-information schemes, where chosen actions can reveal additional losses through a directed observation system.

    Source: §1 · pp. 1–2

  • Method

    The paper develops EXP3-IX and FPL-IX using implicit exploration, with geometric resampling supporting the computationally efficient combinatorial algorithm.

    Source: §1 · p. 3, §2.1 · p. 4, §3.1 · p. 7

  • Results

    EXP3-IX has near-optimal regret guarantees without prior observation-system knowledge, while FPL-IX provides similar properties with efficient computation for a wide range of combinatorial problems.

    Source: §1 · p. 3, §3 · p. 6, §3.1 · p. 7

  • Takeaways & Limitations

    Implicit exploration gives the algorithms an alternative to costly explicit exploration, and FPL-IX extends the approach to combinatorial settings where efficient computation matters.

    Source: §1 · p. 3, §2.1 · p. 4, §3 · p. 6

    The ordinary bandit scheme with only chosen-action feedback is noted as lacking known efficient algorithms close to minimax regret.

    Source: §3 · p. 6

Abstract

from arXiv · show

We consider online learning problems under a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.

1 Introduction

The paper extends partial-observation online learning to directed feedback systems between bandit and full-information feedback. It introduces implicit-exploration algorithms aimed at efficient learning without prior knowledge of the observation system.

1 Introduction

  • In the news-feed example, selecting a feed can reveal clickthroughs for unchosen assignments when feeds share content.The example groups assignments by user and treats the task as choosing one assignment per group.Source: §1 · p. 1
  • The model represents actions as binary vectors with at most m selected components, whose losses are observed alongside feedback determined by a directed observability graph.An edge i → j means selecting component i reveals component j’s loss; empty and complete graphs correspond to semi-bandit and full-information feedback when m > 1.Source: §1 · p. 2
  • Earlier clique-based regret bounds can fail to exploit highly connected observation systems with small cliques, motivating bounds based on independence numbers [15].Alon et al. [1] proposed EXP3-SET with regret O(√(αT log d)), where α upper-bounds the graphs’ independence numbers.Source: §1 · p. 2
  • EXP3-DOM has similar guarantees but requires advance access to the observation system and a sequence of set-cover problems [1].The paper identifies these requirements as limiting practical applicability.Source: §1 · pp. 2–3
  • EXP3-IX avoids requiring prior knowledge of the observation system, while FPL-IX offers an efficiently computable option for many combinatorial problems with m > 1.FPL-IX requires either set-cover solutions or an upper bound on the observability graphs’ independence numbers.Source: §1 · p. 3

2 Multi-armed bandit problems with side information

This section introduces EXP3-IX for directed side-observation bandits, replacing explicit exploration with optimistic, γ_t-controlled loss-estimate bias. Its analysis establishes a regret guarantee with learning-rate tuning adapted to Q_t.

2 Multi-armed bandit problems with side information

  • Each round, the chosen arm reveals its own loss and losses of outgoing neighbors in the environment’s directed graph.Unlike EXP3-DOM’s dominating-set exploration, IX avoids prior graph knowledge for exploration, though constructing estimates still requires graph access after acting.Source: §2 · pp. 3–4

2.1 Efficient learning by implicit exploration

  • Implicit exploration replaces explicit exploration with optimistic loss estimates whose learner-side bias is directly controlled by γ_t.Unlike explicit exploration, IX biases the estimates rather than the sampling distribution.Source: §2.1 · p. 4
  • EXP3-IX uses an adaptive-learning-rate variant of EXP3, avoiding prior graph knowledge when setting learning rates.The analysis tunes learning rates using quantities Q_t that depend on the interaction history.Source: §2.1 · p. 4, §2.2 · p. 5

2.2 Performance guarantees for EXP3-IX

  • EXP3-IX has a regret guarantee derived by combining deterministic bounds on each Q_t with a theorem, using parameter choices adaptive to Q_t.The guarantee’s tuning depends on interaction-history quantities.Source: §2.2 · pp. 5–6

3 Combinatorial semi-bandit problems with side observations

The section introduces combinatorial semi-bandit feedback with side observations and an efficient FPL-based algorithm using implicit exploration. Its performance guarantee relies on tuning with efficiently computable approximations to independence numbers.

3 Combinatorial semi-bandit problems with side observations

  • The new semi-bandit-with-side-observations scheme reveals losses of some components outside the chosen action, placing feedback between semi-bandit and full information.The section contrasts this setting with full-information, semi-bandit, and bandit feedback.Source: §3 · p. 6

3.1 Implicit exploration by geometric resampling

  • FPL-IX implements implicit exploration through modified geometric resampling, producing loss estimates that are optimistic in expectation.The estimates use independent copies of the observation indicator and geometrically distributed random variables.Source: §3.1 · p. 7
  • Geometric resampling takes at most d copies of the observation indicator in expectation, with each copy requiring one linear-optimization-oracle call.The passage therefore bounds expected running time by d times the oracle's expected running time.Source: §3.1 · p. 7

3.2 Performance guarantees for FPL-IX

  • FPL-IX's guarantee uses nonincreasing learning rates and efficiently computable independence-number approximations within a factor C of the true values.The stated analysis assumes an oblivious adversary; the section notes that exact quantities are observable information-theoretically but not efficiently computable.Source: §3.2 · pp. 7–8
  • The conclusion emphasizes that the algorithms do not need the observation system before choosing actions and extends the framework to structured action sets.The combinatorial setting is addressed with an efficient algorithm.Source: §3.2 · p. 8

A Proof of Lemma 1

The proof discretizes observation probabilities and uses an expanded graph to bound a sum involving the original graph's independence number.

A Proof of Lemma 1

  • The proof discretizes each p_i as a multiple of 1/M, rounding it upward with error less than 1/M.It then uses monotonicity of x/(x+a) for nonnegative x and a to obtain a bound.Source: A Proof of Lemma 1 · p. 10
  • The expanded graph replaces each node i with a clique of M p_i nodes and connects cliques according to the original directed edges.The construction preserves the independence number α.Source: A Proof of Lemma 1 · p. 10
  • The proof bounds the remaining sum using a graph lemma on indegrees and independence number, after applying an algebraic inequality.The stated lemmas are adapted from Alon et al. [1].Source: A Proof of Lemma 1 · pp. 9–10

B Full proof of Theorem 1

The proof of Theorem 1 controls regret through a potential argument and combines the resulting bounds with optimistic loss estimates.

B Full proof of Theorem 1

  • The proof tracks the evolution of log W′_{t+1}/W_t to control regret.It uses exponential and logarithmic inequalities, then Jensen's inequality, in the derivation.Source: B Full proof of Theorem 1 · p. 11
  • After combining intermediate bounds and taking expectations, the proof telescopes a term across time.The derivation also invokes a standard algebraic lemma [4, Lemma 3.5].Source: B Full proof of Theorem 1 · p. 12
  • The resulting bound yields the theorem because the loss estimates are optimistic.Source: B Full proof of Theorem 1 · p. 12

C Full proof of Theorem 2

The proof of Theorem 2 bounds FPL-IX regret by comparing it with a hypothetical learner and applying auxiliary lemmas.

C Full proof of Theorem 2

  • The analysis applies the follow-the-leader/be-the-leader lemma to a sequence built from the estimated losses and perturbation differences.Source: C Full proof of Theorem 2 · p. 12
  • Auxiliary lemmas bound the expected regret and total expected regret in terms of the variables used in the theorem's bound.The proof cites Neu and Bartók [16] for a result extracted from their Theorem 1 proof.Source: C Full proof of Theorem 2 · p. 13

D Proof of Lemma 3

The proof establishes a lower bound by separating the zero-observation case, then taking expectations and invoking Lemma 1.

D Proof of Lemma 3

Loading 2604.24555v1…