Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Technical Summary: Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Problem Formulation
This paper introduces a new variant of the Best Arm Identification (BAI) problem within the fixed-confidence setting of stochastic multi-armed bandits (MAB). In this setting, termed "BAI with post-action context," the learner selects an action (arm) $X$ and observes not only the reward $Y$ but also an intermediate post-action context $Z$. The context $Z$ is generated as a consequence of the chosen action, distinguishing this problem from standard contextual bandits where context precedes the action.

The authors analyze two structural regimes defined by the causal relationship between action, context, and reward:

1. Separator Context: The reward $Y$ depends solely on the context $Z$, making $X$ and $Y$ conditionally independent given $Z$ ($P(Y|X, Z) = P(Y|Z)$). In this case, the reward distribution is determined entirely by the observed context.
2. Non-Separator Context: The reward $Y$ depends on both the action $X$ and the context $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Here, the context provides additional information but is not a sufficient statistic for the reward.

The objective is to identify the arm with the highest expected reward with a probability of error at most $\delta$, while minimizing the sample complexity (the number of rounds required).

Methodology and Algorithms
The paper derives instance-dependent lower bounds on sample complexity for both settings and proposes algorithms that asymptotically achieve these bounds.

• Separator Setting:

  • Lower Bound: The authors derive a lower bound that depends on the frequencies of observed contexts rather than the frequencies of pulled arms. This is because, in the separator setting, any observation of a specific context $Z=j$ provides information about the mean reward of that context, regardless of which arm generated it.
  • Algorithm (STS): The proposed "Separator Track and Stop" (STS) algorithm utilizes a novel sampling rule called G-tracking. Unlike traditional methods that track optimal arm pull frequencies, G-tracking tracks the optimal frequencies of observing contexts. It treats the problem as an active off-policy learning task where the learner selects a distribution over arms to achieve a target distribution over contexts. The algorithm solves a convex optimization problem to find the optimal context frequencies and uses a geometric projection to select the next arm distribution, ensuring the observed context frequencies converge to the optimal target.

• Non-Separator Setting:

  • Lower Bound: The derived lower bound accounts for the joint distribution of actions and contexts.
  • Algorithm (NSTS): The "Non-Separator Track and Stop" (NSTS) algorithm extends the classical Track-and-Stop framework. It employs D-tracking to estimate and track the optimal proportions of pulling specific arms, utilizing the joint information of actions and their resulting contexts to refine the estimates of the reward means.

Key Contributions

1. Problem Definition: Formalization of BAI with post-action context, distinguishing between separator and non-separator structural regimes.
2. Theoretical Bounds: Derivation of instance-dependent lower bounds on sample complexity for both regimes. The separator bound is shown to be strictly tighter than bounds derived from ignoring the context.
3. Algorithm Design:
   • Introduction of G-tracking, a sampling rule that directly optimizes context observation frequencies in the separator setting, leveraging the geometry of the context space.
   • Extension of the Track-and-Stop framework to the non-separator setting (NSTS).
4. Sub-optimality Analysis: Theoretical and empirical demonstration that algorithms ignoring post-action context (such as standard Track-and-Stop) are strictly sub-optimal. In the separator setting, ignoring context can lead to arbitrarily large increases in sample complexity, even when reward gaps are small, because it fails to utilize the conditional independence structure.
5. Reduction Analysis: The paper analyzes the reduction of the separator problem to linear bandits, showing that such reductions increase the sample complexity lower bound compared to the proposed direct approach.

Results

• Theoretical: The proposed algorithms (STS and NSTS) are proven to be $\delta$-correct and achieve asymptotic optimality, matching the derived lower bounds as $\delta \to 0$.
• Empirical: Experiments on synthetic data and real-world data (KuaiSAR recommendation logs) demonstrate significant performance gains.
  • In the separator setting, STS drastically outperforms baselines (Track-and-Stop and Lazy Track-and-Stop), which often fail to stop within reasonable time horizons.
  • In the non-separator setting, NSTS significantly reduces the number of samples required compared to Track-and-Stop, which ignores context information.
  • Tracking plots confirm that STS converges to the optimal context frequencies, while baselines fail to align with the optimal strategy.

Significance and Claims
The paper claims that leveraging post-action context fundamentally alters the optimal strategy for pure exploration. The authors emphasize that in scenarios where intermediate observations (mediators) are available, ignoring them leads to substantial inefficiency. Specifically, in the separator setting, the ability to pool information across different arms that generate the same context allows for a much faster identification of the best arm. The work highlights that standard BAI algorithms are not merely sub-optimal but can be arbitrarily inefficient in these structured environments. The paper concludes that future work could address the case where the context probability matrix is unknown, noting that this introduces non-convexity challenges that make designing efficient algorithms difficult.