REVIEW 4 major objections 6 minor 41 references
Optimizing Sensor Redundancy in Sequential Decision-Making Problems
T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read A second-order quadratic approximation of expected return, solved as a binary quadratic program, identifies optimal backup-sensor configurations in reinforcement-learning deployments and matches brute force wherever that could be checked.
desk verdict A practical first cut at a real RL robustness problem, with an unproven NP-hardness claim and an unquantified second-order truncation; worth refereeing after fixes. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the quadratic expected-return surrogate built from single-sensor and pair-wise dropout returns. For each pair (i,j), the algorithm estimates \hat{R}(i,j), the policy's return when both sensors fail for an episode, using a momentum-guided budget allocation (Algorithm 1) that preferentially samples pairs whose mean return is still shifting the most. These estimates feed the interaction terms \$\Delta$\hat{R}(i,j)(d), and the full objective is the QUBO Hamiltonian H = -H_soft + \$\beta$ \$\alpha$ H_hard, where the hard term encodes the budget constraint using a binary representation of costs. The backup operation enters by replacing the dropout probability d_i with $d_i^{2}$, so the surrogate expresses redundancy as a change in the failure distribution rather than as a separate system state.
What would settle it
On an environment with dropout probabilities high enough that the probability of three or more simultaneous failures is substantial (say above 20%), enumerate every backup configuration by brute force and compare the true optimum with SensorOpt's QUBO recommendation; any mismatch would show the second-order truncation can mis-rank configurations.
Extended reading notes
Core claim
The paper's central claim is that a second-order expansion of the expected return in the binary backup variables is a faithful surrogate for the true expected return in a Markov decision process with per-episode sensor dropouts. Concretely, if sensor i drops out with probability d_i and a backup squares that probability, the expected return of a backup configuration x is approximated by \hat{R}(d) plus linear terms x_i \$\Delta$\hat{R}(i,i)(d) and pair interaction terms x_i x_j \$\Delta$\hat{R}(i,j)(d), where the interaction terms capture the joint value of backing up two sensors. Minimizing the negative of this approximation together with a cost-penalty term yields a QUBO instance whose best solution the authors take to be the optimal backup configuration. In experiments, the QUBO optimum coincided with the brute-force optimum on CartPole-v1, Acrobot-v1, LunarLander-v2, and Hopper-v2, and produced backup sets that outperform the no-backup baseline on the larger environments.
Load-bearing premise
The approximation assumes that episodes in which three or more sensors fail at once are so unimportant that ignoring them cannot change which backup configuration looks best.
Editorial extensions
If this is right
- On any problem instance where the second-order approximation ranks configurations faithfully, SensorOpt's answer is optimal for the original budgeted problem, regardless of which QUBO solver is used.
- The cost of evaluating the surrogate grows polynomially, roughly O(n^2) pair-return estimates plus a QUBO solve, instead of O(2^n) full evaluations, so the method scales to systems with many sensors.
- Backing up a sensor reduces its effective dropout probability from d_i to d_i^2, which concentrates the value of redundancy on high-dropout sensors; SensorOpt's linear and quadratic terms quantify that value.
- In the four environments where the true optimum was computable, the approximation preserved the identity of the best configuration, not merely the shape of the return landscape.
- The robot-arm grasping result indicates the approach transfers from small benchmark tasks to a continuous-control problem with a neural-network policy.
Reading between the lines
- A reader can test the boundary of the surrogate by raising dropout probabilities until three or more simultaneous failures are common; if SensorOpt then diverges from brute force, the divergence is attributable to the second-order truncation rather than to the solver.
- The same QUBO construction could be repurposed for other redundancy decisions, such as choosing which parts of an observation vector to duplicate or which communication links to back up, whenever a backup can be modeled as squaring a failure probability.
- Adding third-order terms to \hat{R}(d) would cost O(n^3) extra estimates; comparing second-order and third-order optima on medium-size environments would quantify how much ranking fidelity each additional term buys.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses the problem of selecting backup sensor configurations for a trained reinforcement learning policy under a budget constraint. The authors model the expected return of a configuration through a second-order approximation based on pairwise dropout return estimates, encode the resulting surrogate objective together with a cost penalty as a QUBO, and optimize it with Tabu Search ('SensorOpt'). They evaluate the method on eight OpenAI Gym environments and a custom Unity-based RobotArmGrasping environment, and report that SensorOpt matches a brute-force optimum in the four environments where brute force is feasible. A secondary contribution is an adaptive episode-allocation scheme (Algorithm 1) for estimating pairwise dropout returns.
Significance. If the central claim holds, the paper offers a practical and relatively simple way to tackle a relevant deployment problem: deciding which sensors to back up in an RL system with limited budget. The problem formulation is clean, and the idea of using empirically estimated pairwise return interactions to build a QUBO is sensible. The comparison against brute-force optima on four environments is a useful sanity check, and Algorithm 1's momentum-based allocation is an interesting proposal with preliminary supporting evidence. However, the paper's theoretical and empirical support is currently incomplete: the NP-hardness proof is invalid, the QUBO objective is only a truncated version of the paper's own return model with no bound on the omitted higher-order terms, and the figures rely on unexplained scaling constants. These issues do not necessarily invalidate the empirical findings, but they need to be addressed before the claims can be accepted.
major comments (4)
- [Section 3.2, Proposition 1] The NP-hardness proof is not a valid polynomial-time reduction. The construction defines a separate MDP E_x for each candidate solution x and sets the reward r(s0,a0)=x·v, so the problem instance itself depends on the unknown decision variable; moreover, setting d=0 means the backup configuration has no effect on the return, so the Knapsack value cannot be recovered from the optimum of a single reduced instance. The NP-hardness claim may be true, but this proof does not establish it and should be replaced or removed.
- [Section 3.2, definition of \hat R(d) and Eq. (3)] H_soft is at most quadratic in x, but \hat R(d^x) is a ratio of degree-n polynomials in x. For n≥3, the difference \hat R(d^x)-\hat R(d) contains triple and higher products of the x_i, for example through the factor \prod_i(1-d_i^x). Consequently, the QUBO minimizes a second-order truncation of the paper's own renormalized return model, not that model itself. The experiments do not quantify the magnitude of these higher-order terms. Please provide an empirical or theoretical bound, for example by comparing the ranking induced by the full \hat R(d^x) with the ranking induced by H_soft on the brute-force environments, and by reporting the size of the largest third-order interaction terms.
- [Section 5.1, Figure 2 and Section 5.2, Figure 3] The plotted approximation is E[R] = g(x^T Q x + c0), but the constants g and c0 are never defined or reported. Since adding a constant and multiplying by a positive scalar do not change the argmin of the QUBO, choosing g and c0 after seeing the data can make the curves appear arbitrarily well aligned. Please state how g and c0 are selected, report their values, or plot the raw -x^T Q x + \hat R(d) values instead.
- [Section 5.2, Table 2] The main empirical claim that SensorOpt matches the brute-force optimum in CartPole, Acrobot, LunarLander, and Hopper is not supported with sufficient statistical detail. The text says ten problem instances were sampled per environment, but Table 2 reports only one number per environment, with no standard deviations, no per-instance breakdown, and no information about how many of the ten instances actually matched the optimum. Please report the full distribution of results or clarify what the tabulated numbers represent.
minor comments (6)
- [Section 5.1, Table 1] In the proof-of-concept, the budget is C=390 while the total cost of all backup sensors is at most 19, so the cost constraint is inactive. This means the proof-of-concept does not exercise the constrained optimization part of the method; please either choose a binding budget or explicitly state that this experiment focuses only on the return approximation.
- [Section 3.2] The notation d^A is introduced with 'dA = ...', but the superscript is dropped in the displayed formula; please write d^A consistently.
- [Section 3.2] The term H_hard is a penalty term, not a hard constraint. The paper should clarify that the constraint is enforced softly through the penalty, especially because the magnitude of the penalty depends on the hyperparameter β.
- [Section 5.4, Figure 6] The comparison between Algorithm 1 and Round Robin is presented without error bars or a statistical test. Please add confidence intervals or a significance test, and specify how many seeds or independent runs the curves are based on.
- [Section 5.1] The text says a random problem instance was created and 'Real Expected Returns' were determined, but it does not explain how these real returns were computed. Please describe the procedure, including whether they come from simulation, exact evaluation, or a synthetic model.
- [Throughout] There are several formatting inconsistencies, such as 'RobotArmGrasping' being written with a space in the abstract and the Table 2 header 'N O BACKUPS' clearly being a spacing artifact. A careful proofread and consistent notation would improve the presentation.
Circularity Check
No significant circularity: the QUBO is built from empirical rollouts and validated against brute-force environment returns, not against its own construction.
full rationale
The derivation chain is not circular. The QUBO objective in Eq. (3) is constructed from empirical pairwise return estimates \hat R(i,j) obtained by rollouts in the actual environment, and the central evaluation compares the resulting configuration to the true optimum determined by brute-force enumeration of environment returns (Table 2). The approximation \hat R(d) and its truncation H_soft are the paper's model, but the claim that the solver finds optimal configurations is tested against independently measured returns, not against the model itself. The proof-of-concept in Figure 2 is a self-consistency check: its 'Real Expected Returns' are generated from the same synthetic R_ij table (Table 1) that defines \hat R, so it only shows that the quadratic truncation tracks the second-order model on that instance; it is not independent validation, but this does not make the central claim circular because the main experiments provide such validation. The self-citations (Nusslein et al. for QUBO solvers) are background and not load-bearing. The scaling factor g and offset used in the figures are rank-preserving and do not alter the optimal-configuration comparison. No step reduces by construction to its inputs; accordingly the circularity score is 0.
Assumptions & free parameters
free parameters (2)
- beta =
not reported
- g and c0 (plot scaling) =
not reported
assumptions (5)
- domain assumption Independent sensor and backup failures
- domain assumption Dropped sensors output zero vectors
- domain assumption Fixed trained policy pi, not retrained with backups
- ad hoc to paper Second-order truncation of the return
- ad hoc to paper Cost constraint encoded via binary slack variables
Cite this review
Pith. "Pith review of Optimizing Sensor Redundancy in Sequential Decision-Making Problems." pith.science (2026). https://pith.science/paper/BHIF7ZQV
@misc{pith2026241207686,
author = {Pith},
title = {Pith review of: Optimizing Sensor Redundancy in Sequential Decision-Making Problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/BHIF7ZQV}},
note = {Machine review of arXiv:2412.07686}
}
read the original abstract
Reinforcement Learning (RL) policies are designed to predict actions based on current observations to maximize cumulative future rewards. In real-world applications (i.e., non-simulated environments), sensors are essential for measuring the current state and providing the observations on which RL policies rely to make decisions. A significant challenge in deploying RL policies in real-world scenarios is handling sensor dropouts, which can result from hardware malfunctions, physical damage, or environmental factors like dust on a camera lens. A common strategy to mitigate this issue is the use of backup sensors, though this comes with added costs. This paper explores the optimization of backup sensor configurations to maximize expected returns while keeping costs below a specified threshold, C. Our approach uses a second-order approximation of expected returns and includes penalties for exceeding cost constraints. We then optimize this quadratic program using Tabu Search, a meta-heuristic algorithm. The approach is evaluated across eight OpenAI Gym environments and a custom Unity-based robotic environment (RobotArmGrasping). Empirical results demonstrate that our quadratic program effectively approximates real expected returns, facilitating the identification of optimal sensor configurations.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
Beeler, C., Li, X., Bellinger, C., Crowley, M., Fraser, M., and Tamblyn, I. (2021). Dynamic programming with incomplete information to overcome navigational uncertainty in a nautical environment. arXiv preprint arXiv:2112.14657
work page Pith review arXiv 2021
-
[3]
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). Openai gym. arXiv preprint arXiv:1606.01540
arXiv 2016
-
[4]
Bucher, D., N \"u lein, J., O'Meara, C., Angelov, I., Wimmer, B., Ghosh, K., Cortiana, G., and Linnhoff-Popien, C. (2023). Dynamic price incentivization for carbon emission reduction using quantum optimization. arXiv preprint arXiv:2309.05502
arXiv 2023
-
[5]
Choi, V. (2010). Adiabatic quantum algorithms for the NP -complete maximum-weight independent set, exact cover and 3SAT problems
work page 2010
-
[6]
Choi, V. (2011). Different adiabatic quantum optimization algorithms for the NP -complete exact cover and 3SAT problems
work page 2011
-
[7]
Degrave, J., Felici, F., Buchli, J., Neunert, M., Tracey, B., Carpanese, F., Ewalds, T., Hafner, R., Abdolmaleki, A., de Las Casas, D., et al. (2022). Magnetic control of tokamak plasmas through deep reinforcement learning. Nature , 602(7897):414--419
work page 2022
-
[8]
Dulac-Arnold, G., Mankowitz, D., and Hester, T. (2019). Challenges of real-world reinforcement learning. arXiv preprint arXiv:1904.12901
arXiv 2019
Show all 41 references
-
[9]
Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028
2014 arXiv
-
[10]
and Harrow, A
Farhi, E. and Harrow, A. W. (2016). Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674
2016 arXiv
-
[11]
Glover, F., Kochenberger, G., and Du, Y. (2018). A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538
2018 arXiv
-
[12]
Glover, F., Kochenberger, G., and Du, Y. (2019). Quantum bridge analytics I : A tutorial on formulating and using QUBO models
2019
-
[13]
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang, J., Yang, Y., and Knoll, A. (2022). A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv:2205.10330
2022 arXiv
-
[14]
Juliani, A., Berges, V.-P., Teng, E., Cohen, A., Harper, J., Elion, C., Goy, C., Gao, Y., Henry, H., Mattar, M., et al. (2018). Unity: A general platform for intelligent agents. arXiv preprint arXiv:1809.02627
2018 arXiv
-
[15]
and Ozcelikkale, A
Koseoglu, M. and Ozcelikkale, A. (2020). How to miss data? reinforcement learning for environments with high observation cost. In ICML Workshop on the Art of Learning with Missing Values (Artemiss)
2020
-
[16]
D., and Jansen, N
Krale, M., Sim \ a o, T. D., and Jansen, N. (2023). Act-then-measure: Reinforcement learning for partially observable environments with active measuring. arXiv preprint arXiv:2303.08271
2023 arXiv
-
[17]
Liang, Y., Sun, Y., Zheng, R., and Huang, F. (2022). Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning. Advances in Neural Information Processing Systems , 35:22547--22561
2022
-
[18]
Lodewijks, B. (2020). Mapping NP -hard and NP -complete optimisation problems to quadratic unconstrained binary optimisation problems
2020
-
[19]
Lucas, A. (2014). Ising formulations of many NP problems
2014
-
[20]
L \"u tjens, B., Everett, M., and How, J. P. (2020). Certified adversarial robustness for deep reinforcement learning. In conference on Robot Learning , pages 1328--1337. PMLR
2020
-
[21]
Mandlekar, A., Zhu, Y., Garg, A., Fei-Fei, L., and Savarese, S. (2017). Adversarially robust policy learning: Active construction of physically-plausible perturbations. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , pages 3932--3939. IEEE
2017
-
[22]
and Toth, P
Martello, S. and Toth, P. (1990). Knapsack problems: algorithms and computer implementations . John Wiley & Sons, Inc
1990
-
[23]
Mooney, G., Tonetto, S., Hill, C., and Hollenberg, L. (2019). Mapping NP -hard problems to restructed adiabatic quantum architectures
2019
-
[24]
Moos, J., Hansel, K., Abdulsamad, H., Stark, S., Clever, D., and Peters, J. (2022). Robust reinforcement learning: A review of foundations and recent advances. Machine Learning and Knowledge Extraction , 4(1):276--315
2022
-
[25]
and Nishimori, H
Morita, S. and Nishimori, H. (2008). Mathematical foundation of quantum annealing. Journal of Mathematical Physics , 49(12)
2008
-
[26]
A., Fleming, S., and Brunskill, E
Nam, H. A., Fleming, S., and Brunskill, E. (2021). Reinforcement learning with state observation costs in action-contingent noiselessly observable markov decision processes. Advances in Neural Information Processing Systems , 34:15650--15666
2021
-
[27]
N \"u lein, J., Roch, C., Gabor, T., Stein, J., Linnhoff-Popien, C., and Feld, S. (2023a). Black box optimization using qubo and the cross entropy method. In International Conference on Computational Science , pages 48--55. Springer
2023
-
[28]
N \"u lein, J., Zielinski, S., Gabor, T., Linnhoff-Popien, C., and Feld, S. (2023b). Solving (max) 3-sat via quadratic unconstrained binary optimization. In International Conference on Computational Science , pages 34--47. Springer
2023
-
[29]
Pattanaik, A., Tang, Z., Liu, S., Bommannan, G., and Chowdhary, G. (2017). Robust deep reinforcement learning with adversarial attacks. arXiv preprint arXiv:1712.03632
2017 arXiv
-
[30]
Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. (2017). Robust adversarial reinforcement learning. In International Conference on Machine Learning , pages 2817--2826. PMLR
2017
-
[31]
Quintero, R. A. and Zuluaga, L. F. (2021). Characterizing and benchmarking qubo reformulations of the knapsack problem. Technical report, Technical Report. Department of Industrial and Systems Engineering, Lehigh …
2021
-
[32]
Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. (2021). Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research , 22(268):1--8
2021
-
[33]
Rasmussen, R. V. and Trick, M. A. (2008). Round robin scheduling--a survey. European Journal of Operational Research , 188(3):617--636
2008
-
[34]
Roch, C., Ratke, D., N \"u lein, J., Gabor, T., and Feld, S. (2023). The effect of penalty factors of constrained hamiltonians on the eigenspectrum in quantum annealing. ACM Transactions on Quantum Computing , 4(2):1--18
2023
-
[35]
Salkin, H. M. and De Kluyver, C. A. (1975). The knapsack problem: a survey. Naval Research Logistics Quarterly , 22(1):127--144
1975
-
[36]
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347
2017 arXiv
-
[37]
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science , 362(6419):1140--1144
2018
-
[38]
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction . MIT press
2018
-
[39]
and Mori, D
Valdenegro-Toro, M. and Mori, D. S. (2022). A deeper look into aleatoric and epistemic uncertainty disentanglement. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) , pages 1508--1516. IEEE
2022
-
[40]
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J. (2020). Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems , 33:21024--21037
2020
-
[41]
Zielinski, S., N \"u lein, J., Stein, J., Gabor, T., Linnhoff-Popien, C., and Feld, S. (2023). Influence of different 3sat-to-qubo transformations on the solution quality of quantum annealing: A benchmark study. In Proceedings of the Companion Conference on Genetic and Evoluti...
2023
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.