Exploring for Side Observations Without Distorting the Policy

In many decision problems, taking one action also tells you what would have happened under other actions. A retailer who stocks plenty of shelf space sees the true demand, so she can work out the sales, costs, and next inventory level she would have had under every smaller order. A feedback graph is the standard way to describe this. It is a graph whose nodes are actions, or state-action pairs, and an edge from $i$ to $j$ means that executing $i$ also reveals the outcome of $j$. In bandits and tabular reinforcement learning (RL), this structure provably cuts the data needed to learn. Sample cost then scales with small graph quantities, such as the size of a dominating set (a set of nodes whose neighborhoods cover the whole graph), rather than with the number of actions. In RL there is a catch that bandits do not have. The informative nodes must be reached. They are often costly to sit in, and an agent rewarded only by the task has no reason to go there.

This note proposes one specific fix for deep RL with a known feedback graph. The agent receives an exploration bonus that values a state-action pair by how much uncertainty it removes across its whole out-neighborhood in the graph, not by how novel the pair itself is. That bonus is then delivered through a potential-based construction, which guarantees it cannot change which policy is optimal. The bet is that both parts matter. A neighborhood bonus without the guarantee will make the agent linger in high-information but costly states, for example by overstocking. A guaranteed bonus that counts only visits will waste effort on states the graph has already covered for free. The method should win most where the informative states are hard to reach, and we can turn that difficulty up and down on purpose.

Core Claim

Reinforcement Learning with Feedback Graphs supplies the theory. It shows that tabular RL with side observations has sample complexity whose leading term scales with the dominating-set size $\gamma$ instead of the number of state-action pairs. It also exposes the "reaching problem": the bound inflates with $1/p_0$, where $p_0$ is the probability of reaching the least accessible node in the dominating set. Its algorithm is a two-phase plan that first learns to reach the dominating set and then visits it repeatedly. That plan is tabular, assumes the graph is known, and is computationally heavy.

Reinforcement Learning with Intrinsically Motivated Feedback Graph for Lost-sales Inventory Control supplies the deep-RL setting and the closest prior method. Its RLFG approach pushes graph-derived counterfactual transitions into the replay buffers of TD3 and Rainbow DQN. Its IME bonus pushes the agent toward states that yield many uncertain side experiences. However, IME is an unshaped bonus with no guarantee that the learned policy is unbiased.

Potential-Based Intrinsic Motivation supplies the constraint and the tool. It shows that ad-hoc intrinsic rewards cause reward hacking and procrastination. It also gives PBIM and Generalized Reward Matching (GRM), which convert history-dependent bonuses into forms that leave the optimal policy unchanged.

Our claim is that the right exploration signal for RL with feedback graphs is the out-neighborhood uncertainty of a pair, delivered through GRM. This combination beats three alternatives: replay with side observations and no bonus, visitation-based bonuses with or without the guarantee, and unshaped IME. The advantage should grow with reaching difficulty, and only the guaranteed variants should end at the true optimum. No paper in the file combines graph-aware information value with optimality-preserving shaping. Dann et al. never leave the tabular setting, and the inventory work never guarantees optimality.

Research Program

The setting is the "informed" one: the agent knows the feedback-graph rule in advance, as with inventory accounting. Learning an unknown graph is out of scope. That problem runs into the identifiability barrier for binary rewards described in Pure Exploration with Feedback Graphs.

The base learner is RLFG, meaning TD3 or Rainbow DQN whose replay buffer also receives graph-derived transitions. An ensemble of Q-heads gives an uncertainty estimate $u(\bar s,\bar a)$ at any state-action pair. Crucially, this estimate is trained on observed data, side observations included, so a state that is never visited but often observed will correctly look certain. The information value of executing $(s,a)$ is

$$ I(s,a) = \sum_{(\bar s,\bar a) \in N^+(s,a)} u(\bar s,\bar a), $$

where $N^+(s,a)$ is the set of pairs whose outcomes are revealed by executing $(s,a)$, and $u$ is the ensemble disagreement. In practice we compute $I$ on a sampled subset of the neighborhood, because inventory neighborhoods can contain hundreds of order levels.

$I$ changes as the agent learns, so it is history-dependent. A raw bonus of $\beta I$ therefore biases the policy, which is exactly the failure Forbes et al. formalize. We instead pass $\beta I$ through GRM. GRM pays the bonus early and subtracts a matched amount later, with delay $D$, so the total shaping over any episode cancels and the optimal policy is preserved.

The analysis component is modest and targeted. In the tabular case, we will check whether a GRM-shaped neighborhood bonus reduces the effective $1/p_0$ dependence of Dann et al. in the constructed environments. We will check this by comparing measured episodes-to-threshold against computed $p_0$, not by proving a new bound. We do not claim a function-approximation regret theorem.

Environments and Reaching Difficulty

We will use two environment families. Each has a knob that controls how hard the informative nodes are to reach, and each has small instances where the exact optimal policy is computable by value iteration.

The first family is lost-sales inventory from the RLFG work, in single-item, 5-item, and multi-echelon versions with Poisson demand. We add two knobs, order lead time and holding cost. Uncensored, fully informative observations require inventory above demand. A long lead time makes high-inventory states take several steps to reach, and a high holding cost makes them expensive to sit in. Together these turn up the reaching problem directly.

The second family is a MiniGrid-style navigation task, built with the MiniGrid & Miniworld library. It adds "lookout" cells whose execution reveals the transitions and rewards of a whole region, through a known graph rule. The lookouts sit off the optimal path at a controllable distance $k$. This gives a clean, non-inventory test that the method is not specific to accounting identities.

Baselines

The naive reference point is vanilla TD3 or Rainbow DQN with uniform replay and no side observations. The file reports that these fail to converge within reasonable sample budgets under demand censoring.

The strongest existing method is RLFG, meaning TD3-FG and Rainbow-FG, both with and without IME, from the lost-sales feedback-graph paper. That paper reports that TD3-FG and Rainbow-FG reach "near-optimal performance within just 20 episodes" on single-item inventory. It also reports that TD3-FG "reduced the performance gap by up to 4.58%" over TD3 in the 5-item environment. There is no reported result found on Lacuna for IME isolated from RLFG. We will rerun both from the paper's description on identical demand seeds, network sizes, replay ratios, and environment-step budgets. Each method, including ours, gets the same hyperparameter-search budget of trials over its own bonus coefficient and schedule. Beating RLFG means two things. First, reaching within 1% of the value-iteration optimum in significantly fewer episodes once lead time or lookout distance is large. Second, ending no worse than RLFG at the default settings, where we expect a tie.

The second strong competitor is a deep approximation of Dann et al.'s dominating-set strategy. A goal-reaching policy first drives the agent to a greedily computed dominating set and then hands control to RLFG. This tests whether explicit explore-then-commit is enough.

Two ablations isolate the key ingredients. The first is the GRM-shaped visitation bonus, an ensemble-uncertainty bonus on the executed pair only. It isolates the value of using the neighborhood. The second is the unshaped neighborhood bonus. It isolates the value of the optimality guarantee. As a sanity check on the GRM machinery, we will reproduce the MiniGrid DoorKey result of Forbes et al. In that result, GRM with $D=10$ reached the goal in about 38 steps versus about 62 steps for unconstrained intrinsic motivation at curiosity coefficient $0.025$.

Why not just…?

Why not just rely on side observations and skip exploration bonuses entirely? In the default single-item inventory benchmark, this is probably the right answer. RLFG is already near-optimal within 20 episodes there, and we expect no gain. The proposal is only meaningful in the regime that sweep is built to probe. There, the uncensored states are rarely reached under the task reward, so side observations are rarely the informative kind. If RLFG without a bonus matches our method even at long lead times and far lookouts, the idea is falsified. We will report that outcome.

Why not just use a standard count or curiosity bonus, made safe with GRM? A visitation bonus rewards going where the agent has not been. With a feedback graph, the agent can have full information about a place it has never been. The visitation bonus will therefore send it to states the graph already covers for free, and will undervalue lookouts whose own pair is familiar but whose neighborhood is not. The GRM-shaped visitation ablation measures this directly. If it ties our method, the neighborhood term adds nothing and we drop it.

Why not just use IME and anneal its coefficient to zero? This is the most serious threat. Annealing also removes asymptotic bias. The difference is that annealing trades bias for exploration through a schedule that must be tuned per environment. GRM gives zero bias at every coefficient. Under equal tuning budgets, we will measure policy bias at a fixed step budget, for example average inventory held above the value-iteration optimum. We will also measure sensitivity across the annealing grid. If annealed IME matches both speed and final gap with comparable tuning effort, the shaping contribution is not worth its complexity. We would then report the neighborhood bonus as the only lasting contribution.

Why not just increase the replay ratio or prioritize replay by temporal-difference error? Topological Experience Replay reports two relevant findings. Raising the replay ratio causes Q-value overestimation. Uniform and prioritized replay need more than 80 updates on NChain, where ordered replay needs about 30. In any case, more replay cannot create data about states that were never observed. We include prioritized-replay RLFG as a secondary check.

Proposed Experiments

The primary metric follows Dorner's constant-performance threshold from Measuring Progress in Deep Reinforcement Learning Sample Efficiency: environment steps needed to reach a fixed fraction of the optimal return. We also report the final optimality gap and a coverage measure, the fraction of state-action pairs with low ensemble disagreement. Everything is averaged over at least 10 seeds with confidence intervals.

Three checks are decisive. First, as lead time or lookout distance grows, the step gap between our method and RLFG without a bonus should widen. In the same sweep, the visitation-bonus ablation should fall behind our method. Second, unshaped IME and the unshaped neighborhood bonus should show measurable, persistent bias, such as overstocking or detours to lookouts. The GRM variants should match the value-iteration optimum. Third, in the tabular gridworlds, episodes-to-threshold for our method should grow more slowly with computed $1/p_0$ than for the deep dominating-set baseline.