Constraint Tree Exploration for Learning from Language Feedback

Natural language feedback in interactive learning often explains *why* an action failed by pointing to violated requirements. We study this constraint-level regime by modeling user intent as latent constraints over an action space and formulating learning from language feedback as pure exploration over feasible regions. We introduce TRACE (Test-and-Refine Algorithm for Constraint Exploration), a test-before-commit algorithm that organizes candidate constraints in a tree, treats extracted identities as proposals rather than facts, and uses multi-round falsification tests before committing to a refinement. We distinguish two oracle-access regimes induced by the same feedback: (i) *falsification*, which only refutes the constraint set currently being tested, and (ii) *identification*, which may additionally name a violated atomic constraint. Under refutation and separation assumptions, we prove high-probability coverage upper bounds with candidate-class dependence $H$ for TRACE-Falsification. With sound extraction and a discovery-progress condition, TRACE-Identification replaces this dependence by $K/p_{\mathrm{ext}}$, where $K$ is the number of latent constraints and $p_{\mathrm{ext}}$ lower-bounds the probability of extracting a missing true constraint from informative feedback. Experiments across six language-feedback tasks demonstrate the benefits of identification-aware constraint exploration. On RecMovie, TRACE-Identification achieves 73% and 86% final-output success under caps of 20 and 60 evaluated outputs, compared with at most 42% and 48% for the evaluated prompting baselines. Controlled identity-corruption experiments further show greater robustness than direct accumulation when the falsification detector remains reliable.