BEDA: Belief Estimation as Probabilistic Constraints for Performing Strategic Dialogue Acts
Hengli Li, Zhaoxin Yu, Qi Shen, Chenxi Li, Mengmeng Wang, Tinglang Wu, Yipeng Kang, Yuxuan Wang, Song-Chun Zhu, Zixia Jia, Zilong Zheng
2026-01-01
Summary
This paper focuses on making computer agents better at having strategic conversations, meaning conversations where they have goals and need to influence others to achieve them.
What's the problem?
Previous attempts at building these conversational agents were good at *understanding* what the other agent believes, but didn't have a good way to actually *use* that understanding when deciding what to say next. Essentially, they knew what the other person thought, but didn't consistently act strategically based on that knowledge.
What's the solution?
The researchers created a new framework called BEDA. BEDA works by first identifying two key types of conversational moves: trying to trick the other agent (Adversarial) and trying to get on the same page (Alignment). Then, it uses the estimated beliefs about what the other agent thinks to limit what the agent *can* say, making sure its responses are consistent with a strategic approach. It has three parts: a 'world' to represent the situation, a 'belief estimator' to figure out what the other agent believes, and a 'conditional generator' to choose what to say based on those beliefs.
Why it matters?
This work is important because it shows a simple and effective way to make conversational AI more strategic and reliable. By treating belief estimation as a constraint on what an agent says, it consistently outperformed other methods across different types of conversations, like games of deception, cooperation, and negotiation, even when using relatively small AI models. This means we're closer to creating AI that can truly engage in meaningful and goal-oriented dialogue.
Abstract
Strategic dialogue requires agents to execute distinct dialogue acts, for which belief estimation is essential. While prior work often estimates beliefs accurately, it lacks a principled mechanism to use those beliefs during generation. We bridge this gap by first formalizing two core acts Adversarial and Alignment, and by operationalizing them via probabilistic constraints on what an agent may generate. We instantiate this idea in BEDA, a framework that consists of the world set, the belief estimator for belief estimation, and the conditional generator that selects acts and realizes utterances consistent with the inferred beliefs. Across three settings, Conditional Keeper Burglar (CKBG, adversarial), Mutual Friends (MF, cooperative), and CaSiNo (negotiation), BEDA consistently outperforms strong baselines: on CKBG it improves success rate by at least 5.0 points across backbones and by 20.6 points with GPT-4.1-nano; on Mutual Friends it achieves an average improvement of 9.3 points; and on CaSiNo it achieves the optimal deal relative to all baselines. These results indicate that casting belief estimation as constraints provides a simple, general mechanism for reliable strategic dialogue.