Comparative Evaluation of Bandit-Style Heuristic Policies for Moving Target Detection in a Linear Grid Environment Authors: Hyunmin Kang, Minho Ahn, Yongduek Seo Published: 2025 ABSTRACT Moving-target detection under strict sensing constraints is a recurring subproblem in surveillance, search-and-rescue, and autonomous robotics. We study a canonical one-dimensional finite grid in which a sensor probes one location per time step with binary observations while the target follows reflecting random-walk dynamics. The objective is to minimize the expected time to detection using transparent, training-free decision rules defined on the belief state of the target location. We compare two belief-driven heuristics with purely online implementation: a greedy rule that always probes the most probable location and a belief-proportional sampling (BPS, probability matching) rule that samples sensing locations according to the belief distribution (i.e., posterior probability of the target location). Repeated Monte Carlo simulations quantify the exploitation–exploration trade-off and provide a self-comparison between the two policies. Across tested grid sizes, the greedy policy consistently yields the shortest expected time to detection, improving by roughly 17–20% over BPS and uniform random probing in representative settings. BPS trades some average efficiency for stochastic exploration, which can be beneficial under model mismatch. This study provides an interpretable baseline and quantitative reference for extensions to noisy sensing and higher-dimensional search. 1. Introduction Moving target detection is of critical importance in domains such as defense, disaster response, and surveillance robotics, where platforms must localize potentially hostile or vulnerable objects under severe sensing constraints. In this paper, however, we do not attempt to model a full operational system in these domains. Instead, we study a stylized one-dimensional linear-grid setting that abstracts a basic sensing subtask, for example, repeatedly scanning along a corridor, border segment, or pipeline, in order to isolate core algorithmic trade-offs while keeping the model analytically and computationally tractable. Although real operational environments are inherently two- or three-dimensional, many deployed systems execute a search along preplanned one-dimensional paths, such as patrol routes, road segments, or scan lines generated by a higher-level planner. Our linear grid can thus be interpreted as an abstraction of a single such sweep, whose behavior can later be embedded into a broader 2D/3D coverage strategy. Within this simplified setting, the agent must locate the target quickly, an issue that has also been studied in classical search theory. In particular, when the probabilistic distribution of the target is known, it is well established that sequentially searching from the most likely locations yields an optimal strategy [1]. For example, in a static-target environment, probing the location with the highest probability maximizes the expected detection probability [1]. In dynamic settings, ref. [2] proposed related strategies from the perspective of dynamic hypothesis testing. However, these traditional approaches generally assume that the target’s motion model is known a priori and that the search path can be planned deterministically in advance. In recent years, research has expanded beyond offline search planning on known maps to include real-time online pursuit-evasion using mobile robots and unmanned aerial vehicles (UAVs). In addition, there has been growing interest in approximating partially observable Markov decision process (POMDP) problems with deep reinforcement learning. For example, ref. [3] compared a deep-RL solver with traditional point-based POMDP algorithms on an “olfactory search” POMDP and showed that lightweight policies learned by deep RL can be competitive. For rapid anomaly detection under limited resources, ref. [4] proposed an active hypothesis-testing framework based on the ref. [5,6] suggested a strategy that tracks a moving target on a graph by probing the second-most-likely location. Distinct from these prior studies, this work analyzes simple bandit-style heuristic policies, inspired by reinforcement-learning and restless-bandit theory, in a stylized moving-target detection setting and evaluates them with the objective of minimizing the expected time to detection (ETTD). Rather than implementing any explicit learning algorithm, we focus on closed-form online decision rules that can be executed directly on the belief state without computing a complex optimal policy. The central scientific question of this study is as follows: to what extent can simple, interpretable, training-free belief-based heuristics serve as effective online baselines for moving-target detection under strict sensing constraints? Specifically, we address three research questions:(RQ1) How do greedy (maximum-belief) probing and belief-proportional probing differ in ETTD and in the overall detection-time distribution under the reflecting random-walk model?(RQ2) What exploitation–exploration trade-off emerges between greedy (maximum-belief probing) and BPS (belief-proportional sampling), and when can stochastic exploration improve robustness (e.g., reduced sensitivity to local belief peaks or model mismatch)?(RQ3) How do the comparative trends scale with the grid size, and what quantitative performance gaps can be established as a reusable baseline for future extensions? (RQ1) How do greedy (maximum-belief) probing and belief-proportional probing differ in ETTD and in the overall detection-time distribution under the reflecting random-walk model? (RQ1) How do greedy (maximum-belief) probing and belief-proportional probing differ in ETTD and in the overall detection-time distribution under the reflecting random-walk model? (RQ2) What exploitation–exploration trade-off emerges between greedy (maximum-belief probing) and BPS (belief-proportional sampling), and when can stochastic exploration improve robustness (e.g., reduced sensitivity to local belief peaks or model mismatch)? (RQ2) What exploitation–exploration trade-off emerges between greedy (maximum-belief probing) and BPS (belief-proportional sampling), and when can stochastic exploration improve robustness (e.g., reduced sensitivity to local belief peaks or model mismatch)? (RQ3) How do the comparative trends scale with the grid size, and what quantitative performance gaps can be established as a reusable baseline for future extensions? (RQ3) How do the comparative trends scale with the grid size, and what quantitative performance gaps can be established as a reusable baseline for future extensions? The remainder of this paper is organized as follows: Section 2 reviews related work, followed by the problem definition in Section 3. Section 4 introduces the belief update mechanism and the decision rules for greedy and BPS policies. Section 5 analyzes their performance through simulations, and Section 6 discusses the results. Finally, Section 7 concludes with directions for future research. The specific contributions of this paper are summarized as follows:We formulate single-target moving-target detection in a one-dimensional reflecting random-walk grid as a POMDP over a belief state, and we adopt the ETTD as the primary performance metric.We present two training-free, purely online heuristic policies with closed-form decision rules—(i) greedy (maximum-belief probing) and (ii) belief-proportional sampling (BPS)—and we benchmark them against two simple baselines: ε-greedy (controlled exploration) and uniform random probing.Under the stylized 1D model, we provide an analytic characterization and interpretation of the two policies’ ETTD behavior, connecting the insights to classical sequential search and bandit-inspired decision-making.We conduct systematic simulations across grid sizes to quantify ETTD improvements and detection-time distributions, providing a transparent baseline for future extensions to noisy sensors and higher-dimensional settings. We formulate single-target moving-target detection in a one-dimensional reflecting random-walk grid as a POMDP over a belief state, and we adopt the ETTD as the primary performance metric. We formulate single-target moving-target detection in a one-dimensional reflecting random-walk grid as a POMDP over a belief state, and we adopt the ETTD as the primary performance metric. We present two training-free, purely online heuristic policies with closed-form decision rules—(i) greedy (maximum-belief probing) and (ii) belief-proportional sampling (BPS)—and we benchmark them against two simple baselines: ε-greedy (controlled exploration) and uniform random probing. We present two training-free, purely online heuristic policies with closed-form decision rules—(i) greedy (maximum-belief probing) and (ii) belief-proportional sampling (BPS)—and we benchmark them against two simple baselines: ε-greedy (controlled exploration) and uniform random probing. Under the stylized 1D model, we provide an analytic characterization and interpretation of the two policies’ ETTD behavior, connecting the insights to classical sequential search and bandit-inspired decision-making. Under the stylized 1D model, we provide an analytic characterization and interpretation of the two policies’ ETTD behavior, connecting the insights to classical sequential search and bandit-inspired decision-making. We conduct systematic simulations across grid sizes to quantify ETTD improvements and detection-time distributions, providing a transparent baseline for future extensions to noisy sensors and higher-dimensional settings. We conduct systematic simulations across grid sizes to quantify ETTD improvements and detection-time distributions, providing a transparent baseline for future extensions to noisy sensors and higher-dimensional settings. 2. Related Work The problems of searching for and tracking moving targets have been studied for a long time using a variety of approaches. Traditionally, search plans have been proposed to maximize the probability of detection within a finite time horizon for both static and moving targets [1,7]. For example, strategies that improve the efficiency of sequential search for static or moving targets have been presented in [1,7]; these studies typically adopt a planning-based approach that models target motion as a Markov chain. In robotics, alongside offline path planning that exploits known maps, online strategies have been proposed to track targets in real time within the sensor’s field of view. A survey of search/pursuit problems for mobile robots and a taxonomy of scenarios is provided in [8], while efficient path planning in indoor environments with multiple robots is studied in [9]. They showed that, given a known map, the robot path-selection problem is NP-hard and proposed scalable approximation algorithms based on finite-horizon planning and coordinated cooperation [9]. In contrast, when map information is unavailable, research has addressed cooperative search with multiple UAVs and optimal resource allocation. For cases in which map information is unavailable, Bayesian estimation-based cooperative UAV search has been proposed in [10], and a recursive Bayesian search-and-tracking algorithm using coordinated UAVs is presented in [11]. These techniques update the probability distribution of the target’s location in real time, thereby improving search strategies even under limited sensing resources. Recent years have also seen active research using reinforcement learning (RL). A deep reinforcement-learning approximation for an olfactory-search partially observable Markov decision process is compared with point-based methods in [3]. For multi-UAV cooperative search in three-dimensional environments, multi-agent learning-based cooperative search in three-dimensional settings is investigated in [12,13,14]. Collectively, these studies extend RL-based search problems to 2D/3D spaces, multi-agent settings, and dynamically moving targets, demonstrating the utility of learning-based approximations in lieu of solving the full POMDP exactly [15]. Beyond these domain-specific applications, recurrent deep RL architectures such as deep recurrent Q-networks (DRQN), asynchronous advantage actor–critic with long short-term memory (A3C-LSTM), and proximal policy optimization (PPO) have been proposed to maintain an internal memory of past observations, making them particularly suitable for POMDP settings. In this context, the present work does not aim to compete with such high-capacity controllers, but rather to provide a lightweight, analytically transparent baseline against which more expressive recurrent deep RL policies can be evaluated in future moving-target detection studies. In contrast to these deep recurrent approaches, the present work focuses on simple, closed-form policies (greedy and belief-proportional sampling) without any parameter learning, using them as interpretable reference baselines rather than as competitors to state-of-the-art deep RL controllers. Given the very high computational complexity of obtaining exact POMDP optima [16], the present work offers a new perspective based on approximate online learning. Related work includes analyses of why certain POMDPs are easier to approximate [17], Monte Carlo value iteration for continuous-state settings [18], and point-based algorithms such as Successive Approximations of the Reachable Space under Optimal Policies (SARSOPs) and related advances [19,20,21,22,23]. Likewise, indexability and bandit-theoretic analyses relevant to exploration are discussed in [24,25], and a general reinforcement-learning perspective is summarized in [26]. Finally, as noted in [26], learning-based approaches can serve as powerful alternatives even for complex decision-making problems. To clarify how our study relates to prior work and to highlight the motivation for our approach, Table 1 summarizes representative lines of research, along with their key advantages and limitations with respect to online moving-target detection under sensing constraints. This comparison helps identify the gap addressed by this paper: an analytically transparent, training-free baseline that bridges classical search theory and bandit-style sequential decision-making while directly targeting expected time to detection. As summarized in Table 1, prior work spans classical search theory, robotics planning, Bayesian multi-agent tracking, POMDP solvers, and deep RL. However, there remains a practical need for a simple, interpretable, and computationally lightweight benchmark that can be executed fully online without a training phase, while still capturing key POMDP characteristics through belief updates. Motivated by this gap, we focus on two closed-form bandit-style heuristics, greedy sensing based on the maximum belief and stochastic sensing based on belief-proportional sampling, and evaluate their trade-offs using ETTD as the primary metric. 3. Problem Definition In this work, the environment is a one-dimensional grid composed of N locations (slots) arranged linearly. The slots are connected in a line, where slot 1 and slot N correspond to the left and right boundaries of the grid, respectively. A single moving target exists on the grid and, at each discrete time step t=0,1,2…, occupies exactly one slot. Let Xt∈S denote the discrete target position at time t, where the finite state space (sample space) is S={1,2,…,N}. The target motion is modeled as a time-homogeneous Markov chain with transition matrix T, whose entries are defined by Tji≜P(Xt+1=j∣Xt=i),i,j∈S. Because Xt takes values on a finite, discrete set, all location distributions (including the belief state bt) are probability mass functions (PMFs) over S (i.e., categorical distributions), rather than probability density functions (PDFs), which are used for continuous-valued random variables. From an application viewpoint, such a one-dimensional grid can represent a discretized track along which a UAV, ground vehicle, or pan-tilt sensor repeatedly scans, for example, a corridor in a building, a pipeline or power line, a perimeter fence, or a coastline segment. In realistic two- or three-dimensional missions, a higher-level planner could decompose the workspace into a sequence of such linear tracks, and the policies analyzed in this paper would then govern the allocation of sensing effort along each track. In this sense, the present model should be viewed as a building block for larger 2D/3D search-and-tracking systems, rather than a full description of the entire operational space. The target’s motion model is given by a random walk as follows: Interior slot (2≤i≤N−1): at the next time step, the target moves to the left (i−1), stays (i), or moves to the right (i+1) with equal probability 13.Left boundary (slot 1): at the next time step, the target remains at the boundary with probability 23 or moves to the right (slot 2) with probability 13.Right boundary (slot N): at the next time step, the target remains at the boundary with probability 23 or moves to the left (slot N−1) with probability 13. Interior slot (2≤i≤N−1): at the next time step, the target moves to the left (i−1), stays (i), or moves to the right (i+1) with equal probability 13. Interior slot (2≤i≤N−1): at the next time step, the target moves to the left (i−1), stays (i), or moves to the right (i+1) with equal probability 13. Left boundary (slot 1): at the next time step, the target remains at the boundary with probability 23 or moves to the right (slot 2) with probability 13. Left boundary (slot 1): at the next time step, the target remains at the boundary with probability 23 or moves to the right (slot 2) with probability 13. Right boundary (slot N): at the next time step, the target remains at the boundary with probability 23 or moves to the left (slot N−1) with probability 13. Right boundary (slot N): at the next time step, the target remains at the boundary with probability 23 or moves to the left (slot N−1) with probability 13. These boundary probabilities (2/3 for staying and 1/3 for moving inward) are chosen to define a simple reflecting random walk that preserves the symmetry of the interior motion while enforcing hard boundaries on the finite grid. In the interior, the target has three symmetric options (move left, stay, or move right), and each is assigned a probability of 1/3. Formally, we start from the interior kernel P(Xt+1=i−1∣Xt=i)=P(Xt+1=i∣Xt=i)=P(Xt+1=i+1∣Xt=i)=1/3. At the left boundary i=1, the inadmissible outcome Xt+1=0∉S would receive probability mass 1/3; we fold (reassign) that mass onto the admissible “stay” event, giving P(Xt+1=1∣Xt=1)=1/3+1/3=2/3 and P(Xt+1=2∣Xt=1)=1/3 (analogously for i=N). At a physical boundary, the “outside” location is not admissible, so the probability mass that would have exited the domain is reassigned to the stay event, yielding a 2/3 chance of remaining at the boundary and a 1/3 chance of returning toward the interior. This construction leads to an ergodic Markov chain with nearly uniform stationary behavior and avoids introducing an artificial drift either toward or away from the boundaries. Similar reflecting random-walk models are widely used as minimal abstractions for diffusive motion in bounded domains in the search-theoretic literature [1,7]. While this equal-probability random walk is clearly a simplification relative to real targets, which may exhibit directional drift, dwell-time asymmetries, patrol patterns, or adversarial evasive maneuvers, we adopt it here as a canonical, symmetric baseline that isolates the effect of the sensing policy from higher-level motion planning. More general Markovian or semi-Markov motion models can be accommodated in the same framework by replacing the transition matrix T with any stochastic matrix capturing the desired dynamics; the belief-propagation step bt+1′=bt×T in Equation (4) and the greedy/BPS policies then remain unchanged. Under this model, the state transition of the target is represented by the transition matrix T, where P(Xt+1=j|Xt=i)=Tji, and the entries are summarized in Table 2. Sensors (agents) select one slot s∈{1,…,N} on the grid at each time step and can send a sensing signal to that location. The sensing outcome is a binary observation o∈{0,1}: if the target is present in the chosen slot, then o=1 (detection), otherwise, o=0 (miss). In this study, we assume an idealized binary sensor with perfect detection (probability of detection Pd=1) and no false alarms (probability of false alarm Pfa=0), so that the observation depends only on whether the target truly occupies the sensed slot. This assumption is adopted to isolate the effects of the motion model and the belief-update mechanism and to keep the analysis analytically tractable. In practical systems, 00. The target transition model and all remaining parameters follow Table 3. Figure 8 shows the mean detection time as a function of the grid size N for the ideal sensor (solid curves) and the noisy sensor with false alarms (dashed curves, Pd=0.8, Pfa=0.02). Introducing both missed detections and false alarms shifts the ETTD curves upward across all four policies, reflecting the additional uncertainty in the sensing process. However, the qualitative behavior of the policies is largely preserved. The greedy policy continues to yield the lowest mean detection time, while the random policy and BPS remain less efficient, with BPS suffering the most under this noise model due to its stronger exploratory behavior. The slopes of the noisy curves are similar to those of the ideal case, indicating that the increase in ETTD remains approximately linear in the grid size. Overall, these results suggest that the performance ranking of greedy, BPS, and random probing observed in the idealized setting is preserved even when moderate levels of both missed detections and false alarms are present. 6. Discussion The ideal detector (Pd=1, Pfa=0) should be interpreted as an optimistic upper-bound baseline rather than a realistic sensing model. Under Pd<1, repeated misses slow evidence accumulation and typically increase ETTD, while Pfa>0 can distort termination statistics unless additional confirmation logic is introduced. The sensitivity study in Section 5.5 (Figure 8) is included to partially close this realism gap by quantifying how moderate missed detections and low-rate false alarms affect the performance trends. Before discussing the quantitative trade-offs between the two policies, it is important to clarify the scope of applicability. The simulation results in Section 5 provide direct evidence to answer the research questions posed in Section 1. For RQ1, the detection-time statistics and distributional plots show that the greedy policy consistently achieves a lower expected time to detection than belief-proportional sampling, while also revealing differences in variance and tail behavior. For RQ2, the empirical distributional comparisons highlight the exploitation–exploration trade-off: greedy concentrates sensing on the current belief peak, whereas BPS injects stochastic exploration that can improve robustness under uncertainty. For RQ3, the multi-N experiments quantify how the performance gaps scale with grid size, establishing a reusable quantitative baseline for future extensions to noisier sensors and higher-dimensional search. Our model deliberately omits many factors that are crucial in realistic defense, disaster-response, and surveillance-robotics deployments, such as 2D/3D geometry, occlusions, multi-sensor coordination, communication constraints, and hardware-level imperfections. The goal of this study is not to provide an end-to-end field-ready system, but rather to analyze, in isolation, a canonical “linear search under limited sensing resources” motif that can appear as one component within larger planning architectures. Accordingly, the results should be interpreted as providing conceptual insight and quantitative baselines for such subproblems, while bridging the gap to full-scale applications will require richer motion models, sensor noise, and hardware-in-the-loop validation in future work. For instance, the current equal-probability random-walk assumption does not capture many realistic behaviors such as drift along road networks, environment-dependent stopping patterns, or adversarial avoidance of sensed regions; extending the proposed policies to such structured motion models is a key step toward operational deployment. In particular, a more realistic validation pipeline would couple the proposed policies with physical sensors (e.g., radar, lidar, or vision-based detectors) and systematically inject measurement noise, false positives, and missed detections in order to quantify how the belief-update mechanism and ETTD degrade under non-ideal conditions. Moreover, the present simulations employ an idealized binary detection/miss model (Table 3) without explicit detection and false-alarm parameters; extending the framework to imperfect sensors with specified Pd and Pfa values is an important direction for making the results more representative of real-world sensing systems. Synthesizing the experimental results, the proposed greedy policy achieved the lowest ETTD and thus favored faster detection, which aligns with intuition from classical search theory. However, the greedy policy risks repeatedly probing an incorrect slot when the belief estimate is wrong, and its performance can degrade sharply if the target’s motion model changes or the environment is noisy. By contrast, the BPS policy explores diverse slots in the early stages, offering the possibility of recovery from misspecified beliefs and exhibiting greater robustness to environmental variability. While our current linear-grid experiments focused on varying grid sizes and sensor noise, the literature suggests that such probabilistic exploration can offer the possibility of recovery from misspecified beliefs [27]. In field settings where the target’s motion characteristics are unknown or highly variable, the probabilistic nature of BPS can be advantageous. To understand the trade-off between the two proposed policies (greedy and BPS) more structurally from the standpoint of restless MABs, note that the greedy policy reduces the search space by always selecting the slot with the highest belief, whereas BPS balances exploration and exploitation in a probabilistic manner [28]. Although the Whittle-index policy [24] can be near-optimal in theory, its computational complexity makes real-time, online deployment difficult. In addition, Tong et al. [29] proposed a federated-learning-based distributed RMAB framework to address multi-agent cooperation. Future work could leverage such learning-based approaches to approximate the Whittle index or to extend the problem to more complex settings, such as two-dimensional grids and multiple targets. In particular, with multiple targets, the problem can be generalized to a multi-bandit formulation by maintaining independent beliefs per target, and, following cooperative UAV search studies [10], information sharing among multiple agents could further improve search efficiency. Beyond one-dimensional environments, generalizing to two-dimensional grids or real terrain would be valuable for practical applicability. In multi-dimensional grids, a naive extension of the greedy policy would still perform an O(N) argmax over all cells, but the curse of dimensionality manifests through increasingly fragmented belief landscapes and a proliferation of local maxima. As a result, a direct greedy rule may prematurely focus on a single mode of the belief map and neglect competing hypotheses unless it is combined with spatial hierarchy (e.g., sector-based or scanline-based decomposition), receding-horizon planning, or stochastic exploration components. A promising direction is to treat the one-dimensional policies studied in this paper as primitives that operate along individual tracks or sectors within a larger 2D/3D workspace, while higher-level planners coordinate between tracks to manage both computational load and the risk of local optima. In particular, a natural next step is to instantiate these policies on discretized 2D and 3D grids and quantitatively test whether the relative efficiency and robustness trends observed in our one-dimensional setting persist under more realistic geometric layouts, sensing footprints, and operational constraints. Overall, Section 5 and Section 6 establish consistent empirical evidence and an interpretable mechanism-level explanation for the observed trade-offs between exploitation-driven and exploration-driven sensing. In particular, the results clarify when a belief-argmax rule is advantageous for minimizing expected time to detection and when stochastic belief-proportional sampling can offer robustness against misspecification and uncertainty. These findings, together with the stated modeling limitations, position the present study as a quantitative baseline rather than a field-ready solution. We therefore conclude by consolidating the answers to the research questions, the added value of the benchmark, and the practical challenges that arise when extending the framework to noisier sensors and higher-dimensional deployments. 7. Conclusions This study proposed and evaluated reinforcement-learning-inspired, bandit-style heuristic sensing policies for moving target detection in a partially observable one-dimensional linear-grid environment with binary observations. We focused on training-free decision rules defined directly on the belief state: a greedy belief-argmax heuristic (RMAB-inspired; not a Whittle-index policy) and a belief-proportional sampling (probability-matching) policy, with an ε-greedy baseline (ε = 0.1) and a uniform random policy for reference. Our simulation results demonstrate that the greedy policy consistently achieves a lower mean ETTD across various grid sizes compared to the baselines. The belief heatmaps offer a mechanistic interpretation of policy behavior: greedy sensing concentrates measurements near the belief peak, whereas BPS injects stochastic exploration that can reduce persistent fixation on incorrect hypotheses under uncertainty. Finally, multi-N comparisons quantify how performance gaps scale with problem size, establishing a reusable quantitative baseline for subsequent studies. Overall, the added value of this paper is an analytically transparent and computationally lightweight benchmark that can be executed online without a training phase. Practical implementation challenges arise when moving beyond the idealized setting, including sensitivity to transition-model mismatch, increased computational burden in higher-dimensional deployments, and degradation under missed detections and false alarms. Future work will extend the framework to multiple targets and higher-dimensional grids, incorporate richer sensor/target models, and evaluate learning-based approaches that learn compact belief representations to test whether the observed trends persist in noisier deployments.