{"id":"358428d8-c3ef-4ed8-bbd7-35b8a5caa3a6","arxiv_id":"2412.14614","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"BIOMAP achieves the optimal reward on the Mask Cliff Walking benchmark by reconstructing the state graph from action vectors, but this hinges on an unstated assumption that states are geometric positions.","lead":"BIOMAP is a model-free algorithm that uses an ant-inspired action-vector graph to solve deterministic partially observable MDPs, tested on a masked grid-world navigation task. The paper is worth reading to see whether the method generalizes beyond grid worlds, since its core assumption is that hidden states are recoverable from the agent's movement history.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"BIOMAP's state encoding assumes actions are translations on a vector space; general DET-POMDPs lack this structure, so the claimed model-free conversion is unsupported.","rationale":"The paper's strongest claim is that BIOMAP converts a general DET-POMDP into a fully observable MDP without a model. For that conversion to work, the graph vertex reached after an action sequence must be a faithful encoding of the hidden state. The algorithm's only state-encoding mechanism is cumulative vector addition, so a necessary condition is that the environment's state space admits a translation action by the action vectors with a bijection between states and reachable vectors. This is a strong geometric condition: it fails, for example, in any finite DET-POMDP whose transition graph is a cycle not generated by translations or whose actions map two distinct states to the same lattice point. The paper neither states this condition nor restricts the title or abstract to grid worlds. The experiments, all on Mask Cliff Walking, are therefore not evidence for the general claim; they are evidence only for translation-embedded environments. This is exactly the reader's weakest assumption, so I agree with the reader. Since this concern undermines the central claim and no formal verification or code is supplied, the REJECT verdict is unchanged. The proposed minimal test would settle the point: if BIOMAP nevertheless returns the optimal policy on a non-translation DET-POMDP, the concern would be retired; if not, the abstract and Sec. 4 overclaim.","tokens_in":22679,"tokens_out":4912,"duration_ms":38625,"concrete_test":"Instantiate a minimal non-translation DET-POMDP: S={A,B}, O={o}, A={a}, T(A,a)=B, T(B,a)=A, R(A,a)=+1, R(B,a)=-1, finite horizon 10, uniform initial distribution. Run BIOMAP (Alg. 2) exactly as specified. Because the update o'=o+a sends both A and B to the same node, the Compact Vector Graph has fewer vertices than S; record the returned policy and its mean return. Compare with the exact optimal value for this DET-POMDP (computed by belief-state dynamic programming). If BIOMAP's return is strictly below optimal, the claimed conversion of general DET-POMDPs into fully observable MDPs is falsified. A pass for the paper would require the Compact Vector Graph to remain isomorphic to S on this non-translation example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing assumption is that each hidden state can be recovered as the cumulative sum of action unit vectors. This enters at Def. 3 and Def. 4 (Sec. 3.3.2) and is executed by the update o' = o + a in Alg. 2 line 15 (and Alg. 1 line 18). For this update to identify states, the state space must be a subset of a vector space with each action acting as a fixed translation, so that the action history uniquely determines the state. Def. 1 imposes no such translation structure on S, T, or O. In a deterministic POMDP with S={A,B}, O={o}, and T(A,a)=B, T(B,a)=A, both states map to the same accumulated vector after one action; the Compact Vector Graph is then not isomorphic to S (Def. 5), and the computed policy cannot distinguish states with different rewards. The grid-world experiments satisfy the translation-embedding condition, but the paper never states it as a restriction, and the abstract claims general DET-POMDP conversion. The phase-2 determinism check cannot fix this: it only rejects the malformed graph after construction, and Alg. 2 then breaks instead of converting.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines DET-POMDP, a deterministic subclass of POMDPs with many-to-one observation mappings, and proposes a model-free algorithm called BIOMAP. The algorithm represents the agent's action history as a cumulative vector, builds a 'Compact Vector Graph,' checks the graph with a finite automaton, and then solves a shortest-path problem to obtain a policy. The authors claim this converts a general DET-POMDP into a fully observable MDP. The experimental section introduces a Mask Cliff Walking simulator with several masking settings and reports that BIOMAP matches the best model-based solvers while outperforming some online POMDP solvers.","tokens_in":22878,"tokens_out":7298,"duration_ms":52756,"significance":"If the conversion claim were correct, the paper would make a useful contribution to model-free planning in deterministic POMDPs. The path-integration analogy from desert ants is appealing, and the Mask Cliff Walking environment is a reasonable testbed for studying observation aliasing. However, the central theoretical claim is not established: the algorithm's state encoding requires a geometric translation structure that Definition 1 does not provide, the automaton-based determinism test is logically vacuous in light of NDFA/DFA equivalence, and the proofs of Lemmas 2 and 3 are not valid as written. The experimental success is essentially forced by the grid-world geometry. The paper does not provide machine-checked proofs, formal verification, or public code, and the central derivation depends on unstated assumptions.","major_comments":[{"comment":"The core state-encoding step o' = o + a (Alg. 2 line 15) requires the state space to be embedded in a vector space and each action to act as a fixed translation. Definition 1 imposes no such structure: S, T, and Omega are arbitrary finite sets and functions. Consider S={A,B}, O={o}, T(A,a)=B, T(B,a)=A, R(A,a)=+1, and R(B,a)=-1. From initial state A, after one action the cumulative action vector is the same for both states, the observation is o in both cases, and the Compact Vector Graph has one vertex for two states with different rewards. The bijection V <-> S required by Definition 5 therefore fails, and the graph is not an MDP representation of the DET-POMDP. The paper never states the translation-embedding assumption, although the grid-world experiments satisfy it.","section":"Sec. 3.3.2, Defs. 3-4; Alg. 2 line 15"},{"comment":"The determinism test is not a valid test of full observability. Theorem 4 correctly states the standard equivalence of NDFA and DFA, so every language generated by the NDFMA has a DFMA recognizing it. The subsequent claim that 'if a language is not recognizable by DFMA, then the corresponding MDP for that language is partially observable' is inconsistent with Theorem 4. Consequently, the check 'if M_Markov is not deterministic then Break' (Alg. 2 lines 24-25) cannot detect whether the graph corresponds to a fully observable MDP. Rejecting the graph after construction does not provide a conversion procedure for the general DET-POMDP.","section":"Sec. 3.4.4 and Alg. 2 lines 23-26"},{"comment":"The proofs of Lemmas 2 and 3 are not valid as written. In Appendix E, the proof asserts that the action history trajectory set is a subset of the alphabet Sigma, but the argument is circular because the claimed equality H = L_Markov is used in the definition of L_Markov, the statement 'forall a in exists circle ha' is incomplete, and the transition step 'w1 = a0w0' has the word concatenation backwards. In Appendix F, Lemma 3 is not proved: setting A=A' and S=S' and observing P(s|o) <= 1 only shows the transition relation is not a function; it does not construct a nondeterministic automaton whose accepted language is H', nor does it connect the automaton's acceptance to the POMDP trajectory semantics. Since Lemmas 2 and 3 are the stated basis for the MDP-Graph-Automaton conversion, this is a load-bearing gap.","section":"Appendices E and F (Lemmas 2 and 3)"},{"comment":"Line 11 tests 'o = o_vector', comparing the environment observation o with the action-vector label o_vector; these live in different spaces and the condition is not meaningful as written. If the condition is false, b is never assigned before being used in line 14; if the condition is true, Algorithm 1 may have inserted a self-loop while Algorithm 2 does not update the observation on the boundary branch. The boundary-detection mechanism therefore needs to be specified precisely; as written, the pseudocode does not define a valid algorithm.","section":"Alg. 2, lines 11-14"},{"comment":"The experiment only tests the translation-embedding case. In Mask Cliff Walking, grid states are identified by coordinates, and the cumulative sum of the four unit action vectors from the start recovers the grid cell exactly; masking changes only the observation labels and does not disturb this dead-reckoned encoding. Thus the observed success is a direct consequence of the geometric assumption identified in the first major comment, not evidence for the general DET-POMDP conversion claimed in the abstract. In addition, Table 1 shows BIOMAP tied with QMDP, SARSOP, and POMDPSolver at -2; the claim of 'superior capabilities' over existing POMDP solvers is not supported by the tabulated comparison.","section":"Sec. 4, Tables 1-2 and Fig. 5"}],"minor_comments":[{"comment":"The phrase 'states and observations are many-to-one relationships' is imprecise; the paper means that the observation function is many-to-one, not that the state-observation relation is itself many-to-one in both directions.","section":"Abstract and Sec. 3.1.1"},{"comment":"The expression 'not exists a_vector_prime, 0 < a_vector_prime < a_vector' uses a partial order on vectors that is never defined; the definition of an action unit vector should be stated in terms of an explicit embedding of actions into a normed vector space.","section":"Def. 3"},{"comment":"The labels '[5,2]=28' and '[5,3]=16' in Fig. 5(b) do not match any obvious coordinate-to-index convention (e.g., row-major indexing would give different values); the coordinate convention should be stated clearly.","section":"Fig. 5"},{"comment":"The term 'value episode' is used repeatedly where the standard term is 'value iteration' or 'value-function update'; this should be corrected throughout.","section":"Sec. 2"},{"comment":"The statement that in an 'extreme situation' the variance 'tends towards infinity' is not implied by the displayed finite formula for the variance of the Q-value error; this claim should either be removed or proved.","section":"Sec. 3.2, Theorem 1"},{"comment":"The most relevant baseline for deterministic POMDPs, namely Bonet's deterministic POMDP algorithms cited as reference [1], is not compared or discussed in the related-work section; some discussion of why these algorithms are not benchmarks would strengthen the paper.","section":"Related work"}],"recommendation":"reject","confidential_remarks":"The manuscript's central conversion claim rests on unstated geometric assumptions and on a misapplication of the NDFA/DFA equivalence theorem. These are not local presentation issues; a defensible version of the paper would need a different correctness argument and an explicit restriction of the problem class. I would not recommend encouraging a revision within the current scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is not the general model-free DET-POMDP solver it claims to be. The core move—tracking cumulative action vectors to reconstruct state—works only when the hidden state is exactly the agent's dead-reckoned position, i.e., when the state space is embedded in a vector space and actions act as translations. That condition holds for the grid-world experiments (up/right/down/left are unit translations) but is not part of Def. 1. The stress-test counterexample is sound: two states that toggle under an action and emit the same observation will both map to the same vector sum, so the Compact Vector Graph is not isomorphic to the state space, and the Boundary Arbiter cannot catch it—it will happily add a self-loop. The phase-2 determinism check breaks instead of converting, so the algorithm silently fails outside the translation-embedded case.\n\nWhat is actually new: the BIOMAP algorithm itself and the Mask Cliff Walking benchmark are new, and the bionic path-integration framing is a reasonable heuristic for grid worlds. The experiments are honestly executed and reported: BIOMAP reaches the same optimal reward as QMDP and SARSOP, not a better one, and its time cost is higher than both. The ANOVA mostly shows masking parameters have no effect, which undercuts the claim that the masking is a hard challenge.\n\nThe theory is the soft spot. Theorem 1 is a trivial variance identity. Lemmas 2 and 3 have garbled proofs (e.g., the notation collapses, and the conclusion 'we get the LM arkov' is not a sentence). Theorem 4 is a textbook NFA/DFA equivalence but does not license the jump from 'languages recognized by NDFMA' to 'DET-POMDP can be converted to a fully observable MDP.' Algorithm 2 line 11 compares an observation number to an action vector, which is a type error; line 15 uses the very update rule that presupposes translations.\n\nThe paper would be acceptable if it restricted its claim to deterministic POMDPs whose state space is a subset of a vector space with actions as translations, and if the proofs were rewritten. As written, the abstract's claim of 'convert DET-POMDP into a fully observable MDP' is unsupported.\n\nI would not send this to peer review in its current form. I'd suggest the authors narrow the scope, fix the proofs, and then try a workshop or a specialized venue. For a reading group, it's a useful case study in unstated geometric assumptions, but not a paper I'd cite.","headline":"The paper's central claim fails because BIOMAP reconstructs states from cumulative action vectors, which only works when the environment is translation-embedded—an unstated and nontrivial restriction.","tokens_in":23500,"tokens_out":5264,"would_cite":false,"duration_ms":49168,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","68Q45","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"By tracking its own action vectors, a model-free agent recovers optimal policies in deterministic POMDPs without knowing the environment's transition or observation model.","keywords":["DET-POMDP","model-free POMDP solver","biomimetics algorithm","path integration","Compact Vector Graph","Markov automaton","MDP-Graph-Automaton","cliff walking"],"falsifier":"Build a deterministic POMDP with four states arranged in a cycle where two adjacent states emit the same observation and actions are 'go clockwise' / 'go counterclockwise'; BIOMAP's action vectors will assign the same coordinate to states reached by different histories, so the Compact Vector Graph will not be isomorphic to the true state space, and the returned policy will be suboptimal. If BIOMAP still solves it optimally, the hidden uniqueness condition is not necessary.","tokens_in":22406,"feed_emoji":"🐜","tokens_out":4533,"duration_ms":34540,"temperature":0.7,"pith_summary":"This paper argues that a class of partially observable decision problems—deterministic POMDPs with many-to-one state-observation mappings—can be solved without any model of the environment. The authors propose BIOMAP, an algorithm that tracks the cumulative vector of the agent's own actions, much as a desert ant performs path integration, and builds a graph whose vertices are these dead-reckoned positions. They claim this graph is isomorphic to the true state space, turning the partially observable problem into a fully observable MDP that can be solved with a shortest-path algorithm. Experiments on a masked Cliff Walking task show BIOMAP reaching the same optimal policy as model-based solvers while using no transition or observation model. The paper also quantifies the 'Cognitive Fog' that aliased observations create, measuring the resulting bias in Q-values.","feed_headline":"Desert-ant trick turns hidden-state POMDPs into plain MDPs","feed_subtitle":"By tracking cumulative action vectors, BIOMAP reaches optimal policies without knowing the environment model.","key_machinery":"The Compact Vector Graph: a multigraph whose edges are action unit vectors and whose vertices are cumulative sums of those vectors, i.e., the agent's path-integrated position. Together with the Deterministic Finite Markov Automaton into which the graph is mapped, it lets the agent test whether the observed history is deterministic; if it is, the graph is taken as a full MDP. The Boundary Arbiter decides when repeated observations indicate a wall rather than a new hidden state, so the graph does not expand forever.","core_discovery":"The central claim is that in a deterministic POMDP, an agent that remembers only its own action history—encoded as a cumulative action vector—can reconstruct the hidden state space and recover the optimal policy. BIOMAP implements this by abstracting actions into unit vectors, recording each visited cumulative vector as a vertex of a 'Compact Vector Graph', and using a Markov automaton to check whether the resulting graph has deterministic transitions. If the check passes, the graph is declared a fully observable MDP and the optimal path is found by a shortest-path algorithm. On the Mask Cliff Walking benchmark, BIOMAP attains the same maximum reward as the best model-based solvers, with zero variance across masking configurations, while the model-free agent never sees the transition or observation function.","pith_inferences":["The hidden-state uniqueness condition is not stated explicitly by the paper: BIOMAP works when distinct states have distinct action-vector coordinates AND same observation only for states that are genuinely equivalent in transitions and rewards. A counterexample is a deterministic POMDP with a cycle in state space, where two different states share the same observation and the same incoming action ","Testable extension: run BIOMAP on a non-grid DET-POMDP where actions do not act as translations (e.g., a graph with a branching structure where two paths arrive at the same observation from different directions); the graph would collapse states and the policy would degrade.","The Q-value variance theorem quantifies Cognitive Fog, but the paper does not use it to predict when BIOMAP will fail; that threshold could be derived from the variance formula."],"forward_implications":["If BIOMAP's reconstruction is correct, any deterministic POMDP whose state space is a translation-invariant grid can be solved optimally without a model, matching model-based solvers.","The algorithm supplies a practical test for 'environmental deceptiveness': if the graph fails the determinism check, the environment is not reducible to a fully observable MDP by this method.","BIOMAP's zero-variance performance across masking settings in the experiments suggests the recovered policy is independent of which observations are aliased, as long as the dead-reckoned positions stay distinct.","The framework offers a finite-state representation of DET-POMDP trajectories, so planning reduces to a shortest-path problem on a graph of size at most the number of distinct cumulative action vectors."],"supporting_citations":[{"why":"Defines the deterministic POMDP model that the paper extends and studies.","marker":"[1]"},{"why":"Supplies the biological path-integration mechanism that inspires the action-vector tracking approach.","marker":"[29]"},{"why":"Provides the general POMDP formulation that DET-POMDP is a subclass of.","marker":"[3]"},{"why":"Supplies the QMDP baseline that BIOMAP is compared against in the experiments.","marker":"[11]"},{"why":"Supplies the SARSOP baseline, a model-based solver that BIOMAP matches in performance.","marker":"[22]"},{"why":"Provides the shortest-path algorithm used to extract the optimal policy from the reconstructed graph.","marker":"[40]"}],"fun_headline_variants":["Ant-inspired BIOMAP turns POMDPs into plain MDPs","Action memory alone unlocks hidden POMDP states","Model-free BIOMAP solves deterministic POMDPs","Desert ant trick: POMDPs solved as MDPs","BIOMAP: cumulative action vectors reveal hidden states"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Each hidden state is uniquely identified by the cumulative sum of the agent's action vectors, so no two different states can share both an observation and an action history, which is only true when states behave like positions in a vector space.","fun_headline_variants_meta":{"raw":{"variants":["Ant-inspired BIOMAP turns POMDPs into plain MDPs","Action memory alone unlocks hidden POMDP states","Model-free BIOMAP solves deterministic POMDPs","Desert ant trick: POMDPs solved as MDPs","BIOMAP: cumulative action vectors reveal hidden states"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1439,"prompt_tokens":956,"completion_tokens":483,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":398}},"tokens_in":572,"tokens_out":483,"duration_ms":5591,"temperature":1.0,"reasoning_tokens":398,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:04:26.125730+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a deterministic POMDP with four states arranged in a cycle where two adjacent states emit the same observation and actions are 'go clockwise' / 'go counterclockwise'; BIOMAP's action vectors will assign the same coordinate to states reached by different histories, so the Compact Vector Graph will not be isomorphic to the true state space, and the returned policy will be suboptimal. If BIOMAP still solves it optimally, the hidden uniqueness condition is not necessary.","supporting_citations":[{"cited_title":"Path integration in desert ants, cataglyphis fortis.Proceedings of the National Academy of Sciences , 85(14):5287–5290, 1988","cited_arxiv_id":null,"evidence_quote":"Supplies the biological path-integration mechanism that inspires the action-vector tracking approach."},{"cited_title":"Learning policies for partially observable environments: Scaling up","cited_arxiv_id":null,"evidence_quote":"Supplies the QMDP baseline that BIOMAP is compared against in the experiments."}],"review_version":1}