ATPO: ADAPTIVE TREE POLICY OPTIMIZATION FOR MULTI-TURN MEDICAL DIALOGUE
Authors: Ruike Cao
Shaojie Bai
Fugen Yao
Liang Dong
Jian Xu
Li Xiao
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning (RL)
Large Language Models (LLMs)
Medical Dialogue
Tree Search
Primary area: reinforcement learning

Abstract: Effective information seeking in multi-turn medical dialogues is critical for accurate diagnosis, especially when dealing with incomplete information. Aligning Large Language Models (LLMs) for these interactive scenarios is challenging due to the uncertainty inherent in user-agent interactions, which we formulate as a Hierarchical Markov Decision Process (H-MDP). While conventional Reinforcement Learning (RL) methods like Group Relative Policy Optimization (GRPO) struggle with long-horizon credit assignment and Proximal Policy Optimization (PPO) suffers from unstable value estimation in this context, we propose a novel uncertainty-aware Adaptive Tree Policy Optimization (ATPO) algorithm. Our method adaptively allocates the rollout budget to states with high uncertainty, quantified by a composite metric of Bellman error and action-value variance. This strategy enables more accurate value estimation, while fostering more efficient and diverse exploration. To mitigate the high computational cost of tree-based RL, we introduce two key optimizations: an uncertainty-guided pruning mechanism to minimize the number of rollouts, and an asynchronous search architecture that leverages KV cache reuse to maximize inference throughput. Extensive experiments on three public medical dialogue benchmarks demonstrate that our algorithm significantly outperforms several strong baselines, culminating in Qwen3-8B model surpassing the much larger GPT-4o (+0.92% accuracy).

Published as a conference paper at ICLR 2026
ATPO: ADAPTIVE TREE POLICY OPTIMIZATION FOR MULTI-TURA MEDICAL DIALOGUE
Ruike Ca Shaojie Bai Fugen Yao Liang Dong²
Jian Xu²
Li Xiao
University of Science and Technology of China
?wwe Applications Business Group, Alibaba Group *Zhejiang University
ABSTRACT
Effective information seeking in multi-turn medical dialogues is critical for ac- curate diagnosis, especially when dealing with incomplete information. Aligning Large Language Models (LLMs) for these interactive scenarios is challenging due to the uncertainty inherent in user-agent interactions, which we formulate as a Hierarchical Markov Decision Process (H-MDP). While conventional Reinforce- ment Learning (RL) methods like Group Relative Policy Optimization (GRPO) struggle with long-horizon credit assignment and Proximal Policy Optimization (PPO) suffers from unstable value estimation in this context, we propose a novel uncertainty-aware Adaptive Tree Policy Optimization (ATPO) algorithm. Our method adaptively allocates the rollout budget to states with high uncertainty. quantified by composite metric of Bellman error and action-value variance. This strategy enables more accurate value estimation. while fostering more efficient and diverse exploration. To mitigate the high computational cost of tree-based RI., we introduce two key optimizations: nism to minimize the number rollouts, and an asynchronous search architec- ture that leverages KV cache reuse maximize inference throughput. Exten- sive experiments on three public medical dialogue benchmarks demonstrate that our algorithm significantly outperforms several strong baselines, culminating in Qwen3-8B model surpassing the much larger GPT-4o (+0.92% accuracy).
uncertainty-guided pruning mecha-
INTRODUCTION
In recent years, Large Language Models (LLMs) such as GPT-4 Achiam et al. (2023), Gemini 2.5 Comanici et al. (2025), Qwen3 Yang et al. (2025), and DeepSeek-RI Guo et al. (2025a) have demonstrated exceptional capabilities across a range of natural language processing tasks, including open-domain question answering. dialogue generation, and code generation, continuously pushing the boundaries of AI performance (Chen et al., 2025). These models are increasingly being applied to downstream domains like education (Chu al., 2025), law (Siino et al., 2025), and healthcare (Awasthi et al., 2025). Within the medical field, medical LLMS are consistently achieving state-of- the-art results on various benchmarks (Sellergren et al., 2025; Li et al., 2025a), such as professional medical examinations (Jiang et al., 2025) and disease diagnosis tasks (Xu et al., 2025; McDuff et al., 2025), and show immense potential for providing preliminary medical advice and assisting in clinical decision-main maaiin (Kopka al., 2025).
However, despite these achievements, a critical aspect has long been overlooked. Current training and evaluation of medical I.LMs predominantly focus on single-turn interaction scenarios, where models are expected to provide faithful responses based on the user's initial input. In real-world medical dialogues, however, the information provided by users is often incomplete, making it diffi- cult to generate a satisfactory response based solely on the vague or fragmented initial query (Auer- bach al., 2024; Wu et al., 2025a). This necessitates the model's ability to proactively ask clarifying
'Equal contribution. 1 'Corresonning author: fugen..ff www.yyf@@@iaaaaiin.ccomm CCode: https: / / thub. ccm www//uureeeeeeee -ued//uuarrreeeeeee ca ATTO.

---

Published as a conference paper at ICLR 2026
questions to gather more essential information. Unfortunately, this capability for dynamic, multi- turn information gathering is a significant deficiency in current models (Laban et al., 2025).
Previous work has attempted to fill this gap. Some approaches Li et al. (2024); Liu et al. (2025a); Hu et al. (2024) have used prompt engineering to clicit proactive questioning, but these methods often fail to fundamentally enhance the model's multi-turn interactive capabilities and can even lead to poorer performance than simply responding with incomplete information. Other efforts Liao et al. (2023); Liu al. (2025b) have employed supervised fine-tuning (SFT) improve dynamic inter- action, yet these models tend to merely imitate the training data. Furthermore, some studies Shi al. (2024); Xiong et al. (2024) have extended single-turn preference optimization the trajectory level, but they rely on costly preference data and are highly sensitive to distribution shift. While reinforcement learning offers a promising, goal-driven alternative with stronger generalization (Guo et al., 2025a), current methods are also flawed. For instance, Group Relative Policy Optimization Shao et al. (2024) struggles with long-horizon credit assignment, and Proximal Policy Optimiza- tion Schulman et al. (2017) often suffers from unstable value estimation, hindering effective policy learning for complex multi-turn dialogues (Feng et al., 2025a).
In this work, we introduce Adaptive Tree Policy Optimization, novel uncertainty algorithm illustrated in Figure 1. ATPO employs an adaptive tree search where, for each node, it calculates an uncertainty metric to decide whether to expand the search further. This metric is composite of two key signals: the Bellman error, which prioritizes nodes beneficial for critic training, and the action- value variance, which encourages sampling diversity. Furthermore, ATPO achieves high training efficiency by reusing shared prefixes to fully leverage the Key-Value (KV) cache Kwon et al. (2023) mechanism, combined with an asynchronous execution strategy. We conduct comprehensive evalua- tions on three Qwen3 models Yang et al. (2025) with different sizes (Qwen3 1.7B, 4B and 8B) using three multi-turn medical dialogue datasets meticulously adapted from public multiple-choice ques- tion datasets (MedQA Jin et al. (2020), MedMCQA Pal et al. (2022), and MedicalExam Liao et al. (2024)). The experimental results demonstrate that our proposed method significantly outperforms strong competitive RI. baselines across all datasets and model sizes, validating its effectiveness and generalization capabilities.
Our contributions are as follows:
We propose the Adaptive Tree Policy Optimization algorithm, which adaptively allocates rollout budgets based on tum-level uncertainty in multi-turn medical dialogues. This method enhances sampling diversity while simultaneously improving the critic model's accuracy,
We design ATPO to be highly efficient by reusing shared prefixes to fully leverage the KV cache, and we implement with an asynchronous execution strategy to achieve substantial improvements in inference throughput.
Extensive experiments demonstrate that ATPO not only consistently and significantly out- performs strong RL baselines, but also achieves this with far greater sample efficiency, validating its robust generalization and effectiveness.
RELATED WORK
2.1 REINFORCEMENT LEARNING IN MULTI-TURN MEDICAL DIALOGUES
Recent efforts have applied reinforcement learning to train medical LLMs for proactive, multi-turn dialogue. A common approach involves simulating doctor-patient interactions within a multi-agent framework. For instance, DoctorAgent-RL Feng et al. (2025b) uses such a setup where a "doctor agent" and "patient agent" (termed the "assistant" and "user", respectively, our work) interact, with the former learning optimal questioning strategy guided by comprehensive evaluator. To better guide this learning process, ProMed Ding et al. (2025) introduces a process reward based on Shapley Information Gain, which uses cooperative game theory to formally quantify the clinical util- ity of each question, enabling more targeted policy optimization. In contrast, Savage Conversation Forests (SCF) Savage (2025) concentrates on the training architecture, which employs branched conversation structure to help the model leamn how early conversational choices impact downstream outcomes by exploring multiple dialogue paths simultaneously. Despite these excellent works,
2

---

Published as a conference paper at ICLR 2026
PPO
TreePO
Tnitial
Transitioned State
X: Pruning
Terminal Leaf Node
Assistant Response Action
GRPO
State Transition
Response
Yo
((ooyYa
X1
ATPO
Uncertainty-Aware Tree Expansion
(lartt) rfe (slen)
Mix, Al) r(au.1)) +H 0dms) - Malle)
((())) - ulll (1 2342(ss)
Critic +p
Thresholding
Overview of ATPO algorithm. ATPO generates training data via an adaptive tree search. At each expansion step, it generates candidate child nodes and computes a composite uncertainty score based on their Bellman error U1 and Q-value variance U2. Nodes with high uncertainty U are fully expanded, while low-uncertainty nodes are pruned by randomly selecting single child for the subsequent rollout. The collected trajectories are then used for policy and critic updates.
Figure 1:
robust reinforcement learning algorithm capable of training model handle the complexities of real-world medical dialogues remains to be fully explored.
2.2 TREE-BASS BASED REINFORCEMENT LEARNING
To enhance the reasoning capabilities of LLMs, recent reinforcement learning approaches have be- gun to integrate tree-based search, particularly for single-turn tasks. These methods primarily focus on three distinct goals. First, some aim improve value estimation; for example, VinePPO Kazem- nejad et al. (2024) uses auxiliary "vine" rollouts to compute more accurate Monte Carlo values, mitigating the impact of inaccurate value estimation. Second, another line of work leverages model uncertainty to guide exploration, typically by expanding the search tree at tokens with high en- tropy (Hou et al., 2025; Dong et al., 2025). Third, others refine the search structure itself for better credit assignment efficiency, such SPO Guo et al. (2025b), which defines "segments" based on low- cow-probability tokens, or TreePO Li et al. (2025b), which uses a fixed N-ary tree for compu- tational gains. Despite their innovations, these methods are fundamentally limited by their single- turn, token-level focus. Their operational units (tokens, segments) do not naturally translate to the macro-level decisions required in multi-turn dialogue. Moreover, their uncertainty metries are ei- ther indirect proxies (e.g.. token entropy) or absent entirely in methods with fixed structures. Our approach directly addresses these limitations. We introduce an uncertainty measure based on the variance of turn-level Q-values, which quantifies the uncertainty over future rewards for different macro-actions (i.e., conversational turns). This makes our method inherently better suited for the long-horizon planning challenges of multi-turn interactions.
3 METHODS
3.1 MULTI-TURN DIALOGUES AS A HIERARCHICAL MDP
Similar to ArCHer Zhou al. (2024), we model multi-turn dialogues as a Hierarchical Markov Decision Process (H-MDP), which comprises high-level MDP with a nested low-level MDP. For the high-level MDP, a macro-action defined as the full token sequence of the assistant's response in single turn. A micro-action in the low-level MDP is single token, such that generating sequence of micro-actions actions in the low-level MDP leads to a single macro-action in the high-level MDP. Formally, each state zg in the high-level MDP consists of the interaction history between the
3

---

Published as a conference paper at ICLR 2026
user and the assistant prior the k-th turn, together with the user's query d at the k-th turn. The macro-action yk is defined as a variable-length token sequence representing the assistant's 's response to 9k- The low-level MDP models the process of generating macro-action, where each low-level action yk.t corresponds to an individual token (i.e., the 1-th token in the k-th macro-action). low- level state Ty; f is defined the concatenation of the high-level state zy and the partial sequence <t, namely the tokens that have already been generated in the current turn up to (but excluding) the 1-th token.
3.2 DIALOGUE EXPLORATION VIA TREE EXPANSION
In H-MDP optimization, accurate state-value estimation is crucial for effective policy improvement. Existing methods either rely on pure Monte Carlo estimates from full trajectories (e.g., GRPO Shao et al. (2024)), which can be high-variance and lead to unstable training, or solely on a learned critic (e.g.. PPO Schulman et al. (2017)), which may suffer from approximation errors. To strike a balance between accuracy and efficiency, propose an exploration strategy based on incremental tree expansion. This approach efficiently reuses the computation of shared dialogue prefixes (a detailed analysis of the computational savings is provided in Appendix A.7) and adaptively allocates the sampling budget to the most promising or uncertain parts of the dialogue space, rather than repeatedly re-exploring from the root.
In this framework, the multi-turn dialogue process is viewed as the expansion of a search tree. The initial user query forms the root node, which is depth 0 and corresponds to state To- From there, the tree expands turn-by-turn. At any non-terminal node corresponding to state IA the assistant produces macro-action, which can be either clarifying question or definitive answer. In the case of a clarifying question, the user's reply completes the state transition to Th+11 resulting in the creation of new node at the next depth of the tree. In the case of definitive answer, the dialogue terminates along that branch and the node becomes terminal leaf; for consistency, the subsequent user feedback in this scenario considered empty. Thus, the depth of node corresponds to the number of turns elapsed in the dialogue, with the root at depth O, and the nodes at depth k: representing all possible dialogue states after & turns of interaction.
This entire procedure is guided by an uncertainty-awee aware principle. The core idea is to prioritize the expansion of nodes exhibiting high uncertainty, as they provide more diverse and informative sam- ples for driving effective policy updates and improving critic accuracy. In the multi-turn dialogue setting, this uncertainty can be broadly categorized into two types: Epistemic uncertainty, aris- ing from the inherent cognitive limitations of the model and manifests uncertainty in its action. Aleatoric uncertainty, stemming from the inherent randomness in the environment, such as the variability in user responses.
3.3 UNCERTAINTY-AWAL TREE EXPANSION MECHANISM
To operationalize our tree expansion strategy, we first quantify the uncertainty of each frontier node. Consider a specific node depth k. representing the dialogue state zд. We sample a set of N candidate macro-actions {3j J from the policy Te(- For each candidate action vi. we define its estimated action-value (( vf) using one-step lookahead:
Q( vi) = r(zx: vit) + 7 (2
(I)
where r|.1 is the state resulting from action v and the next-state value Vo is given by the critic model. Based on this, the uncertainty is calculated as:
N
(x+)
(x((
QE vtt
2
(2(z Varie[M] [2(21, [k))
Σ
1 N
Σ
Óz vt)
(3)
U(x)) a Un (xx) + (1 a) U2(2))
(4)
The first term, U, (mx). measures the Bellman error between the critic's current value estimate (xx and the empirical one-step lookahead value averaged over all candidates. It serves
4

---

Published as a conference paper at ICLR 2026
proxy for aleatoric uncertainty; large error indicates inaccurate value estimate for the current state. Note that this error metric is used solely as heuristic to guide the tree expansion process, rather than target for bootstrapping updates of the critic model. The second term, (2(22), quantifies the variance of the action-value estimates. This term captures a blend of both epistemic and aleatoric uncertainty. High variance can arise from two distinct sources: the policy's ' own indecision leading it to explore diverse set of candidate actions (epistemic), or the environment's ' inherent randomness where different state transitions yield widely varying Q-values (aleatoric). The notation Var(-) represents the variance across the N candidate actions. This raw value is subse- quently normalized using Z-score scaling based on historical samples create a stable, comparable metric. The hyperparameter
[0, 1] balances the contributions of these two uncertainty sources.
With the uncertainty metric (ara) defined, the expansion process guided by a threshold-based rule. When the expansion process reaches a node at depth k, representing one of the possible dia- logue states after & turns, we compare its calculated uncertainty against a predefined threshold т: U(IR) > the node is considered highly uncertain and all N branches are retained. Conversely, if (xx)) S T, the node is deemed sufficiently understood. To conserve computational resources, we primarily prune the search by randomly selecting only one of the N candidate branches. However, to maintain a baseline level sampling diversity, we bypass this pruning with a small probability (e.g., 10%) and instead expand all N branches.
The uncertainty driven expansion continues along the retained branches until all dialogues terminate or the total number of leaf nodes (i.e., the tree width) reaches predefined budget. Once this budget is met, no further nodes are expanded, and all current leaf nodes proceed to the rollout phase until termination.
3.4 VALUE TRACEBACK, TREE DECOMPOSITION AND MODEL. OPTIMIZATION
Following the completion of the tree expansion process, we compute the values and advantages for all nodes within the generated tree via a recursive backward pass starting from the leaf nodes. First, we calculate the target value ((z2) for each state Ih. which serves as robust empirical estimate of the Monte Carlo return from that state and can be used as the value target for subsequent critic updates:
rlaks Vk), B(ox)
if leaf node,
(Tx)
(5)
(((2))0)) vi) + + (xt+
otherwise.
B(Ik)
If state is terminal, its target value equals the immediate reward; otherwise, it is the average one- step TD target over all child branches. Here, B(xx) denotes the number of child nodes, which according to the expansion rule is either N for fully expanded nodes or 1 for pruned nodes, and the superscript i indexes the i-th branch among these children.
With the target values established, we compute the estimated advantage for each macro-action y using the standard one-step cemporal-differeme formulation:
A(TR, v = r(x,, vid + 7 (olok-n) (o
(6)
The reason we use the critic's value estimates instead of the target values V(()) is that, when only one branch retained, (<xx equals its one-step return, resulting in a zero advantage; whereas the critic's estimates preserve non-zero learning signals.
Once values and advantages have been computed for all nodes, the expanded tree is decomposed into a set of independent trajectories for model optimization. Each unique path from the root leaf node constitutes one trajectory, so a tree with M leaf nodes directly yields M such trajectories. The number of turns in the j-th trajectory, denoted by K(), can vary across trajectories because different dialogues may terminate after different numbers of turns. The policy no is then updated by
5

---

Published as a conference paper at ICLR 2026
maximizing the following PPO-style objective, aggregated over all tokens from all trajectories:
M
KG Σ
((] = E T ==:
M
KU)
==1
A=1
L(v
min
Pk.t A u bkit).
clip(pk.) (0) c, 1 A) (ii)) - 8 3DKL (Tol (Tol(Tzet)
(5)
T
ykit
Ik Mk,ct)
and A vl) A(r,, v for SSS T(uk
where Ph.t
(5) T 2k,
Trel
In this objective, the expectation EE.) is taken over initial user queries zo sampled from the dataset D, along with subsequent states and actions. The term Pk. denotes the probability ratio between the current policy To and the reference policy 7ref for generating the t-th token in the k-th turn of the j-th trajectory. Consistent with our hicrarchical MDP formulation, the advantage A(zx, vk,t) for each token is set equal to the macro-action' 's advantage A(ER, ()),, thereby uniformly distributing the turn-level credit across the tokens generated in that turn. The update is normalized by two factors: C(zkk). (2)), ), the visit count of the state across all trajectories, which prevents over-optimizing on frequently visited nodes; and L(vls) (3) ), the length of the response, which ensures the turn-level advantage properly scaled for each token. The min(.) and clip(.) constrain the policy update to stabilize training.
Finally, the critic model, parameterized by v. is trained to predict the target state values. The critic consists of the LLM backbone and a linear value head. Its value estimate Vy (xx)) is obtained as the average of the predictions over the final h special tokens. The critic is trained by minimizing the following mean squared error loss:
K
L(m
((+)) M
Σ
- 2
1
(8)
K
t=
())
-+++1
where (x the value predicted at the t-th token position of the input, with I(x denoting the total number of tokens of state o This loss trains the critic to make the predictions at the final h token positions for state ..(() match the ground-truth target value V(x)).
EXPERIMENTS
4.1 EXPERIMENT SETUP
Environment and Task Description. We establish a multi-turn clinical case reasoning environment with two LLM-based agents: User Simulator and an Assistant Agent. (1) User Simulator: Im- plemented using Qwen3-8B, it is instructed to answer the Assistant's questions strictly based on given set of atomic facts (an example is provided in Appendix A.9), refusing respond any out- oc-sc queries. The prompt for user simulator is provided Appendix A.8. To ensure reliability, we continuously monitor its behavior during training and verify with GPT-4o, achieving 100% accuracy in following instructions and rejecting irrelevant queries, with a hallucination rate of only 1.2%, demonstrating high fidelity. This verification was performed using the user simulator quality monitoring prompt (see Appendix A.8). (2) Assistant Agent: The Assistant Agent is tasked with resolving a clinical case question by selecting the correct answer from a list of options. It begins with initial context and can iteratively query the User Simulator for additional information. The process terminates when the agent either commits to a final answer or the pre-defined turn limit is reached. An interaction example between the Assistant Agent and the User Simulator is provided in Appendix A.I.
Baselines. We compare our ATPO with several baselines to evaluate its effectiveness:

---

Published as a conference paper at ICLR 2026
1) Zero-shot Prompting: To benchmark performance, evaluate several base models (Qwen3- 1.7B, Qwen3-4B, and Qwen3-8B) under two distinct settings. The first is Direct single-turn setting, where the agent must respond using only the initial context. The second is an interactive MEDIQ Li et al. (2024) setting, which allows the agent to interact with the User Simulator for up to 8 turns in total, including the final answering turn. Prompts for both settings are provided in Appendix A.8.
2) SFT: To establish a stronger baseline, we fine-tune the Qwen3 instruct models to encourage multi-turn infornation-seekinng behavior instead of directly producing an answer in the first turn. Using the MEDIQ validation dataset as the source of atomic facts, questions, and answer options, we employ the expert model Gemini-2.5- assistant to generate 269 multi-turn dialogues (the prompt is provided in code repository as it is too long to display in the paper). We ensure no information leakage during this process and retain only dialogues with a correct final answer. The resulting dataset is used to train the models with supervised fine-tuning and dynamic fine-tuning (DFT Wu et al. (2025b)).
self-play setup, where role-plays both user and
3) SFT+RL: We compare our algorithm with standard RL post-training methods under the same environment, using rewards solely based on the correctness of the final answer. Critic-based Meth- ods: PPO (MDP) treats text generation as a standard MDP, assigning unique value to each token. PPO (H- HDDM)) adopts a hierarchical formulation, estimating a single value per turn and propagating the corresponding advantage to all tokens in that turn. Critic-free Methods: We implement GRPO, which assigns a single advantage to an entire trajectory and shares it across all tokens. We also adopt TreePO (Guo et al., 2025b; Li et al., 2025b), where construct binary search tree in which each non-terminal node expands into two child nodes, constrained only by maximum depth cor- responding to the dialogue turn limit, without any pruning. After the search completes, we perform a backward pass to compute the aggregate return for each node as its target value V (zx). The ad- vantage is calculated as Á(Tx, 3k) = r(akk 3/s) + +~V (xR+11 - (zx), and is assigned to all tokens generated in that sequence for policy optimization.
Implementation Details. For RL experiments, we use the SFT-trained Qwen3-1.77, Qwen3-4B, and Qwen3-8B models as the initial policy for the Assistant Agent. The reward function is based solely on final-answer correctness: +3 for a correct answer, 0 for an incorrect answer, and -1 for an invalid format. The training data contains 14, 256 samples, with 66% (9, 400) drawn from the MEDIQ training dataset and 34% (4, 856) constructed from the MedMCQA training dataset.
0.01, and discount factor = 1. The critic is initialized from the actor's weights and warmed up for 5 steps. Method-specific settings include group size of 32 for GRPO, and for ATPO, an expansion size N = 4 with total expansion budget of 128. In ATPO (U1), the uncertainty threshold is T = 0.5; in ATPO (U1 + U2), we set a 0.3 and T 1.5.
Policy learning rate 1 10-6, critic learning rate 10-5, KL penalty weight
Our TreePO and ATPO implementations build upon the VeRL (Sheng et al., 2025) Agentic RL framework, integrating tree search, reward computation, and advantage estimation into a single concurrent phase. This design eliminates the need for a multi-stage pipeline by producing ready- to-train trajectories directly from the search process. In ATPO, throughput is further improved by executing the assistant model's 'sss answer generation, its interaction handling with the user model, and the value estimation by the critic model a fully asynchronous manner within the sampling phase. Together with efficient prefix sharing and the vLLM KV cache, this design achieves decoding speeds of up to 2,500 tokens/sec/GPU on a 1.7B model with TreePO. Both our implementation and the associated datasets are available at https: / / giighb.......... com/ Quarruuarrkkaakkk -eed cal 1/ATPO..
4.2 RESULTS
Evaluation Setup. We conduct evaluations on three Qwen3 models Yang et al. (2025) of different sizes (Qwen3-1.7B, Qwen3-4B, and Qwen3-8B), along with GPT-4o and Gemini-2.5-PPr as a strong baseline to assess the effectiveness of our method. Experiments are performed on three multi-turn medical dialogue datasets adapted from public multiple-choice question datasets: MedQA, obtained directly from the MEDIQ Li et al. (2024) test set; MedMCQA, constructed from its original training data Pal et al. (2022); and MedicalExam, sourced directly from AIE Liao et al. (2024). Each sample is reformulated into set of atomic facts, a concise initial context, an atomic question that excludes factual details, and several answer options with exactly one correct choice (details in Appendix A.2). The primary evaluation metric is final- accuracy, defined as the percentage of test cases where
7

---

Published as a conference paper at ICLR 2026
Table Performance comparison (%) on MedicalExam, MedQA, and MedMCQA. Bold indicates the best performance, underlined the second-best (excluding GPT-4o and Gemini-2.5-Pro,
Model
Method Type
Method Name
MedicalExam
MedQA
MedMCQA
Direct MEDIQ
35.07 1.12
34.05 + 0.38
32.54 0.49
Prompt
34.00 + 2.26
34.20 + 0.75
32.35 + 1.73
SFT
DFT
29.07 + 1.46
28.38 + 0.80
21.08 + 0.90
Qwen3-1.7B
SIT
32.27 4.77
33.42 1 0.95
28.10 1 2.32
PPO (MDP)
39.33 1 4.01
38.64 1.17
35.37 1 0.80
PPO (H-MDP)
39.33 + 2.79
39.08 + 1.85
34.89 + 1.00
SFT+RL
GRPO
42.93 + 1.80
41.17 0.64
36.57 + 3.26
TreePO
43.33
1.56
42.05 + 1.03
38.47 2.00
ATPO (U1)
45.73
1.53
42.54 0.339
38.66 0.66
ATPO (Ui U2)
43.20 + 1.85
42.87 = 0.77
39.93 + 1.05
Direct
48.13 + 0.87
44.94 + 0.35
41.53 +: 0.39
Prompt
MEDIQ
45.87 1.20
40.11 1 0.60
31.64
SFT
DFT
41.72 1 1.27
33.28
Qwen3-4B
SFT
48.93 + 2.14
1.01 47.15
39.18 + 1.22
PPO (MDP)
50.13 + 2.80
50.60 + 0.90
42.50 + 0.84
PPO (H-MDP)
52.40 2.24
48.58 1.48
43.32
2.22
SFT+RI.
GRPO
53.87 2.08
51.17 1 1.08
43.84
0.78
TreePO
56.13 + 0.99
53.74 + 0.56
45.22 + 0.65
ATPO (Ui)
56.80 + 1.28
53.15 = 0.55
46.23 + 1.25
ATPO (U1 U2)
59.73 2.61
55.47 0.99
45.93
Prompt
Direct
52.40 + 0.37
45.22 + 0.34
46.16 + 1.04
MEDIQ
51.87 3.69
46.03 + 0.75
41.60
0.91
SFT
DFT
51.86 3.63
48.80 1 1.30
42.20 0.83
Qwen3-8B
SFT
55.87 + 0.30
53.75 + 1.18
1.74 46.87
PPO (MDP)
59.20 + 3.84
$7.38 + 0.84
50.00
0.81
PPO (H-MDP)
59.07 3.15
67.81 1.29
51.98 + 0.67
SFT+RL
GRPO
60.93 - 1.86
57 0.68
51.12
1.29
TreePO
66.33 + 3.09
61.81 0.90
54.74 + 1.99
ATPO (U5)
65.52 1 3.12
62.57 1 0.41
53.22
1.30
ATPO (Ui U2)
65.87 = 3.72
64.07 = 0.43
53.66 + 1.52
GPT-4o Gemini-2.5-Pro
Prompt Prompt
MEDIQ
64.00 3.53
63.15 + 0.82 0.82
53.03
MEDIQ
74.33 + 2.53
68.69 1 0.61
63.31 + 1.37
the Assistant Agent's chosen option matches the ground-truth answer. For statistical robustness, we report the mean and standard deviation of five independent runs.
Main Findings. From Table 1, we observe that in the zero-shot setting, the MEDIQ prompting strat- egy performs worse than the Direct single-turn prompt, consistent with the finding MEDIQ Li et al. (2024) that prompting LLMs to ask questions can reduce accuracy. Supervised fine-tuning brings only modest gains in final-answer accuracy while being crucial for enabling multi-turn in- formation seeking and providing solid foundation for subsequent reinforcement learning. We further explored the limits of SFT by distilling knowledge from much larger models like GPT-4o and Gemini-2.5-Pie As detailed in Appendix A.3, this distillation approach also failed yield sig- nificant improvements (Table 2), reinforcing the notion that simply imitating expert trajectories is insufficient for generalization and that a goal-driven reinforcement learning approach is necessary.
Our proposed ATPO achieves the highest accuracy in most settings, even surpassing GPT-4o at the 8B scale (e.g., exceeding GPT-4o on MedQA by 0.92%). This demonstrates the strong effectiveness of the method. Further, the results show that both uncertainty metrics are valuable and complemen- tary: ATPO (U, U2) generally outperforms ATPO (U1), which turn achieves higher accuracy than TreePO. Combining Un and U2 yields the best results, with absolute gains over TreePO on MedQA of 0.82%, 1.73%, and 2.26% for the 1.7B, 4B, and 8B models, respectively. This per- formance improvement is partly driven by the enhanced quality of the dialogues. As shown in Appendix A.4, the proportion of effective questions asked by the assistant steadily increases during ATPO training (Figure 4), allowing it to gather erucial information more efficiently and solve tasks in fewer turns.
ATPO also exhibits markedly higher sample efficiency, shown in Figure 2 (a). For instance, on MedQA with Qwen3-4B, ATPO (U, + U2) achieves approximately 52.7% accuracy while using only 55% of the training turns required by TreePO (A detailed analysis of the computational costs of
8

---

Published as a conference paper at ICLR 2026
(M))
ATPO (M, Ugl
PMD
TrewnD
N-
IU, E.)
ATHO (9, Mg) EX%
0.30
10
811
0.34
Coltee Lass
0.50
Rotum
12
0.48
0.46
10f
Trinnin Turms
107
29
(0)
Nurther of of Natee
Pelay Gradieat Cip Fraates
Pelp Eatrays
Mous
Depeh
Training
(2)
Figure 2: Analysis of the ATPO algorithm on Qwen3-4B. (a) Training efficiency and performance comparison of various algorithms, plotting accuracy against the number of generated turns. (b), (c) Return variance and critic loss for ATPO and baseline methods. (d), (c) Distribution of branching nodes and returns by depth for samples from ATPO at representative training step. (f), (g) Stability analysis of ATPO with and without visit-count hatt-cout--based down-weighting.
various algorithms is provided in A.5). This advantage stems from ATPO's adaptive rollout budget allocation mechanism. Moreover, unlike TreePO's fixed branching, which causes an exponential growth of nodes concentrated in early turns, ATPO's uncertainty- bbased pruning enables deeper and more balanced exploration across all dialogue depths (as shown in Figures (d), (e)), making more suitable for long-horizon horizon tasks. Additionally, hierarchical modeling proves beneficial in multi- turn dialogue: PPO (H-MDP) slightly but consistently surpasses PPO (MDP), scoring higher of evaluation settings. Among critic-free methods, the tree-based approach demonstrates clear superiority, with TreePO substantially outperforming GRPO, This indicates that, for complex multi- turn tasks, structuring credit assignment via a search tree is more effective than relying on a single trajectory-level advantage.
4.3 ABLATION AND ANALYSIS
We conducted several ablation experiments on ATPO, which provide the following key insights.
The dual uncertainty metries enhance both sampling diversity and critic optimization. Figure 2 (b) shows that guiding node expansion with U1 + U2 produces a high variance of sample returns, com- parable to GRPO and markedly higher than TreePO, while using only Un reduces diversity. At the same time, Figure 2 (c) indicates that the critic's value loss under U1 + U/ is substantially lower than PPO (both MDP and H-MDP), with U₁ alone ranking second. These results highlight that uncertainty-an
tree search benefits value function learning. This advantage partly stems from intelligent budget allocation (Figures 2 (d), (e)): U1 alone drives aggressive early exploration, con- centrating expansions at shallow depths (3-4) and causing steep local drops in node values, whereas U1 + U2 achieves deeper coverage and maintains more uniform value variance, enabling a more globally effective search.
We also find that weig-teighting policy updates by node visit count crucial for training stability. An ablation study compares the default ATPO (policy advantage down-weighted) with two variants: EXP,, (no policy down- weightin)) and EXP,, flown-weightin both policy advantage and value loss). EXP, results in uncontrolled entropy growth and excessive policy clipping (Figures (f), (g)). since ignoring visit counts leads to disproportionate policy updates on frequently visited nodes, causing the policy to diverge rapidly from its reference state. In contrast, F.X P, induces rapid en-

---

Published as a conference paper at ICLR 2026
tropy collapse. fligh-iisit nodes provide the most reliable value estimates due abundant samples, and underweighting the value loss on these nodes destabilizes the critic, increasing value variance in early layers over time. As result, the policy learns to distrust its flawed value function, abandons multi-turn exploration, and regresses to suboptimal single-turn strategies.
Moreover, assess the generalization of our method, evaluated the assistant model trained with ATPO using an unseen user simulator. Specifically, for evaluation, we replaced the Qwen3-8B simulator used during training with the Jlama-3.3-70B-Instuu model. As detailed in Appendix A.6, the assistant maintains similar performance across all test sets (Table A.6), providing strong evidence that our method does overfit to the conversational patterns specific simulator and possesses robust generalization capability.
5 CONCLUSIONS AND FUTURE WORK
In this paper, we present ATPO, a novel adaptive tree search method that intelligently guides explo- ration in multi-turn dialogues through state-uncertainty evaluation. By selectively expanding nodes that maximize sampling diversity and benefit critic optimization, ATPO achieves superior perfor- mance with markedly fewer exploration steps, surpassing strong RL baselines such as TreePO and GRPO across several clinical dialogue benchmarks, and even outperforming GPT-4o on MedQA with the Qwen3-8B model. Beyond its success multi-turn medical dialogue, ATPO can also be applied to wide range of scenarios, including multi-ture open open-ended dialogue and tool use.
Future work could pursue several promising directions. First, replacing the current thelslhr expansion mechanism with learnable, soft control policy may reduce hyperparameter tuning ef- fort and enable the expansion strategy to adapt dynamically as the policy evolves. This idea could be further extended adaptively determine the number of nodes expand based uncertainty metrics, rather than relying on random selection. Second, refining credit assignment within the Hi- erarchical MDP (H-MDP) framework could yield additional gains. A more sophisticated approach to distributing high-level advantages to low-level token actions, moving beyond uniform cloning, may allow for more precise policy optimization and improved performance.
ACKNOWLEDGMENTS
This work was supported by Qwen Applications Business Group of Alibaba Group through Alibaba Research Intern Program.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv: 08774, 2023.
Andrew D Auerbach, Tiffany M Lee, Colin C Hubbard, Sumant R Ranji, Katic Raffel, Gilmer Valdes, John Boscardin, Anuj K Dalal, Alyssa Harris, Ellen Flynn, al. Diagnostic errors in hospitalized adults who died or were transferred to intensive care. JAMA Internal Medicine, 184 (2):164-173,, 2024.
Raghav Awasthi, Sai Prasad Ramachandran, Shreya Mishra, Dwarikanath Mahapatra, Hajra Arshad, Aarit Atreja, Anirban Bhattacharyya, Atharva Bhattad, Nishant Singh, Jacek B Cywinski, et al. Artificial intelligence in healtheare: 2024 year in review. medRxiv, pp. 2025-02, 2025.
Qingyu Chen, Yan Hu, Xueqing Peng, Qiangian Xie, Qiao Jin. Aidan Gilson, Maxwell B Singer, Xuguang Ai. Po-Ting Lai, Zhizheng Wang. et al. Benchmarking large language models for biomedical natural language processing applications and recommendations. Nature communi- cations, 16(1):3280, 2025.
Zhendong Chu, Shen Wang, Jian Xie, Tinghui Zhu, Yibo Yan, Jinheng Ye, Aoxiao Zhong, Xuming Hu, Jing Liang, Philip Yu, et al. Llm agents for education: Advances and applications. arXiv preprint Xivi: 11733, 2025.
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality. long context, and next generation agentic capa- bilities. arxiv preprint arXiv:2507.06261 2025.
Hongxin Ding, Baixiang Huang, Yue Fang, Weibin Liao, Xinke Jiang, Zheng Li, Junfeng Zhao, and Yasha Wang. Promed: Shapley information gain guided reinforcement learning for proactive medical 1lms. arXiv preprint arXiv:2508. 13514, 2025.
Guanting Dong, Hangyu Mao, Kai Ma, Licheng Bao, Yifei Chen, Zhongyuan Wang, Zhongxia Chen, Jiazhen Du, Huiyang Wang. Fuzheng Zhang, al. Agentic reinforced policy optimization. arXiv preprint arXiv:2507.198/7 2025.
Xiao Feng, Bo Han, Zhanke Zhou, Jiaqi Fan, Jiangchao Yao, Ka Ho Li, Dahai Yu, and Michael Ng. DyPO: Dynamic policy optimization for multi-turn interactive reasoning. In ICML 2025 Workshop on Programmatic Representations for Agent Learning, 2025a. URL https: //opezeeview net fest/forume forum?
1eot://oormmm-----MiBBMKMM d-OWBBiMKddo.
Yichun Feng, Jiawei Wang. Lu Zhou, Zhen Lei, and Yixue Li. Doctoragent-rl: A multi-agent collaborative reinforcement learning system for multi-turn clinical dialogue. arXiv preprint arXiv:2505.196600 20255..
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma. Pciyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning, arXiv preprint arXiv:2501.122 2025a.
Yiran Guo, Lijie Xu, Jie Liu, Dan Ye, and Shuang Qiu. Segment policy optimization: Ef- fective segment-level credit assignment in for large language models. arXiv preprint arXiv:2505.23564, 2025b.
Zhenyu Hou, Ziniu Hu, Yujiang Li, Rui Lu, Jie Tang, and Yuxiao Dong. Treerl: Llm reinforcement learning with on-policy tree search. arXiv preprint arXiv:2506. 11902, 2025.
Zhiyuan Hu, Chumin Liu, Xidong Feng. Yilun Zhao, See- KeenKiong Ng, Anh Tuan Luu, Junxian He, Pang Wei W Koh, and Bryan Hooi. Uncertainty of thoughts: Uncertainty planning hances information seeking in 1lms. Advances in Neural Information Processing Systems, 37: 24181-24215. 2024.
11

---

Published as a conference paper at ICLR 2026
Xinke Jiang, Ruizhe Zhang, Yongxin Xu, Rihong Qiu, Yue Fang, Zhiyuan Wang, Jinyi Tang, Hongxin Ding, Xu Chu, Junfeng Zhao, et al. Hykge: A hypothesis knowledge graph enhanced rag framework for accurate and reliable medical Iims responses. In Proceedings of the 63nd An- nual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp- 11836 11856, 2025.
Di Jin, Eileen Pan, Nassim Oufattole, Wei-Hung Weng, Hanyi Fang, and Peter Szolovits. What dis- ease does this patient have? large-scale open domain question answering dataset from medical exams. arXiv preprint arXiv:2009. 13081, 2020.
Amirhossein Kazemnejad, Milad Aghajohari. Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. Vineppo: Refining credit assignment in training of llms. arXiv preprint arXiv:2410.0167, 2024.
Marvin Kopka, Niklas von Kalckreuth, and Markus A Feufel. Accuracy of online symptom assess- ment applications, large language models, and laypeople for self-triage decisions. npj Digital Medicine, 8(1):178, 2025.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng. Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Philippe Laban, Hiroaki Hayashi, Yingbo Zhou, and Jennifer Neville. Lims get lost in multi-turn conversation. arXiv preprint arXiv:2505.064 0660000 2025.
Ao Li, Bin Yan, Bingfeng Cai, Chenxi Li, Cunzhong Zhao, Fugen Yao, Gaogiang Liu, Guanjun Jiang, Jian Xu, Liang Dong, al. Quarkmed medical foundation model technical report. arXiv preprint arXiv:2508.1 11894, 2025a.
Stella Li, Vidhisha Balachandran, Shangbin Feng. Jonathan Ilgen, Emma Pierson, Pang Wei W Koh, and Yulia Tsvetkov. Mediq: Question- Iims and a benchmark for reliable interactive clinical reasoning. Advances Neural Information Processing Systems, 37:28858- -28888, 2024.
Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Tianshun Xing, Shuyue Guo, Tianyu Zheng, Xin Zhou, Xingwei Qu, Wangchunshu Zhou, et al. Treepo: Bridging the gap of policy optimiza- tion and efficacy and inference efficiency with heuristic tree-based modeling. arXiv preprint arXiv:2508. 17445, 2025b.
Yusheng Liao, Yutong Meng, Hongcheng Liu, Yanfeng Wang, and Yu Wang. An automatic evalua- tion framework for multi-tum medical consultations capabilities of large language models. arXiv preprint 20Xiv=2330.002077, 2023.
Yusheng Liao, Yutong Meng, Yuhao Wang, Hongcheng Liu, Yanfeng Wang, and Yu Wang. Auto- matic interactive evaluation for large language models with state aware patient simulator. arXiv preprint arXiv:2403.0m 4088:994 2024.
Ruoyu Liu, Kui Xue, Xiaofan Zhang, and Shaoting Zhang. Interactive evaluation for medical Ilms via task-oriented dialogue system. In Proceedings of the 31st International Conference on Com- putational Linguistics, pp. 4871-4890 1-966, 2025a.
Zijie Liu, Xinyu Zhao, Jie Peng. Zhuangdi Zhu, Qingyu Chen, Xia Hu, and Tianlong Chen. Dialogue is better than monologue: Instructing medical llms via strategical conversations. arXiv preprint arXiv:2501. 2002551117700 2025b.
Daniel McDuff, Mike Schaekermann, Tao Tu, Anil Palepu, Amy Wang, Jake Garrison, Karan Sing- hal, Yash Sharma, Shekoofeh Azizi, Kavita Kulkarni, et al. Towards accurate differential diagno- sis with large language models. Nature, pp. 1-7, 2025.
Ankit Pal, Logesh Kumar Umapathi, and Malaikannan Sankarasubbu. Medmeqa: A large-scale multi-subject multi multi-choice dataset for medical domain question answering. In Conference on health, inference, and learning, pp. 248-260. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2026
Thomas Savage. Conversation forests:
The key to fine tuning large language models for multi-turn medical conversations is branching. arXiv preprint TrXiv:2507.04099, 2025.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint (ett:::777..6444 2017.
Andrew Sellergren, Sahar Kazemzadeh, Tiam Jaroensri, Atilla Kiraly, Madeleine Traverse, Timo Kohlberger, Shawn Xu, Fayaz Jamil, Cían Hughes, Charles Lau, et al. Medgemma technical report. arXiv preprint 2tti:::55700020.... 2025.
Zhihong Shao, Peiyi Wang. Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi. Haowei Zhang, Mingchuan Zhang. YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathemati- cal reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient rlhf framework. In Proceedings of the Twentieth European Conference on Computer Systems, EuroSys '25, pp. 1279-1297, ACM, March 2025. doi: 10. 00.1145/388901133666777 3689031. 3696075.
URL http://dde dei org/ 10.0110.11 1145/
Wentao Shi, Mengqi Yuan, Junkang Wu, Qifan Wang, and Fuli Feng. Direct multi-turn preference optimization for language agents. arXiv preprint arXiv:2406. 148,:,,,,0,,88,, 2024.
Marco Siino, Mariana Falco, Daniele Croce, and Paolo Rosso. Exploring Ilms applications in law: A literature review current legal nlp approaches. IEEE Access, 2025.
Chaoyi Wu, Pengcheng Qiu, Jinxin Liu, Hongfei Gu. Na Li, Ya Zhang, Yanfeng Wang, and Weidi Xie. Towards evaluating and building versatile large language models for medicine. npj Digital Medicine, 8(1):58, 2025a.
Yongliang Wu, Yizhou Zhou, Zhou Ziheng, Yingzhe Peng. Xinyu Ye, Xinting Hu, Wenbo Zhu, Lu Qi, Ming-Hsuan Yang. and Xu Yang. On the generalization of sft: A reinforcement learn- ing perspective with reward rectification, 2025b. URL https: arxiv. org/ abs/2508. 05629.
Wei Xiong, Chengshuai Shi, Jiaming Shen, Aviv Rosenberg, Zhen Qin, Daniele Calandriello, Misha Khalman. Rishabh Joshi, Bilal Piot, Mohammad Saleh, et al. Building math agents with multi- turn iterative preference learning. arXiv preprint 2rX.v:2409.023392. 2024.
Yongxin Xu, Xinke Jiang, Xu Chu, Rihong Qiu, Yujie Feng, Hongxin Ding, Junfeng Zhao, Yasha Wang, and Bing Xie. Dearllm: Enhancing personalized healthcare via large language models- deduced feature correlations. Proceedings of the AAAI Conference on Artificial Intelligence, 39 (1):941-949, Apr. 2025. doi: 10.1609/anai, 10.1609/umii.v3911.2277 33911.32079 URL https://oft aaai org/ index.ppp/AAe /tlp/AAAAIO htt./aaiiica http://ttteeeeeeeeeeeeeteteetttt 32079.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao. Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025.
Yifei Zhou, Andrea Zanette, Jiayi Pan, Sergey Levine, and Aviral Kumar. Archer: Training language model agents via hierarchical multi-turn In International Conference on Machine Learning. pp.
PMLR, 2024.
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 INTERACTION PROCESS BETWEEN ASSISTANT AGENT AND USER SIMULATOR
Figure 3 presents an example of the interaction flow in our multi-turn clinical reasoning environment.
The process starts from an incomplete initial user query representing clinical case. The Assistant Agent receives this query along with a set of answer options. The initial information is intentionally limited; attempting answer directly at this stage often leads to incorrect results. Therefore, the Assistant Agent must actively ask targeted questions to the User Simulator in order to obtain the missing key facts. The User Simulator responds strictly within the scope of predefined atomic facts, refusing to provide any information beyond this scope. This iterative exchange continues until the Assistant Agent commits to final answer or the predefined turn limit is reached.
8-month-old boy brought office by his mother for recurrent infections.
Problem: What the most likely cause of this patient's condition?
Options: ('A': 'Adenosine deaminase deficiency'. 'B': "Hypoxamthine-gumnn phosphoribosyl transferasc (HGPRT) deficicney,, 'C": 'HIV infection', 'D'; Purine nuclcoside phosphoryyass lase deficiency')
<think
The patient is 8-month-old with recurrent infections, classic sign immanodefieicney, The ifferential diagnoses provided inc lude Severe Combined Immunedeficiency (SCID) variants D), metaholic disorder (B), and an acquired immunodeficiency (C. III).. Before investiguting ra genetic causes, crucial
out verrically transmitted HIV, which can present similarly. herefore, my first question will be about the mother's health and testing during pregnancy. <ithink>
Question: the mother tested for any infectious disenses, such HIV, during pregnancy?
The mother denies any history of infection during her prognancy and was tested negative for HIV.
<think>
The mother's negative HTV makes congenital HIV (Option C) highly unlikely. The focus shifts to primary immunedeficiencies like Adenos inc deaminase deficiency (A) and Purine nuel coside phosphorylen lase deficiency (D), both of which can cause SCID. A key radiological finding in many forms of SCID the absence of thymic shudow due lack T. cells. Asking about imaging is the most direct way investigate this possibility and differentiate f rom other causes of infection.
<ithink>
Question: Hos the patient undergone any imaging tests, such as a chest X-ray?
Yes, chest X-ray reveals absent thymic shadow and fails show any lung pathology.
J
<think>
The dialogue has established two critical facts: The mother HIV negative, riling congenital HIV infection (Option C). 2) A chest X-yay revealed an absent thymic shadow. The
combination of recurrent infections in early infancy and an absent thymic shudow is classic
presentation Severe Combined Immunodeficiency (SCID). Adenosine deaminase (ADA)
deficiency (Option A) is well-known cause of autosomal recessive SCID and perfectly matches this clinical picture. syspoxanhine-guannin phosphoribesyl transforase (HGPRT) defieiency (Option B) presents with ncurological and behavioral issucs, immunodeficiency, Purine nucleuside phosphorylase deficiency (Option D) is another, rarer cause of immunodeficiency Rased on the hallmark finding of an absent thymus, ADA deficiency the most probuble diagnosis.
<ithink>
Final Answer: A
Figure 3: Schematic diagram of the interaction flow between the Assistant Agent and the User Simulator in the multi-turn clinical reasoning environment. The process starts from an incomplete initial user query, after which the Assistant Agent asks targeted questions and the User Simulator responds strictly within the scope of predefined atomic facts, until a final answer is produced or the turn limit is reached.
A.2 TEST DATASETS
ExdicalExam: This test set is curated from a collection provided by Liao et al. (2024), comprising five distinct data sources: MedQA, MedMCQA, MMLU, SelfExam, and QMAX. The original data
14

---

Published as a conference paper at ICLR 2026
from MedMCQA and MMLU lacked the atomic facts. To address this, employed Gemini-2.5. pro to decompose the original problems into our required structure, consisting of an atomic question, atomic facts, and several answer options, using the prompt detailed in Appendix A.8. The final curated set contains 150 samples.
This dataset is derived from the medical dialogues test provided by MEDIQ LLi al. (2024)). We preprocessed this data by filtering out all samples where the atomic facts were empty. The final test set contains total of 268 samples.
MEDQA:
MedMCQA: This test set was constructed from the official validation set of MedMCQA ( Pal et al. (2022)). We first selected samples where the question description exceeded 150 characters in length. For these selected samples, we then utilized an LLM to synthesize the corresponding atomic facts and question. This process resulted in final test set of 536 samples.
A.3 DISTILLATION EXPERIMENT AND ANALYSIS
Since prompting GPT-4o alone yields results close to the best performance across all benchmarks, a natural idea is to leverage high-quality multi-turn dialogue data generated by GPT-4o or Gemini- 2.5-Pro for model distillation. Therefore, we used the same self-play prompts to have both GPT- 4o and Gemini-2.5-PP strictly simulate dialogues based on the data from the RL training dataset (14,256 samples). Then, we perform SFT on the Qwen3-8B model separately using the dialogue data generated by the two models (i.e., distilling the correct dialogue outputs from GPT-4o and Gemini-2.5-Pro separately), and test the performance. As shown in Table even with additional data and extended SFT training time, the model performance shows almost no improvement. This further confirms that the primary role of the SFT stage is teach the model the question-answer format, and does not require a particularly large dataset to achieve adequate training. However, it should be noted that the model obtained after SFT training (i.e., the starting checkpoint for RL training) can affect the data obtained during RL sampling. thereby influencing the subsequent RL training Ding et al. (2025); Guo et al. (2025a). It is also evident that SFT training alone, even with large-scale data, fails to give the model strong generalization ability, making RL training necessary for improving its generalization capabilities.
Table 2: The performance of Qwen3-8B distilled from the respective multi-tun multi-tuum dialogue outputs of GPT-4o and Gemini-2.5-Pra
Model
Dialogue Simulator
MedicalExam
MedQA
MedMCQA
GPT-4o
57.33 + 2.26
53.25 + 0.72
46.04 + 1.31
Qwen3-8B
Gemini-2.5-Pa
58.67 + 0.08
51.51 + 1.33
48.06 + 0.94
A.4 ANALYSIS OF MODEL EFFECTIVE QUESTION RATE WITH ATPO TRAINING PROGRESS
To further investigate the improvement in dialogue quality brought by ATPO training, plotted the variation curve of the proportion of effective questions (defined as questions that elicit valid re- sponses from the user) across multi-turn dialogues training progresses. As illustrated in Figure 4, the proportion of effective questions increases steadily throughout the training process, demonstrat- ing that the assistant's 's queries become more answerable for the user. This allows the assistant to gather more useful information and accomplish tasks in fewer dialogue turns, thereby enhancing the overall user experience. An example illustrating the change in dialogue quality before and after ATPO training for the Qwen3-8B model is provided in Figure 5.
A.5 COMPARATIVE ANALYSIS OF THE COMPUTATIONAL REQUIREMENTS OF DIFFERENT ALGORITHMS
To assess whether ATPO's performance gains over other algorithms are simply attributable to greater computational resources, we conducted a detailed evaluation of resource usage across methods. Specifically, we measured the time required by each algorithm to achieve the same test-set accuracy, taking the best performance of PPO as the benchmark. The results are presented in Table 3. As shown, ATPO achieves the target accuracy in the shortest time, whereas GRPO requires the longest.
15

---

Published as a conference paper at ICLR 2026
Qwen3-1.78
Owen3-4B
0.44
Owen3-86
0.40
Effective Rate
0.38
0.36
0.34
Traning Step
Figure 4: The variation curve of the proportion of effective questions for various scale models across multi-turn dialogues as ATPO training progresses.
Since all algorithms were executed on identical hardware, shorter training time directly translates to reduced computational resource consumption. Therefore, the superior performance of ATPO cannot be attributed to increased computational resources, but rather to its algorithmic effectiveness, Fur- thermore, in our experiments, observed that with continued training, PPO's curve had already converged without further improvement, while GRPO and TreePO even experienced entropy ex- plosion and crashed. Additionally, we computed the proportion of total training time spent in the rollout stage for each algorithm, as well as the computational distribution within this stage, as sum- marized in Table ATPO exhibits the highest rollout-stage proportion, approximately 45% of the total time, in contrast other methods, which are nearly identical at about 25%. Moreover, more than half of the computation in ATPO's rollout stage is used for value estimation, which is sensible ATPO frequently estimates node values during rollout dynamically allocate the rollout budget. However, these costs are meaningful, as it produces high-quality sampling data, thereby accelerat- ing model convergence. This is corroborated by Figure 2(a). where ATPO's convergence curve is steeper than those of other algorithms. In contrast, for other methods, rollout-stage computation is dominated by sequence generation, producing lower-quality sampled data that slows convergence. In summary, while ATPO allocates more time to the rollout stage, its emphasis on value estima- tion produces higher-quality data, resulting in faster convergence, reduced total training time, and ultimately lower overall computational resource consumption compared to competing algorithms.
Method
Total Time (hour)
Proportion of Rollout Time
PPO
3.02
26.16%
ATPO (U1+U2)
2.22
45.05%
ATPO (U1)
2.98
41.95%
TreePO
3.15
14.13%
GRPO
4.86
25.72% 75%
Table 3: The total time required for different algorithms to reach comparable performance, and the proportion of time spent on the rollout phase.
16

---

Published as a conference paper at ICLR 2026
Initial Info
Belore Trainied
Alkey Trainden
linu mosh magurt
poeac delh reproder
dee hes molidigg onvitin or perr tora fomder, roogle
Rorder romm saler comeoca on vabo anteain
X
Lualeg boink lem aeneudd
thee roge abfiive onderar The feeed has Docin
soleet you and
faeh priter ploaical curmiatto
De socu mee
the boies pelict
Ahars fe aude cint sagpoven aoreeaall
and love sioo du anloua gooik
ssel
ane celouati coffhieg canoget cflt
tohal
seginatur deaerved roral
The und serul tue rils right purts moune mneert ceaern
X
bulage pubacc
cain Lad lock Bric Uhaare" aen
we you aies reeer be of semeeill afteen of leal
X
The
Atomic Facts
(1 lay poss of aenus deiy contton ageal
X
Figure 5: Comparison of model dialogue quality before and after ATPO training.
Proportion of Generation TFLOPs
Proportion of Value Estimation TFLOPs
Method
Rollout TFLOPs
PPO
444, 915.23
100%
0%
ATPO (U1+U2)
639, 410.69
37.99%
62.01%
ATPO (U,)
817, 173.44
42.38%
57.62%
TreePO
916, 408.62
100%
0%
GRPO
4, 708, 526.96
100%
0%
Table 4: Rollout computation required by various algorithms reach comparable performance, along with the respective proportions allocated to generation and to value estimation.
17

---

Published as a conference paper at ICLR 2026
A.6 TESTED WITH DIFFERENT USER SIMULATORS
We employed Qwen3-8B as the user simulator in both the training and testing phases. However, relying on single simulator may lead the assistant model to overfit its specific tone or response format, potentially limiting generalization to unseen simulators. To assess this risk, we replaced the user simulator at test time with the -lama-333-70BIIntteee mance of Qwen3-1.7B, Qwen3-4B, and Qwen3-8B trained with ATPO (U1 + U2). As shown in Table 5, the assistant's performance after replacement remains almost unchanged, with no signifi- cant differences. These results indicate that the assistant model did not overfit to the tone or response style of the training user simulator and can perform effectively with an unseen simulator, thereby demonstrating strong generalization capability.
model, and re-evaluated the perfor-
Model
User Simulator
MedicalExam
MedQA
MedMCQA
Qwen3-8B
43.20 + 1.85
42.87 = 0.77
39.93 + 1.05
Qwen3-1.7B
43.07 + 1.53
43.15 + 0.60
40.07 + 1.39
Qwen3-8B
59.73 = 2.61
55.47 = 0.99
45.93 + 1.13
Qwen3-4B
Llama-3.3-70B-Instee
61.20 + 2.76
56.47 + 0.94
47.76 + 1.06
Qwen3-8B
65.87 3.72
64.07 + 0.43
53.66 1.52
Qwen3-8B
Llama-3.3 1aima--.3-70B-Instruee
67.07 + 3.35
63.93 + 1.01
55.60 1.21
Table 5: Performance of different models tested with different user simulators.
A.7 ANALYSIS OF THE COMPUTATIONAL SAVINGS OF TREE SEARCH
ATPO performs sampling based on a tree structure, which can reduce the computational cost during the sampling process. Here, we provide a brief theoretical analysis of the potential savings gained through tree expansion, following the computation statistics methodology in VeRL. (Sheng et al., 2025).
For an LLM of given size, let & denote the number of parameters in the linear projections and 0 denote the number of parameters in the attention mechanism. For specific turn in multi-turn dialogue, denote the input length of the current turn as æ and the output length as y.
If we sample one data instance at a time, using the KV cache, the prefill stage on the input incurs computational cost:
Cpeeall 2dx 40x².
During decoding, benefit from cached K and V, yielding a computational cost:
Cdscode 2óy + 20 + y + 1).
When sampling N' instances of equal length, the total computational cost without tree expansion becomes:
Cindependent = (2drr + 40x²) + (2dy + 20 + y 1)).
In contrast, with tree expansion, the prefill step is performed only once, followed by decoding N samples. The total cost becomes:
Ciree = 1 (2Ør + 40x?) + N (2dy + 20(2x + ++
The theoretical computational saving is therefore:
AC (N - 1) (20r + 40x²).
Since ATPO is grounded tree-structured sampling, it inherits this cost reduction property.
It is worth noting that TreePO (Li et al., 2025b) provides a rigorous empirical verification of tree- based sampling efficiency (Section 4. 1),, showing higher throughput in tokens per second. Compared to TreePO's s scenario, where the inference chain is divided into multiple segments for brsed sampling. our multi-turn setting produces semantically distinct tree nodes, making it naturally more amenable to tree search.
18

---

Published as a conference paper at ICLR 2026
A.8 PROMPTS
User Prompt
You are a medical information assistant. Your role to help doctors by providing informa- tion strictly from patient data.
INSTRUCTIONS:
1. Search through the provided atomic facts for information that directly answers the doctor's question
2. If you find relevant atomic facts, provide the answer using ONLY that information
3. Do NOT add any medical analysis, inference, interpretation, or external knowledge
4. Do NOT make assumptions or draw conclusions beyond what explicitly stated
5. If atomic fact directly answers the question, respond with exactly this phrase: "The patient cannot answer this question."
Patient atomic facts:
fatomic facts}
Doctor's question:
{doctor's question)
Your response:
Direct Method Prompt
You are an expert medical assistant. Based on the medical case given by user, which includes initial patient information, question, and several options, select the single best answer. Your response must be only the letter of the chosen option (e.g., A, B, C...,, without any additional text, punctuation, explanation.
Initial information:
[initial patient information]
Question: [question]
Options: [options]
Your response:
MEDIQ System Prompt
You are a professional medical assistant, possessing outstanding medical diagnostic reason- ing and analytical abilities, well as strong clinical inquiry and patient assessment skills.
Below, the user will provide initial patient information at the beginning of the first turn of conversation, pose a single-choice question (Problem: question description), and corre- sponding options (Options: option descriptions). Your task is to, based the question description, the option descriptions, the currently available patient information, and your own knowledge, select the correct option.
Note:
The imitial patient information provided by the user in the first turn is incomplete. You can ask the user questions continuously obtain more patient information until you confident enough to select the correct option.
In each turn of dialogue, you must first determine: Based on the question description, the option descriptions, the currently available patient information, and your knowledge, do you have enough confidence to select the correct option?
1. If you are not confident enough, output specific question in the following format: Question: [The specific question you want ask]
19

---

Published as a conference paper at ICLR 2026
2. If you are confident enough, output your selection in the following format: Final Answer: [Your chosen option]
Important Notes:
1. In each turn of conversation, you must make clear decision either choose an option or ask question. Do not be vague. When responding or asking, you must strictly follow the corresponding format.
2. When choosing an option, you can only choose one from the provided options (e.g-- B, C, etc.), and cannot choose multiple or include any other content.
3. When asking question, you only ask specific question at time, cannot repeat questions that have already been asked, and cannot include any other content.
4. Interaction Limit: You have a maximum turns. This means you can ask at most
7 questions and must provide your Final Answer by the 8th turn at the latest.
Initial information: [initial patient information]
Question: [question]
Options: [options]
Your response:
Atomic Facts Extraction Prompt
You are honest and knowledgeable medical assistant. I will provide medical diagnosis case in ISON format, including relevant patient information and the medical problem that needs diagnosis. Your task is to analyze the patient information and extract relevant details. Your final output must single, perfectly formatted JSON object.
Extraction Steps
1. Identify the main issue medical problem described in the information that quires diagnosis, and record it as the "question".
2. Excluding the "question" information, extract a series of key facts from the remain- ing information. Each fact should contain only one relevant information point and must self-contained.
3. From the extracted key facts, write a short introductory sentence summarizing the background of the case "context". Be careful the context should include as few atomic facts as possible, no more than two.
4. The remaining key facts should be documented as "atomic_ facts".
Output Format Requirements
1. Your only output must be complete JSON object written in English.
2. The extracted "question" information must be placed in the "question" field, the extracted "context" information must be placed in the "context" field, and the ex- tracted "atts"" information must be placed in the "atomic facts" field.
3. Output structure example:
"question": extracted question, "context""; [extracted context], "atomic.faee facts": [atomic fact1, cromic.fact)) sromic.factt, ...]
Please start extracting information based on following input: [input]
20

---

Published as a conference paper at ICLR 2026
User Simulator Quality Monitoring Prompt
You given:
1. A list of atomic facts (ground truth facts).
2. A multi-turn interaction between user and an assistant (called "output" below).
Evaluation criteria:
1. user answered related q: "yes" if the assistant asked question that is clearly re- lated any fact in the atomic facts list and the provided relevant information in their answer. If the assistant's 's question is unrelated to atomic facts, and the user responds with something like "The patient cannot answer this question.", this is acceptable and should still be marked "yes". Only mark "no" if the assistant's s question strongly related to atomic facts, the user could have answered based on them, but did not provide such an answer.
2. user hallucinated:: "yes" if the user's answer includes fabricated content not appear- ing in the atomic facts list; "no" otherwise.
Only output JSON object with exactly these two keys:
"user answered related -q: "yes" or "no", "user hallucinated"": "yes" or "no"
Do not output anything else.
Atomic facts: [atomic_facts
Conversation output: [output_text]
A.9 ATOMIC FACTS DATA EXAMPLE
Atomic Facts Data Example
1. The symptom precipitated in the morning.
2. The symptom precipitated during exams.
3. There is no history of loss of consciousness.
4. Her cousin sister has been diagnosed with epilepsy.
5. An EEG was performed and was suggestive of epileptic spikes.
21


Reviews:
[{"review_id": "JZvBfEauEl", "reviewer": "Reviewer_Dv8Q", "summary": "This paper addresses sampling for RL models being trained for multi-turn conversations with long-term objectives. Specifically, the background use-case involves answering medical multiple-choice questions in an interactive scenario where the LLMs must ask clarification questions proactively (seek information when missing) before providing the answer.\n\nTo this end, the authors extend recent work on Tree Policy Optimization developed for reasoning tasks for information-seeking conversational scenarios. The default TreePO would incur high computational costs to roll-out all possible trajectories from a given “state” for multi-turn conversations while estimating the policy and value functions during RL. \n\nTo mitigate these costs, they propose measuring the uncertainty of a state and pruning mechanisms based on this uncertainly thus making the sampling process efficient while ensuring diverse exploration. Their proposed metric combines both the epistemic uncertainty (limitations of the model wrt selection among possible actions from a given state) and aleatoric uncertainty (e.g. induced due to user responses to questions) and  only those branches which meet thresholds on uncertainty are retained resulting in efficient tree expansion during sampling.\n\nCoupled with asynchronous search architectures and KV caches that enable prefix sharing, their experiments show not only improvements in final task (MCQA) accuracy but are also compute efficient. In particular, their performance is on-par with SOTA and slightly out-performs GPT-4o model using a significantly smaller Qwen3-8B model on three different datasets from the medical domain.", "questions": "- Would like to see some discussion on how this may work in “real world” usage where the MCQ options are not available? How might that look like? How will the process scale when the number of possibilities become 10 instead 4? What are the consequences when the user assistant does not behave “ideally” providing the correct answer in response during inference? May be the above can be discussed using the anecdotal example in Figure 3.\n\n- Some discussion on where the pruning might breakdown, chances of throwing out useful trajectories? Intuition for setting the threshold, how does one do this in practice and why was it set to 0.5/1.5 in your experiments? \n\n- Lines 255-257 seems to be missing some qualification information, as to when the critic value estimates are used -- requires rewriting for clarity.\n\n- For the datasets, where atomic fact extraction was done with Gemini etc (Appendix A.2), include the prompts and other details or provide references, if same as those used for other datasets. What does an atomic fact look like? How do you ensure with GPT-4o that the user assistant is behaving correctly? (305-308)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper makes a good extension to recent works on using TreePO for training RL models for reasoning tasks and conversation forests on the task of answering MCQs in medical domain. This is an important task in the important domain of medical diagnosis that may specifically prefer small, in-house models than proprietary ones such as GPT.\n\nThe paper is well-written, building up the intuition for the proposed metric as well as the developing equations for actor/policy and critic/value updates.\n\nThe main claims are suitably supported via detailed experiments and ablation studies on three separate datasets from the topic. \n\nOverall, a valuable contribution advancing the state-of-the-art in modeling efficiency aspects of sampling in RL for multi-turn conversations.", "weaknesses": "Not weaknesses specifically but some areas for improvement where details are lacking or there are clarity issues are listed below--\n\n- Contributions (line 84) --This aspect is not really highlighted much in the paper and as such the setup seems identical to that described in the TreePO paper (Li et al 2025b cited by the authors). If different, please highlight the differences and why this forms a core contribution. \n\n- In general, the performances in Table-1 seem very close to TreePO in many instances—would like to see some explanation on key differences between the two methods (if there is anything else apart from the pruning aspect which save on computation)—the lines 333-338 are not very clear \n\n- Overall discussion on parameters, possible application in practice, and some details on experiments need presentation improvements, some of which are listed in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Kpt2s5FLiu", "reviewer": "Reviewer_8sJu", "summary": "This paper proposes a framework, namely ATPO, for generating multi-turn medical dialogues, which enhances the performance of LLMs in medical QA datasets.", "questions": "I encourage the authors to keep polishing this work. If the authors can improve or convince others about the Cons (1) and (2), and reorganize the paper, I believe this can be a good work.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "(1) This paper has some theoretical derivation for the framework.", "weaknesses": "1) However, I find some parts of the theoretical derivation questionable. 1） When defining the Bellman error in equations (1) and (2), the authors use a one-step lookahead. This is questionable since with one step, there is no long-term reward (i.e., long-term exploration). In this case, equations (1) and (2) would collapse to the average reward of all the states. If the authors finally generate an answer based on the whole dialogue, it makes more sense to enable the Bellman error to look multiple steps. 2) When writing equations (1) and (2), the authors need to freeze one of the critics to calculate the Bellman error. I didn't see any mention of this.\n(2) This is a fundamental question. The authors are using LLM-generated data to train LLM. This can be problematic. For example, the authors used Gemini-2.5-Pro to simulate the conversation data. There will be data leakage if the Gemini-2.5-Pro also uses the same dataset for its pretraining or fine-tuning. Thus, the improvements in Table 1 can be attributed to the data leak.\n(3) The title of this paper talks about the optimization for multi-turn medical dialogue. But there is no evaluation of the quality of the generated dialogue! Instead, the authors use medical QA performance to justify the usefulness of the multi-turn dialogue. The authors need to think clearly about this. If your purpose is to have a better performance on medical QA, then you need to compare with the SOTA methods. If the purpose is to generate better multi-turn medical dialogue, you need to improve Cons (1) and (2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5GNDXiCKzW", "reviewer": "Reviewer_Pcyh", "summary": "This paper proposes a new RL training method to improve LLMs ability at solving medical multi-turn dialogues, which involves asking many (clarification/diagnosis) questions in multiple turns before returning the final answer. The authors identify that a key challenge in optimizing multi-turn dialogue is the high uncertainty in user's responses, resulting in often insufficient exploration/data coverage for training a robust enough medical agent. The proposed method (ATPO) aims to solve this by utilizing tree search algorithms, so that during RL rollout ATPO prioritizes on expanding nodes with high uncertainty. During optimization, ATPO then treats each branch of the search tree as an independent trajectory to perform loss computation/backpropagation. The authors experimented on three medical benchmarks and showed improved performance of ATPO compared to baselines such as GRPO and TreePO.", "questions": "- Have the authors measured test performance when a user simulator *different from training* is used (e.g., LLaMA-3.3 or LLaMA-4 models). It is likely that RL training with a fixed user simulator may overfit to specific tone/response formats of the user simulator used during training, and may not generalize to other unseen users/user simulators at test time.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The notion to expand nodes and allocate more rollout budget to states with high uncertainty is sound. I believe the overall design (with some abstractions) could be applicable to other dialogue tasks beyond medical benchmarks.\n\n- The authors provided evaluation on three different medical benchmarks, showing improvement of ATPO compared to other training methods such as GRPO and TreePO.\n\n- The authors also provided interesting analysis of performing tree-based training during RL. Specifically, the authors experimented with using different uncertainty metrics during RL/the importance of down-weighing policy updates by node visit counts for stability.", "weaknesses": "Despite the overall positive experimental results, I believe there are some uncertainty/flaw in the experimental setup that could substantially undermine the results and comparisons made. If these are addressed I am willing to increase my soundness and overall score. I detail them below.\n\n\n1. Tree based methods generally requires much more compute compared to methods such as PPO/GRPO, as they need to perform multiple policy and value inference per state. However, neither Table 1 nor Figure 2 reports FLOPs statistics or # of LLM calls during rollout, raising concerns that the observed gains may stem from simply using more compute rather than true algorithmic improvements. I suggest the author to (1) report FLOPs used during rollout stage across different methods (especially comparing search based method such as ATPO and non-search based method such as GRPO and PPO), and (2) provide compute-equal comparisons between ATPO and methods such as GRPO and PPO (e.g., if ATPO uses N flops during the entire rollout stage, adjust the batch size and group size of GRPO so that it also uses N flops during rollout).\n\n\n2. Many results in Table 1 are actually improvements *within one standard deviation*. For example, the MedQA and MedMCQA result on Qwen3-1.7B (TreePO vs ATPO), MedMCQA result on Qwen3-4B, and MedicalExam and MedMCQA result on Qwen3-8B. Additionally, simply prompting GPT-4o already achieves performance within one standard deviation of the best results across all benchmarks. Could the authors provide a statistical significance analysis to confirm whether these improvements are indeed meaningful?\n\n\n3. Since simply prompting GPT-4o achieves near best result (within one standard deviation) in Table 1 across all benchmarks, I wonder why did the author not compare against a simple baseline of directly distilling (correct) dialogue outputs obtained by prompting GPT-4o? Instead, this paper uses self-play data obtained from Gemini-2.5-Pro (L321-323), whose performance is also not reported in Table 1. This is because (1) improvements from RL tends to heavily depends on the quality of the initial SFT checkpoint, which may be undertrained in this work; (2) distilling outputs from GPT-4o is far more computationally efficient than SFT + RL, making it a more practical choice in the context of this paper if prompting GPT-4o already achieves near-best performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HQctUvxJ7S", "reviewer": "Reviewer_PxMc", "summary": "This paper proposed an adaptive tree policy learning method for multi-turn dialogue systems. It builds a conversation tree to calculate the value of nodes and uses reinforcement learning algorithms to improve the system with feedbacks. An uncertainty-aware tree expansion component is also introduced to expand the conversation tree. Experiments show performance improve on different datasets and different large language models.", "questions": "This methods seem more general. Can it be applied to general conversation settings other than the medical domain?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The designs of the framework seem reasonable, because conversation has different flows and can be modeled as a tree.\\\n2. The presentation of the paper is clear.\n3. Experiments demonstrate performance improvement on different datasets and different models.", "weaknesses": "1. It will be better if other aspects of conversation quality, such as informativeness and helpfulness can be evaluated.\n2. The paper claims an improvement of computation cost with KV cache techniques, so a detailed analysis on efficiency will be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)