Learning Unknown Pollution Costs Without Exploring

Many control problems in energy and operations share a convenient property. Most of their randomness, such as weather, electricity prices, building demand or grid carbon intensity, evolves on its own, whatever the controller does. Recent theory shows that in these "exogenous" problems a controller can skip deliberate exploration entirely and simply act on its current best estimate. The catch is that this only holds if everything except the outside randomness is known in advance. Real plants and buildings also produce undesirable outputs: emissions, demand peaks, waste. These are by-products of useful production, and the coefficients linking actions to them (battery losses, combustion efficiency, how a control move shows up in net load) are usually not known. The theory says that once such a coefficient is unknown, pure exploitation can fail permanently.

We propose to close this gap with a structural condition. Undesirable outputs cannot be freely discarded; they are physically tied to production. Exogenous demand forces a controller through many different operating points no matter what it prefers. We ask when this forced variation is enough to learn the unknown pollution coefficients for free. We then ask whether a controller that is greedy about rewards and cautious only about pollution can learn at the optimal rate and keep pollution caps without ever adding an exploration bonus. The claim fits in two sentences. When outside randomness pushes the controller's pollution-relevant features in every direction, it learns unknown emission costs as a side effect of exploiting. Pessimism about those costs then enforces caps without stalling learning.

Core Claim

The closest existing work is Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?. It studies an exogenous Markov decision process (Exo-MDP), meaning a sequential decision problem whose state splits into a part the agent controls and a part driven by outside randomness. In this setting it proves that a least-squares value iteration algorithm with no exploration bonus, called LSVI-PE, gets regret polynomial in the feature dimension and independent of the size of the continuous controllable state. The same paper also proves a negative result that constrains our design. If the rewards or the controllable dynamics are unknown, pure exploitation suffers linear regret. Its algorithm has a single scalar reward and no notion of by-products or caps.

Our claim is that this negative result has a large escape hatch whenever the unknown quantity is an undesirable output whose features are pushed around by the outside randomness. We write the vector of undesirable outputs as linear in known features. For output $j$, the observed amount is $b_j = \langle \theta_j, \psi(x,a,\xi)\rangle + \text{noise}$, where $x$ is the controllable state, $a$ the action, $\xi$ the exogenous state, $\psi$ a known $d$-dimensional feature map, and $\theta_j$ an unknown coefficient vector. The desirable reward and the controllable dynamics stay known, as in LSVI-PE. Each output $j$ has its own cap $\tau_j$, rather than being folded into one budget. This reflects the main lesson of the undesirable-output literature: different by-products have independent slacks and should not be scaled proportionally The Classification Impact of Different Types of Environmental Regulation on Chinese Provincial Carbon Emission Efficiency.

The structural condition we propose is exogenous forcing. For every policy $\pi$ in the class the agent might play, the average feature second-moment matrix it induces is bounded below:

$$\mathbb{E}_{\xi,\pi}\big[\psi(x,a,\xi)\psi(x,a,\xi)^\top\big] \succeq \lambda_0 I, \qquad \lambda_0 > 0.$$

This is the multi-step analogue of the condition in Stochastic Linear Contextual Bandits with Diverse Contexts. That paper shows that in a single-step bandit, greedy play gives constant regret once the regions where each arm is chosen span the feature space. It is also the analogue of the smoothing argument in Smoothed Adversarial Linear Contextual Bandits with Knapsacks, where Gaussian jitter on contexts keeps the minimum eigenvalue bounded away from zero.

Under forcing, the least-squares error on each $\theta_j$ after $n$ episodes shrinks like $\sqrt{d \log n/(\lambda_0 n)}$, which is the standard ridge-regression rate with $n\lambda_0$ as the effective information. A controller that inflates each estimated cost by this width can therefore keep every cap with high probability. Because the width shrinks without any exploratory action, the price of caution vanishes at a $\sqrt{K}$ rate over $K$ episodes. We conjecture regret $\widetilde{O}(\mathrm{poly}(d,H,|\Xi|)\sqrt{K}/\lambda_0)$, where $H$ is the episode length, $|\Xi|$ is the number of exogenous states, and the $1/\lambda_0$ dependence is inherited from the eigenvalue argument. We also expect a matching lower-bound construction showing that as $\lambda_0 \to 0$ we recover the linear regret of the original negative result.

Research Program

The algorithm, which we call pessimistic-greedy LSVI, makes one change to LSVI-PE. It keeps the known-reward backward value iteration and the anchor-state machinery, and it adds no bonus to rewards. At each step it restricts actions to those whose upper-confidence pollution estimate $\langle \hat\theta_j,\psi\rangle + \beta\|\psi\|_{\Lambda^{-1}}$ stays below $\tau_j$ for every $j$. Here $\Lambda$ is the regularized Gram matrix of observed features and $\beta$ is a confidence radius.

This deliberately splits apart the two halves of SLUCB-QVI from Safe Reinforcement Learning with Linear Function Approximation. That algorithm pairs optimism on rewards with pessimistic ellipsoidal safe sets on a single linear cost. It needs a known safe seed action and a star-convex action set, and its regret bound is $\widetilde{O}(\kappa\sqrt{d^3H^3T})$. We keep its pessimism, drop its optimism, and replace the seed-action argument with forcing. The natural worry is that pessimism plus greed freezes: the agent avoids uncertain actions and so never learns about them. Forcing answers this, because the outside randomness moves the features even inside the cautious action set. The theoretical work has three parts. We will prove the regret and zero-violation guarantee under forcing. We will give checkable sufficient conditions for forcing in storage problems, for example that demand or price states push net load across both charging and discharging regimes. We will also characterize what happens under misspecification, when $b_j$ is only approximately linear.

The undesirable-output literature plays two further roles beyond motivating separate caps. First, its weak-disposability axiom, which says pollution cannot be cut to zero without cutting production, is what makes forcing plausible. If demand must be served, the polluting features must move. Second, it supplies the evaluation lens. Aggregate scores in prior work hide which by-product a controller over-produces. We will score each learned policy with a non-radial slacks-based measure (SBM) against the empirical frontier of all evaluated policies, following the per-output slack decomposition used in Productivity Decomposition of Chinese Energy Generation Enterprises: an Index Calculation Approach Embedded in the Data Envelopment Analysis Framework and The Impacts of Market Segmentation on Thermal Power Generation Efficiency. Here SBM is a reporting device, not part of the learning objective. That panel dataset has no emissions column, so it cannot calibrate an environment, and we will not use it as one.

Baselines

The naive reference point is plug-in greedy control with no pessimism. It runs LSVI-PE with estimated pollution coefficients treated as truth and the caps applied to point estimates. It costs nothing extra and shows how often certainty-equivalence violates caps before its estimates settle. It doubles as the ablation that isolates our one new ingredient, the pessimistic cost set. We count ourselves as beating it if we match its long-run reward while cutting early-episode violations to near zero.

A second ablation removes forcing rather than pessimism. We hold the controller fixed and shrink the exogenous variability, sweeping $\lambda_0$ toward zero. Regret should degrade in proportion to $1/\lambda_0$ and should become linear at the limit the theory predicts. If performance stays flat as forcing disappears, our explanation is wrong.

The strongest principled competitor is SLUCB-QVI from Safe Reinforcement Learning with Linear Function Approximation, extended in the obvious way to one pessimistic set per output. On its own modified Frozen Lake task it reports 0% safety violations. No empirical regret number is reported on Lacuna for that benchmark. It is the strongest competitor because it already guarantees safety under unknown linear costs; the only open question is whether its reward optimism is wasted effort when forcing holds. We run it with the same features, confidence radius $\beta$, anchors and episode budget, and tune its bonus scale over the same grid size we use for $\beta$. Beating it means equal 0% violations with lower cumulative regret on forced Exo-MDPs.

We also run an optimistic LSVI-Opt-style baseline without safe sets. Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation? reports qualitatively that LSVI-PE "consistently outperformed" LSVI-Opt on its synthetic storage task, but no numerical regret value is reported on Lacuna. This baseline tells us whether that advantage survives once costs are unknown.

On CityLearn the strongest existing system is ZO-iRL from Winning the CityLearn Challenge: Adaptive Optimization with Evolutionary Search under Trajectory-Based Guidance. It is a convex-optimization controller whose virtual-price parameters are tuned by guided evolutionary search. It reports an overall score of 0.944, against 1.070 for the runner-up, plus a ramping score of 0.781 and a peak-demand score of 0.962, where the rule-based controller scores 1.000 and lower is better. The best listed baseline on ramping, MARLISA, scores 1.022. Because no code resource is listed, we will reimplement ZO-iRL under the challenge's evaluation protocol and report both the reimplementation and the published figure. We will claim a win only on the reimplemented comparison under identical data and evaluation years. We do not expect to beat 0.944 overall. The realistic target is to come within a few points of it while meeting explicit per-output carbon and peak caps that ZO-iRL does not enforce, and while carrying a guarantee.

Why not just…?

Why not just subtract a weighted pollution penalty from the reward and run greedy control? If the pollution coefficients are unknown, the penalized reward is itself unknown. That is exactly the regime where the negative result of Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation? predicts linear regret absent forcing. Scalarization does not escape the problem; it hides it. A penalty also controls caps only on average. Safe Reinforcement Learning with Linear Function Approximation reports that penalty-in-reward baselines frequently violated constraints early in learning. We include a tuned-$\lambda$ penalty baseline and report early violations per output. If it matches us on both regret and violations, the per-output pessimism is unnecessary.

Why not just use optimism, which is known to be rate-optimal? Optimism is safe when nature does not explore for you. Two pieces of evidence suggest it is wasted when nature does. In exogenous problems, the comparison in Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation? found forced exploration slowed learning. Across 516 datasets in A Contextual Bandit Bake-off, plain greedy finished a close second to RegCB-opt, often with no significant difference. This is a real threat on weakly forced instances. The $\lambda_0$ sweep settles it, because there should be a crossover value of $\lambda_0$ below which SLUCB-QVI wins, and we will report where it lies.

Why not just add a little random dithering to the greedy controller? This is the most dangerous alternative, because small random action noise is cheap and may supply whatever diversity forcing lacks. Two things count against it here. Dithering by definition sometimes takes actions outside the cautious set, so it trades violations for information. Under strong forcing it also buys nothing. We run $\epsilon$-dithered pessimistic-greedy control over a grid of $\epsilon$ values. If some small $\epsilon$ dominates us across the $\lambda_0$ sweep at zero violations, we will report that the right recommendation is "pessimism plus tiny dithering" and that forcing is not needed.

Why not just train a deep actor-critic on CityLearn? The CityLearn report states that SAC, PPO and TD3 baselines struggled even after a year of training data and were beaten by ZO-iRL. Deep function approximation also gives up the guarantees we are after, as the divergence results in Convergent TREE BACKUP and RETRACE with Function Approximation illustrate. We include SAC under the same data budget only as a reference row.

Proposed Experiments

The first testbed is the synthetic continuous storage environment from Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?, which has continuous stored energy and discrete exogenous prices. We add two undesirable outputs with unknown linear coefficients and separate caps: conversion losses tied to charge rate, and peak grid draw. We control $\lambda_0$ by changing how strongly the exogenous demand states push the storage level across operating regimes. The metrics are cumulative regret against the cap-respecting optimum, per-output violation rate per episode, and the measured minimum eigenvalue of the feature Gram matrix. The decisive check is the predicted shape: pessimistic-greedy beats SLUCB-QVI at large $\lambda_0$, loses at small $\lambda_0$, and its regret scales roughly as $1/\lambda_0$.

The second testbed is the modified Frozen Lake task from Safe Reinforcement Learning with Linear Function Approximation, used as a negative control. It has no exogenous forcing, so pessimistic-greedy should stall, and SLUCB-QVI should keep its advantage. If our method wins there, the forcing story is not the explanation.

The third testbed is the 2021 CityLearn Challenge. Grid carbon intensity, weather and solar generation are exogenous. We treat storage efficiency and the map from control actions to net load as unknown linear coefficients, and we impose caps on carbon and on daily peak. The evaluation uses the challenge's six normalized metrics and the overall score, a per-output SBM slack score against the frontier of all evaluated controllers, and violations of the caps. Because CityLearn dynamics are not exactly linear, this testbed doubles as the misspecification check. The outcome that would sink the proposal is caps violated at the predicted confidence level even though the measured eigenvalue is healthy. That pattern would mean model error, not lack of exploration, is the binding problem in real storage control.