# Enhancing Language Model Rationality with Bi-Directional Deliberation
Reasoning

Yadong Zhang 1 Shaoguang Mao2 Wenshan Wu2
Yan Xia2 Tao Ge2 Man Lan1 Furu Wei2
1 East China Normal University
2 Microsoft Research
https://aka.ms/GeneralAI Work was done when interning at Microsoft Research
Asia.

###### Abstract

This paper introduces BI-Directional DEliberation Reasoning (BIDDER), a novel
reasoning approach to enhance the decision rationality of language models.
Traditional reasoning methods typically rely on historical information and
employ uni-directional (left-to-right) reasoning strategy. This lack of bi-
directional deliberation reasoning results in limited awareness of potential
future outcomes and insufficient integration of historical context, leading to
suboptimal decisions. BIDDER addresses this gap by incorporating principles of
rational decision-making, specifically managing uncertainty and predicting
expected utility. Our approach involves three key processes: Inferring hidden
states to represent uncertain information in the decision-making process from
historical data; Using these hidden states to predict future potential states
and potential outcomes; Integrating historical information (past contexts) and
long-term outcomes (future contexts) to inform reasoning. By leveraging bi-
directional reasoning, BIDDER ensures thorough exploration of both past and
future contexts, leading to more informed and rational decisions. We tested
BIDDER’s effectiveness in two well-defined scenarios: Poker (Limit Texas
Hold’em) and Negotiation. Our experiments demonstrate that BIDDER
significantly improves the decision-making capabilities of LLMs and LLM
agents.

##  1 Introduction

The rapid advancement of large language models (LLMs) has significantly
enhanced natural language understanding and generation [29]. However, as the
application scope of LLMs expands, they often struggle to make rational and
optimal decisions in real-world scenarios[8, 10, 23], particularly in complex
environments that require careful consideration of both historical data and
potential future outcomes.

Existing methods predominantly enhance reasoning performance by navigating
through the problem space and selecting optimal nodes (states) based on the
progress toward solving the problem [43, 49]. These unidirectional (left-to-
right) reasoning approaches limit LLMs’ ability to effectively leverage future
information, resulting in suboptimal decisions due to insufficient integration
of historical context with potential future outcomes [18]. To address these
shortcomings, we propose BI-Directional DEliberation Reasoning (BIDDER), a
novel approach designed to enhance decision rationality. BIDDER leverages the
strengths of classical bi-directional modeling, as exemplified by
Bidirectional Encoder Representations from Transformers (BERT [9]), and
integrates these with decision theory principles to overcome the limitations
of traditional reasoning methods in LLMs.

The key innovation of BIDDER lies in its bi-directional reasoning capability,
which ensures a thorough exploration of both past and future contexts. As
illustrated in Figure 1, unidirectional reasoning utilizes historical context
to make left-to-right decisions. In contrast, bi-directional reasoning
explores potential future states and predicts the expected utility for future
moves, using both historical contexts and future exploration contexts for more
informative reasoning.

Figure 1: Comparing Unidirectional and Bi-Directional Reasoning:
Unidirectional reasoning utilizes historical context to make left-to-right
decisions. In contrast, bi-directional reasoning explores potential future
states and aggregate the expected utility for future moves. It then uses both
historical contexts and future exploration contexts to conduct bi-directional
reasoning.

BIDDER’s approach involves three main processes: inferring hidden states to
represent uncertain information from historical data, using these hidden
states to explore future potential states and outcomes, and integrating both
historical contexts and future explorations to inform reasoning. By leveraging
these bi-directional deliberation processes, BIDDER enables LLMs to make more
informed and rational decisions. Although future information cannot be
directly obtained, BIDDER refers to the Q-Learning [42] algorithm in
Reinforcement Learning, employing LLMs to explore various future time horizons
and use this information to calculate the expected utility of potential
actions.

To demonstrate BIDDER’s effectiveness, we conducted experiments in two well-
defined strategic decision-making scenarios: Poker (Limit Texas Hold’em) [50]
and Negotiation [21, 6]. These scenarios provide a rigorous testbed for
evaluating the decision-making capabilities of LLMs due to their clear
comparison of final payoffs and well-established theoretical optimal
solutions. Our experimental results show that BIDDER significantly enhances
the decision-making capabilities of LLMs, aligning their behavior more closely
with optimal solutions. By incorporating bi-directional deliberation
reasoning, BIDDER minimizes uncertainty, considers long-term payoffs, and
ensures that LLMs can effectively integrate both historical context and future
explorations into their decision-making processes.

The contributions of this work are as follows:

  * •

We introduce the first bi-directional reasoning approach with LLMs to enhance
their decision rationality by considering both historical context and future
potential outcomes. Unlike traditional methods that focus solely on past
information, this bi-directional reasoning helps manage uncertainty and
predict expected utility more effectively.

  * •

We incorporate principles from the Q-Learning algorithm, leveraging LLMs to
explore future trajectories and aggregate rewards, thereby constructing
reasoning contexts that include potential future outcomes.

  * •

We validate BIDDER’s effectiveness through rigorous experiments in strategic
decision-making scenarios, demonstrating its superiority over traditional
reasoning methods.

##  2 Method

Figure 2: BI-Directional DEliberation Reasoning includess: 1. Hidden State
Inference: Inferring hidden states (e.g. opponent’s strategies) behind
decision-making from historical data (e.g. opponent’s actions); 2. Future
Exploration: Exploring possible future trajectories based on inferred states;
3. Action Reward Collection: Aggregating utilities from predicted trajectories
to make decisions. The bi-directional reasoning enhances decision rationality
by incorporating both historical context and potential future outcomes.

BI-Directional DEliberation Reasoning (BIDDER) is designed to enhance the
decision rationality of LLMs. It is based on the concepts of uncertainty and
expected utility in decision theory [1] and leverages bi-directional reasoning
to incorporate both historical context and potential future outcomes into the
decision-making process. Since future contexts are not available at the
decision point, we refer to the Q-Learning algorithm in Reinforcement Learning
[42], calculating the expected total reward for taking different actions in a
given state as the context for right-to-left reasoning.

Figure 2 illustrates the entire process of this method. Specifically, BIDDER
consists of three modules: 1) inferring hidden states behind decision-making
from available historical data, 2) utilizing the inferred hidden states to
explore future trajectories, and 3) aggregating the utilities along each
explored trajectories and making decisions to maximize the expected long-term
utility.

In order to simplify the complexity of the description, we will limit the
subsequent discussion to a two-player game, referring to the current player as
"player" and the other participant as "opponent." We standardize the notation
here:

  * •

The player’s initial hidden state $s_{0}$ , and the opponent’s hidden state
$\overline{s}_{0}$.

  * •

The player’s public trajectory at time $t$:
$\mathcal{\tau}(t)=\\{a_{0},s_{1},\dots,s_{t}\\}$ (as the hidden state,
$s_{0}$ is unobservable by other players) , and the opponent’s trajectory
$\mathcal{\overline{\tau}}(t)$.

###  2.1 Infer Hidden State From History

Inferring hidden states is essential for understanding environmental changes
influenced by latent variables, such as an opponent’s status or strategy in a
game. Predicting these variables allows for a more accurate reconstruction of
future behaviors, enhancing the rationality of decision-making.

Previous research [15, 45] has shown that LLMs can recognize contextual causal
relationships and correct causal arguments with high probability. Therefore,
we use a causal reasoning approach to infer environmental information, with
historical data $\mathcal{\overline{\tau}}(t)$ as the effect and environmental
uncertainties $\overline{s}_{0}$ as the causes.

Formally, we consider the relationship
$P(\mathcal{\overline{\tau}}|\overline{s}_{0})$, where $P$ represents the
probability distribution. By analyzing
$P(\mathcal{\overline{\tau}}|\overline{s}_{0})$, we aim to estimate the causal
factors $\overline{s}_{0}$ influencing the observed data
$\mathcal{\overline{\tau}}$. The LLM can be regarded as an implicit Bayesian
inference model, inferring hidden states $\overline{s}_{0}$ based on observed
data $\mathcal{\overline{\tau}}$, et al.
$P(\overline{s}_{0}|\mathcal{\overline{\tau}})$.

Hidden State Inference Prompt
$\overline{s}_{0}=\mathrm{Hidden\\_Inference}(\mathcal{\overline{\tau}})$
Opponent Action History:
[Opponent Trajectory]
Possible Hidden States for Opponent’s Actions:
[Discretized State Space List]
Select the most likely state of the opponent.

In this prompt, [Opponent Trajectory] represents the opponent’s observed
actions (historical data $\mathcal{\overline{\tau}}$), and [Discretized State
Space List] enumerates possible hidden states $\overline{s}_{0})$ causing
these actions. The LLM processes this information and selects the most
probable hidden state $\overline{s}_{0}$, thereby inferring the causes from
the effects. This method leverages the LLM’s ability to understand and reason
about complex causal relationships, enabling effective prediction and
decision-making in uncertain environments.

###  2.2 Explore Future Trajectories with Opponent Modeling

Opponent Modeling Prompt
$\overline{a}^{\prime}_{t}=\mathrm{Opponent\\_Modeling}(\overline{\tau}(t))$
Inferred Hidden State of Opponent:
[Opponent’s Hidden State]
Opponent Action History:
[Opponent Trajectory]
Select the most likely action which opponent will take under inferred hidden
state.

Based on the hidden states inferred in Section 2.1 and opponent’s behavioral
records, we simulate their likely actions under various states using prompts.

At the current decision point $t$, we explore all possible actions with the
following termination conditions:

  * •

Reaching the preset exploration horizon $T$.

  * •

Reaching a terminal state or a chance node111A chance node signifies the
introduction of new information that can influence decisions. For instance, in
Texas Hold’em poker, this occurs when a new community card is revealed..

For the current reasoning point, we generate a set of exploration paths based
on opponent modeling:

$\begin{array}[]{c}\mathcal{T}(t)=\\{\tau\mid\tau=(s_{t},a^{\prime}_{t},\ldots,a^{\prime}_{t+T-1},s_{t+T})\\}\end{array}$
(1) $s_{t+1}=s_{t}\times a^{\prime}_{t}\times\overline{a}^{\prime}_{t}$ (2)

Here, $\mathcal{T}(t)$ represents the set of all possible trajectories
starting from the current state $s_{t}$. Each trajectory $\tau$ consists of a
sequence of states and actions, starting from the current state $s_{t}$, and
includes the sequence of actions $a^{\prime}_{t},\ldots,a^{\prime}_{t+T-1}$
and the explored states $s_{t+1},\ldots,s_{t+T}$ up to the exploration horizon
$T$. For the detailed algorithm of future trajectories exploration, please
refer to Appendix C.

###  2.3 Aggregate Rewards for Explored Trajectories

Action Reward $r$ Calculation Prompt
$r(s_{t})=\mathrm{Reward\\_Calculation}(\overline{s}_{0},s_{t})$ All
historical information (including Player and Opponent):
[Trajectories of Player and Opponent]
Feasible Actions of the Current State:
[Feasible Actions]
Estimate the possible payoff $r$ for each action, and $r$ must be normalized
to between 0 and 1.

We use LLMs to estimate the rewards for the potential payoff of explored
paths. This extends the paths in Equation 1 to include estimated rewards. We
utilize the Bellman equation [2, 35] to aggregate the return of each trace
$\tau$:

$G(\tau)=\sum_{k=0}^{T}\beta^{k}r(s_{t+k})$ (3)

Here, $G(\tau)$ is the total reward accumulated along the path $\tau$,
$r(s_{t+k})$ is the reward at horizon $k$, and $\beta$ is the discount factor,
determining the importance of future rewards.

The return for each current action $a$ is calculated as follows:

$\begin{array}[]{c}G(a)=\max_{\tau\in\mathcal{T}(t,a)}G(\tau)\end{array}$ (4)
$\mathcal{T}(t,a)=\\{\tau\mid\tau=(s_{t},a^{\prime}_{t}=a,\ldots,a^{\prime}_{t+T-1},s_{t+T})\\}$
(5)

Here, $G(a)$ is the maximum cumulative return starting from the current time
step $t$ and taking action $a$. The set $\mathcal{T}(t,a)$ represents all
possible trajectories starting from the current state $s_{t}$ and action $a$.

Finally, the LLM makes decisions based on the past available information, the
inferred hidden states and the future long-term returns of each action at the
current point in time:

Decision Making Based on Bidirectional Deliberation Reasoning
$a_{t}^{*}=\mathrm{Decision\\_Making}(s_{t},\overline{s}_{0},\\{G(a)\\})$
[Past Trajectory and Player’s Current State]
Inferred Hidden State of Opponent:
[Opponent’s Hidden State] #Left-to-right Deliberation Reasoning
Possible Hidden States of Opponent:
[$\\{G(a)\\}$ of all feasible actions in current state] #Right-to-left
Deliberation Reasoning
Make the most rational decisions based on current information.

This bidirectional deliberation reasoning framework enhances decision
rationality by incorporating both historical contexts and potential future
outcomes into the decision-making process to minimize uncertainty.

##  3 Experiments

###  3.1 Limit Texas Hold’em

We utilized two-player Limit Texas Hold’em as our testbed. Limit Texas Hold’em
is a popular betting game which, unlike no-limit Texas Hold’em, restricts the
number of raises and fixes the raise amount. The detiled game rule of Limit
Texas Hold’em can be found in the Appendix A.1. Among the two game
participants, we refer to the focal participant as the Player, while the other
participant is designated as the Opponent.

We randomly generated 100 game sessions. To enhance the diversity of the
hands, we increased the frequency of strong hands appearing in these 100
games. The specific distribution of hand types is detailed in the AppendixA.1.
For fairness, each game has a mirrored game, where the Player and the Opponent
switch their hands.

####  3.1.1 Baselines

We adapt a variety of approaches to comprehensively compare the performance of
methods from different sources in Limit Texas Hold’em environment. These
methods include:

Rule-Based Approaches:

Random: Randomly selects an action from the set of feasible actions.

Rule: Predefined procedures that select actions based on hand strength, such
as raising when holding a pair.

Counterfactual Regret Minimization (CFR) [58] : An iterative algorithm that
converges to a Nash equilibrium in two-player zero-sum games.

Machine Learning Approaches:

Deep Q-Network (DQN) [27]: Utilizes deep neural networks to approximate the
Q-value function, addressing decision-making problems in high-dimensional
state spaces.

Deep Monte Carlo (DMC) [33]: Integrates deep learning with Monte Carlo
methods, using deep neural networks to generate efficient samples to estimate
the expected value of complex distributions.

Deep CFR [5]: Combines deep learning with counterfactual regret minimization,
employing neural networks to approximate regression targets for strategy
solving in complex games.

LLM Reasoning Approaches:

Direct: The LLM generates the final action in response to the given game
setting prompt.

Chain-of-Thought (CoT) [43, 20]: A zero-shot native reasoning method where the
LLM follows a step-by-step thought process.

Reflexion [32]: This method refers to the concept of language agents with
verbal reinforcement learning.

####  3.1.2 Main Result

We utilized the gaming environment described in the Section 3.1. Table 1
presents the performance of different methods when facing various opponents,
with the values representing the average final chips obtained over 100 games.

|  |  Player Opponent
---
Random | Rule | CFR | DQN | DMC | DeepCFR | AVG
| Random | -0.28 | -0.05 | -0.56 | -1.87 | -0.55 | -1.89 | -0.87
Rule | Rule | 0.01 | -0.14 | 0.04 | 0.21 | -0.07 | 0.33 | 0.06
| CFR | 0.55 | -0.17 | -0.38 | -3.15 | -1.89 | -3.88 | -1.49
| DQN | 2.61 | 0.19 | 2.86 | 0.06 | -0.03 | -5.28 | 0.07
| DMC | 1.53 | 0.34 | 1.41 | 0.17 | -0.09 | -0.038 | 0.55
Reinforcement Learning | DeepCFR | 1.55 | 0.11 | 2.85 | 3.15 | -0.03 | -0.67 | 1.16
| Direct | 0.86 | 0.68 | 0.74 | -0.30 | -0.12 | -0.30 | 0.26
| CoT | 0.99 | 0.49 | 0.83 | 0.71 | 0.42 | -0.64 | 0.47
LLM Reasoning | Reflexion | 1.42 | 0.48 | 0.76 | 1.00 | 0.44 | -0.53 | 0.60
| T=1 | 2.66 | 0.74 | 2.83 | 1.61 | -0.10 | 1.45 | 1.53
| T=2 | 2.47 | 0.74 | 3.39 | 1.61 | -0.10 | 1.44 | 1.59
BIDDER (Ours) | T=3 | 1.61 | 0.74 | 2.76 | 1.87 | -0.14 | 0.39 | 1.21

Table 1: The outcomes (payoff) of various models against different opponents
in Limit Texas Hold’em. To more clearly distinguish between varying degrees of
Payoff, the background color will be greener as the profit increases and
redder as it decreases.

From Table 1, it is evident that compared to the previous LLM Reasoning method
(Direct, CoT and Reflexion), BIDDER shows significant improvement when facing
different opponents, demonstrating a noticeable increase in average earnings.

Additionally, in comparison with Machine Learning methods, BIDDER
astonishingly outperformed. It is noteworthy that BIDDER relies solely on LLM
for bidirectional information judgment, operating as a completely non-learning
method. This highlights the potential of BIDDER in decision-making based on
LLM.

####  3.1.3 Rationalality Evaluation

% | P vs O | Random | Rule | CFR | DQN | DMC | DeepCFR | AVG
---|---|---|---|---|---|---|---|---
Rule | Random | 33.72 | 37.76 | 29.65 | 34.52 | 34.22 | 32.52 | 33.73
Rule | 35.29 | 36.44 | 44.81 | 48.36 | 43.54 | 42.08 | 41.75
CFR | 46.43 | 51.43 | 37.77 | 39.38 | 42.22 | 40.82 | 43.01
Reinforcement Learning | DQN | 54.86 | 54.59 | 60.45 | 51.66 | 64.48 | 52.65 | 56.45
DMC | 42.00 | 50.62 | 43.51 | 29.36 | 39.3 | 28.95 | 38.95
LLM Reasoning | Direct | 6.20 | 2.01 | 6.90 | 5.56 | 7.85 | 2.43 | 5.16
CoT | 9.32 | 2.05 | 11.43 | 11.6 | 15.6 | 6.96 | 9.49
BIDDER (Ours) | T=1 | 65.51 | 55.75 | 66.76 | 47.29 | 80.81 | 28.68 | 57.47
T=2 | 68.38 | 58.62 | 70.09 | 45.77 | 79.24 | 29.79 | 58.97
T=3 | 66.03 | 55.75 | 69.85 | 45.59 | 78.65 | 28.98 | 57.47
Equilibrium |  DeepCFR 222Due to the presence of random perturbations in the calculation of CFR, the results are not 100% consistent. | 91.99 | 91.07 | 93.7 | 89.45 | 93.15 | 83.69 | 90.51

Table 2:  The Rational Degree (%) of various models in Limit Texas Hold’em
against different opponents, as calculated by Equation 6.

Equilibrium can be viewed as a stable state in a multi-agent game environment,
achieved by each participant through a rational decision-making process. In
most cases, it can be regarded as the most rational decision. We take the
behavior at each decision point of DeepCFR as the optimal solution $a_{o}$,
and compare the rationality levels of different methods with the optimal
solution.

The quantitative calculation method is:

$\mathrm{Rational\ Degree}=\frac{\\#\\{a=a_{o}\\}}{\\#\\{\mathrm{All\ action}\
a\\}}$ (6)

Figure 3: Direct, BIDDER, and DeepCFR Action Distribution in Limit Texas
Hold’em.

Table 2 shows the rationality levels of different methods when facing various
opponents. From Table 2, we can see that BIDDER has significantly improved the
$\mathrm{Rational\ Degree}$ compared to previous LLM Reasoning methods and
Machine Learning methods. This indicates that BIDDER has enhanced the decision
rationality of the LLM.

Additionally, we further analyzed the action distribution of different methods
in Limit Texas Hold’em. From Figure 3, we can observe that compared to the
Direct approach, BIDDER has a much higher frequency of Raise, which aligns
with the optimal solution (DeepCFR). In contrast, the Direct approach shows
higher frequencies of Call and Check, indicating that an LLM-based approach
acts as a passive decision-maker. BIDDER, however, calculates future returns
and prompts the LLM to act based on these returns, transforming the LLM into
an active decision-maker. This active decision-making is rational, leading to
improved returns.

###  3.2 Negotiation

Negotiation requires complex communication and reasoning skills, making it an
ideal environment for studying artificial intelligence and classical game
theory [28, 38] due to its dynamic, controllable, and easily assessable
nature. We utilize a game paradigm known as "division of a common pool of
items," as defined in previous research. In this game, agents are tasked with
establishing a mutually acceptable division of items while having their own
hidden utilities for each item. Our rules are based on those outlined by Cao
et al., with the following modifications: ensuring that each individual’s
total value for all items is equal (consistent with Lewis et al.), which is
more equitable compared to the original uniform distribution between 1 and 10.
The experiment consists of 100 games, with each game having a different number
and distribution of item values. Additionally, symmetrical experiments are
conducted by swapping the values for both parties in another game.

####  3.2.1 Baselines

We use widely adopted baselines for reasoning and decision-making comparisons,
including Direct and CoT introduced in Section 3.1.1. Additionally, we
consider:

Monte Carlo Tree Search (MCTS) [7]: This is a heuristic search algorithm that
efficiently explores large search spaces by sampling potential future outcomes
through Monte Carlo simulations.

Tree of Thoughts (ToT) [49]: This approach simulates human System 2 thinking
and excels in complex problems, particularly those requiring search and
judgment.

It is important to note here that although BIDDER fundamentally employs tree
search for future exploration, similar to MCTS and ToT, BIDDER’s search
process integrates opponent hidden information inference and opponent behavior
modeling. This contrasts with MCTS’s probabilistic sampling and ToT’s self-
exploration approach.

####  3.2.2 Metrics

We employ three metrics for negotiation as defined by Lewis et al., which are:

Score: The average score obtained in each game where an agreement is reached.
The score is calculated as the sum of the products of each item assigned to
the agent and its value.

Agreement: The probability of reaching an agreement across all games.

Pareto Optimality: The percentage of Pareto optimal solutions for the agreed
deals. 333Pareto optimal refers to a state in which it is impossible to
improve individual’s situation without worsening other’s.

These metrics not only reflect the agent’s competitive advantage in
negotiations but also demonstrate its cooperative behavior.

####  3.2.3 Result

|  Player Opponent
---
MCTS | Direct | CoT | ToT | BIDDER | Avg
MCTS | [14.8, 100%, 60%] | [15.9, 100%, 20%] | [22.4, 100%, 30%] | [18.5, 100%, 17%] | [15.0, 100%, 33%] | [17.3, 100%, 32%]
Direct | [15.9, 100%, 20%] | [11.2, 50%, 40%] | [16.2, 50%, 40%] | [11.2, 50%, 60%] | [21.0, 17%, 0%] | [15.1, 53%, 32%]
CoT | [25.2, 100%, 30%] | [22.0, 50%, 40%] | [22.4, 70%, 29%] | [16.4, 80%, 50%] | [23.0, 67%, 0%] | [21.8, 73%, 30%]
ToT | [20.8, 100%, 17%] | [15.0, 50%, 60%] | [16.4, 80%, 50%] | [19.8, 71%, 20%] | [21.5, 67%, 0%] | [18.7, 74%, 29%]
BIDDER(Ours) | [30.3, 100%, 33%] | [21.0, 17%, 0.0%] | [18.0, 67%, 0%] | [17.0, 67%, 0%] | [24.0, 50%, 33%] | [22.6, 60%, 13%]

Table 3: Performance of various models in Negotiation against different
opponents, and each cell represents [Score, Agreement, Pareto Optimality]

From Table 3, we can observe that compared to MCTS, the reasoning methods
based on LLM show significant improvements over the Direct approach in both
Score and Agreement metrics. Additionally, all methods achieved 100% Agreement
when competing against MCTS. This is because MCTS is more inclined to agree,
yet it fails to achieve higher gains in terms of score. Furthermore, compared
to the results reported by Lewis et al., the scores for LLM reasoning methods
on Pareto optimality are generally lower. We believe there are two possible
reasons for this: first, the tested methods are all zero-shot, so LLMs cannot
effectively predict the timing for achieving Agreement; second, negotiation is
a game that requires both competition and cooperation, and balancing these two
aspects poses a challenge for LLMs.

Moreover, we found that BIDDER achieved moderate Agreement but had the highest
Score (payoff). This also reflects BIDDER’s rational decision-making when
aiming for payoff maximization, especially when long-term planning is
required.

##  4 Related Work

###  4.1 Enhanced Reasoning Methods of LLMs

Large Language Models (LLMs) demonstrate remarkable proficiency in a range of
complex reasoning tasks, such as mathematical reasoning [26, 31], common sense
understanding [37, 4], and symbolic reasoning [34, 36]. A key technique in
enhancing LLM reasoning is the Chain-of-Thought (CoT) method, which involves
decomposing complex questions into a series of intermediate steps [43, 20].
Building upon CoT, researchers have developed methods such as Tree of Thought
(ToT) [49], Graph of Thought (GoT) [3], and Skeleton-of-Thought [30] to
further advance reasoning processes. To enhance the consistency and quality of
LLM responses, methods like Self-Refine [25] and Reflexion [32] introduce
iterative refinement, while several works [12, 41] integrate detailed persona
information to improve rationality and knowledge precision in LLM reasoning.

Existing methods such as ToT and GoT enhance reasoning performance by
navigating through the problem space and selecting optimal nodes (states).
States are evaluated based on the progress toward solving the problem.
However, these approaches typically involve unidirectional state transitions
and reward generation. In contrast, our work introduces a bidirectional
approach, allowing for a more dynamic and rational reasoning process.

###  4.2 Heuristic Search for LLM Reasoning

With the widespread application of LLMs in the field of natural language
processing, enhancing their reasoning capabilities has become a research
focus. Heuristic search algorithms, as an effective optimization technique,
are being introduced into LLM reasoning to improve efficiency and accuracy.
Specifically, Yao et al. proposed the ToT algorithm based on "System2," which
constructs a search tree by generating candidate actions through LLM and
evaluating them. Subsequently, more methods such as A* algorithm and Monte
Carlo Tree Search (MCTS) have been proposed to enhance LLM’s reasoning and
planning capabilities [11, 17, 57]. To further improve the efficiency and
accuracy of search paths, researchers have also introduced major voting[40],
self-verification[44, 51], training value functions[39], and game-theory-based
solutions[14, 13].

However, these methods are primarily used for reasoning tasks. In multi-agent
decision environments where opponent state information and rewards are
uncertain, traditional heuristic search algorithms are insufficient. BIDDER
extends the application of heuristic search in LLMs by utilizing historical
information to infer hidden opponent information, enabling opponent modeling.
This approach allows for exploration and long-term reward calculation in
multi-agent environments, thus achieving rational decision-making.

###  4.3 Decision-making based on LLM Agents

Recent research on large language models (LLMs) in decision-making [53] has
spanned various multi-agent systems (MAS) including social behavior[56, 19],
economic simulations[55, 22], game theory[10, 46], and game playing[24, 47].
To enhance the strategic reasoning capabilities of LLMs, researchers have
incorporated the concepts of Theory of Mind [13, 16, 54] and Reinforcement
Learning [48, 52]. These approaches aim to prompt LLMs to grasp the
complexities of decision-making tasks.

Although these studies have demonstrated the potential and applications of
LLMs in the decision-making domain, specialized reasoning frameworks designed
for specific tasks face significant challenges when applied to other fields.
Our generalized rational decision-making theory introduces a bi-directional
deliberation reasoning method. Through various experiments, it has been
validated that this approach significantly enhances the benefits gained by
LLMs in decision-making processes.

##  5 Conclusions

As large language models (LLMs) are increasingly applied across various
fields,, BIDDER offers a novel approach to enhance their performance in
complex decision-making environments. By introducing bidirectional reasoning,
BIDDER integrates key concepts from decision science, such as uncertainty
management and expected utility, into the reasoning processes of LLMs. By
leveraging both historical data and potential future rewards, BIDDER
effectively addresses the limitations of traditional unidirectional reasoning
methods. The integration of decision theory principles and bi-directional
modeling ensures a comprehensive exploration of possible states, leading to
more informed and rational decisions. Our experiments in poker and negotiation
scenarios demonstrate that BIDDER significantly improves the decision-making
capabilities of LLMs, aligning their performance more closely with theoretical
optimal solutions. This advancement represents a significant step forward in
the development of LLMs, enabling them to make better decisions in complex,
real-world scenarios.

## References

  * Bacchus et al. [1996] Fahiem Bacchus, Adam J. Grove, Joseph Y. Halpern, and Daphne Koller.  From statistical knowledge bases to degrees of belief.  _Artif. Intell._ , 87:75–143, 1996.
  * Bellman [1966] Richard Bellman.  Dynamic programming.  _science_ , 153(3731):34–37, 1966.
  * Besta et al. [2023] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al.  Graph of thoughts: Solving elaborate problems with large language models.  _arXiv preprint arXiv:2308.09687_ , 2023.
  * Bhakthavatsalam et al. [2021] Sumithra Bhakthavatsalam, Daniel Khashabi, Tushar Khot, Bhavana Dalvi Mishra, Kyle Richardson, Ashish Sabharwal, Carissa Schoenick, Oyvind Tafjord, and Peter Clark.  Think you have solved direct-answer question answering? try arc-da, the direct-answer ai2 reasoning challenge.  _arXiv preprint arXiv:2102.03315_ , 2021.
  * Brown et al. [2019] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm.  Deep counterfactual regret minimization.  In _International conference on machine learning_ , pages 793–802. PMLR, 2019.
  * Cao et al. [2018] Kris Cao, Angeliki Lazaridou, Marc Lanctot, Joel Z Leibo, Karl Tuyls, and Stephen Clark.  Emergent communication through negotiation.  _arXiv preprint arXiv:1804.03980_ , 2018.
  * Chaslot et al. [2008] Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck.  Monte-carlo tree search: A new framework for game ai.  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , volume 4, pages 216–217, 2008.
  * Chen et al. [2023] Xiaoyu Chen, Shenao Zhang, Pushi Zhang, Li Zhao, and Jianyu Chen.  Asking before acting: Gather information in embodied decision making with language models.  _arXiv preprint arXiv:2305.15695_ , 2023.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Duan et al. [2024] Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel-Eskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu.  Gtbench: Uncovering the strategic reasoning limitations of llms via game-theoretic evaluations.  _arXiv preprint arXiv:2402.12348_ , 2024.
  * Feng et al. [2023] Xidong Feng, Ziyu Wan, Muning Wen, Ying Wen, Weinan Zhang, and Jun Wang.  Alphazero-like tree-search can guide large language model decoding and training.  _arXiv preprint arXiv:2309.17179_ , 2023.
  * Fu et al. [2023] Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata.  Improving language model negotiation with self-play and in-context learning from ai feedback.  _arXiv preprint arXiv:2305.10142_ , 2023.
  * Gandhi et al. [2023] Kanishk Gandhi, Dorsa Sadigh, and Noah D Goodman.  Strategic reasoning with language models.  _arXiv preprint arXiv:2305.19165_ , 2023.
  * Gemp et al. [2024] Ian Gemp, Yoram Bachrach, Marc Lanctot, Roma Patel, Vibhavari Dasagi, Luke Marris, Georgios Piliouras, and Karl Tuyls.  States as strings as strategies: Steering language models with game-theoretic solvers.  _arXiv preprint arXiv:2402.01704_ , 2024.
  * Gruver et al. [2023] Nate Gruver, Marc Finzi, Shikai Qiu, and Andrew Gordon Wilson.  Large language models are zero-shot time series forecasters.  In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_ , 2023.
  * Guo et al. [2023] Jiaxian Guo, Bo Yang, Paul Yoo, Bill Yuchen Lin, Yusuke Iwasawa, and Yutaka Matsuo.  Suspicion-agent: Playing imperfect information games with theory of mind aware gpt-4.  _arXiv preprint arXiv:2309.17277_ , 2023.
  * Hao et al. [2023] Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu.  Reasoning with language model is planning with world model.  _arXiv preprint arXiv:2305.14992_ , 2023.
  * Havrilla et al. [2024] Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu.  Teaching large language models to reason with reinforcement learning.  _arXiv preprint arXiv:2403.04642_ , 2024.
  * Hua et al. [2023] Wenyue Hua, Lizhou Fan, Lingyao Li, Kai Mei, Jianchao Ji, Yingqiang Ge, Libby Hemphill, and Yongfeng Zhang.  War and peace (waragent): Large language model-based multi-agent simulation of world wars.  _arXiv preprint arXiv:2311.17227_ , 2023.
  * Kojima et al. [2022] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213, 2022.
  * Lewis et al. [2017] Mike Lewis, Denis Yarats, Yann N. Dauphin, Devi Parikh, and Dhruv Batra.  Deal or no deal? end-to-end learning for negotiation dialogues, 2017.
  * Li et al. [2023] Yang Li, Yangyang Yu, Haohang Li, Zhi Chen, and Khaldoun Khashanah.  Tradinggpt: Multi-agent system with layered memory and distinct characters for enhanced financial trading performance.  _arXiv preprint arXiv:2309.03736_ , 2023.
  * Liu et al. [2024] Xiaoqian Liu, Xingzhou Lou, Jianbin Jiao, and Junge Zhang.  Position: Foundation agents as the paradigm shift for decision making.  _arXiv preprint arXiv:2405.17009_ , 2024.
  * Ma et al. [2023] Weiyu Ma, Qirui Mi, Xue Yan, Yuqiao Wu, Runji Lin, Haifeng Zhang, and Jun Wang.  Large language models play starcraft ii: Benchmarks and a chain of summarization approach.  _arXiv preprint arXiv:2312.11865_ , 2023.
  * Madaan et al. [2023] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al.  Self-refine: Iterative refinement with self-feedback.  _arXiv preprint arXiv:2303.17651_ , 2023.
  * Miao et al. [2021] Shen-Yun Miao, Chao-Chun Liang, and Keh-Yih Su.  A diverse corpus for evaluating and developing english math word problem solvers.  _arXiv preprint arXiv:2106.15772_ , 2021.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Nash Jr [1950] John F Nash Jr.  Equilibrium points in n-person games.  _Proceedings of the national academy of sciences_ , 36(1):48–49, 1950.
  * Naveed et al. [2023] Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Nick Barnes, and Ajmal Mian.  A comprehensive overview of large language models.  _arXiv preprint arXiv:2307.06435_ , 2023.
  * Ning et al. [2023] Xuefei Ning, Zinan Lin, Zixuan Zhou, Huazhong Yang, and Yu Wang.  Skeleton-of-thought: Large language models can do parallel decoding.  _arXiv preprint arXiv:2307.15337_ , 2023.
  * Patel et al. [2021] Arkil Patel, Satwik Bhattamishra, and Navin Goyal.  Are nlp models really able to solve simple math word problems?  _arXiv preprint arXiv:2103.07191_ , 2021.
  * Shinn et al. [2023] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao.  Reflexion: Language agents with verbal reinforcement learning.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Srivastava et al. [2022] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_ , 2022.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Suzgun et al. [2022] Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al.  Challenging big-bench tasks and whether chain-of-thought can solve them.  _arXiv preprint arXiv:2210.09261_ , 2022.
  * Talmor et al. [2022] Alon Talmor, Ori Yoran, Ronan Le Bras, Chandra Bhagavatula, Yoav Goldberg, Yejin Choi, and Jonathan Berant.  Commonsenseqa 2.0: Exposing the limits of ai through gamification.  _arXiv preprint arXiv:2201.05320_ , 2022.
  * Von Neumann and Morgenstern [1947] John Von Neumann and Oskar Morgenstern.  Theory of games and economic behavior, 2nd rev.  1947\.
  * Wang et al. [2024] Chaojie Wang, Yanchen Deng, Zhiyi Lv, Shuicheng Yan, and An Bo.  Q*: Improving multi-step reasoning for llms with deliberative planning.  _arXiv preprint arXiv:2406.14283_ , 2024.
  * Wang et al. [2022] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_ , 2022.
  * Wang et al. [2023] Zhenhailong Wang, Shaoguang Mao, Wenshan Wu, Tao Ge, Furu Wei, and Heng Ji.  Unleashing the emergent cognitive synergy in large language models: A task-solving agent through multi-persona self-collaboration.  _arXiv preprint arXiv:2307.05300_ , 2023.
  * Watkins and Dayan [1992] Christopher JCH Watkins and Peter Dayan.  Q-learning.  _Machine learning_ , 8:279–292, 1992.
  * Wei et al. [2022] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837, 2022.
  * Weng et al. [2022] Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao.  Large language models are better reasoners with self-verification.  _arXiv preprint arXiv:2212.09561_ , 2022.
  * Xie et al. [2022] Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.  An explanation of in-context learning as implicit bayesian inference.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net, 2022.  URL https://openreview.net/forum?id=RdJVFCHjUMI.
  * Xu et al. [2023a] Lin Xu, Zhiyuan Hu, Daquan Zhou, Hongyu Ren, Zhen Dong, Kurt Keutzer, See-Kiong Ng, and Jiashi Feng.  Magic: Investigation of large language model powered multi-agent in cognition, adaptability, rationality and collaboration.  In _ICLR 2024 Workshop on Large Language Model (LLM) Agents_ , 2023a.
  * Xu et al. [2023b] Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu.  Exploring large language models for communication games: An empirical study on werewolf.  _arXiv preprint arXiv:2309.04658_ , 2023b.
  * Xu et al. [2023c] Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu.  Language agents with reinforcement learning for strategic play in the werewolf game.  _arXiv preprint arXiv:2310.18940_ , 2023c.
  * Yao et al. [2023] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of thoughts: Deliberate problem solving with large language models.  _arXiv preprint arXiv:2305.10601_ , 2023.
  * Zha et al. [2020] Daochen Zha, Kwei-Herng Lai, Yuanpu Cao, Songyi Huang, Ruzhe Wei, Junyu Guo, and Xia Hu.  Rlcard: A toolkit for reinforcement learning in card games, 2020.
  * Zhang et al. [2023] Bin Zhang, Hangyu Mao, Jingqing Ruan, Ying Wen, Yang Li, Shao Zhang, Zhiwei Xu, Dapeng Li, Ziyue Li, Rui Zhao, et al.  Controlling large language model-based agents for large-scale decision-making: An actor-critic approach.  _arXiv preprint arXiv:2311.13884_ , 2023.
  * Zhang et al. [2024a] Wenqi Zhang, Ke Tang, Hai Wu, Mengna Wang, Yongliang Shen, Guiyang Hou, Zeqi Tan, Peng Li, Yueting Zhuang, and Weiming Lu.  Agent-pro: Learning to evolve via policy-level reflection and optimization.  _arXiv preprint arXiv:2402.17574_ , 2024a.
  * Zhang et al. [2024b] Yadong Zhang, Shaoguang Mao, Tao Ge, Xun Wang, Adrian de Wynter, Yan Xia, Wenshan Wu, Ting Song, Man Lan, and Furu Wei.  Llm as a mastermind: A survey of strategic reasoning with large language models.  _arXiv preprint arXiv:2404.01230_ , 2024b.
  * Zhang et al. [2024c] Yadong Zhang, Shaoguang Mao, Tao Ge, Xun Wang, Yan Xia, Man Lan, and Furu Wei.  K-level reasoning with large language models.  _arXiv preprint arXiv:2402.01521_ , 2024c.
  * Zhao et al. [2023] Qinlin Zhao, Jindong Wang, Yixuan Zhang, Yiqiao Jin, Kaijie Zhu, Hao Chen, and Xing Xie.  Competeai: Understanding the competition behaviors in large language model-based agents.  _arXiv preprint arXiv:2310.17512_ , 2023.
  * Zhou et al. [2023] Xuhui Zhou, Hao Zhu, Leena Mathur, Ruohong Zhang, Haofei Yu, Zhengyang Qi, Louis-Philippe Morency, Yonatan Bisk, Daniel Fried, Graham Neubig, et al.  Sotopia: Interactive evaluation for social intelligence in language agents.  _arXiv preprint arXiv:2310.11667_ , 2023.
  * Zhuang et al. [2023] Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A Rossi, Somdeb Sarkhel, and Chao Zhang.  Toolchain*: Efficient action space navigation in large language models with a* search.  _arXiv preprint arXiv:2310.13227_ , 2023.
  * Zinkevich et al. [2007] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20, 2007.

##  Appendix A Game Setting

###  A.1 Limit Texas Hold’em

Limit Texas Hold’em is a variant of Texas Hold’em poker where the betting
limits are fixed. The fixed betting structure and sequential decision-making
process create a controlled yet challenging environment for researching agent
decision-making. Its partial observability, and stochastic nature make it
ideal for studying how agents handle uncertainty, strategic planning, and
adversarial competition.

Rules and Gameplay are as following:

  1. 1.

Blinds: - Small Blind and Big Blind are posted before the cards are dealt. \-
The Small Blind is usually half the size of the Big Blind.

  2. 2.

Betting Rounds: \- There are four betting rounds: Pre-Flop, Flop, Turn, and
River. \- Betting amounts are fixed and structured according to the round.

  3. 3.

Dealing: \- Each player is dealt two private cards (hole cards). \- Five
community cards are dealt in stages: the Flop (three cards), the Turn (one
card), and the River (one card).

  4. 4.

Action Spaces: there are four actions, Call, Raise, Fold and Check. In Limit
Texas Hold’em. Each player can only choose a fixed amount of raise. And in
each round the number of raises is limited to four times.

For utilizing LLM as a player, the game setting prompt and the state
description prompt required for each action are as follows:

Game Setting Prompt You are {name} and you are a Texas Hold’em player. Texas
Hold’em is a popular betting game. Each player is dealt two face-down cards,
called hole cards. Then 5 community cards are dealt in three stages (the flop,
the turn and the river). Each player seeks the five best cards among the hole
cards and community cards. In this Texas Hold’em game, there are a total of
{num_players} players namely {players}. The number of chips every player has
is infinite. You just need to win more chips in the competition as much as
possible.

State Prompt The current state is: 1\. The Public Card is {public_card}, and
Your Hand is {hand}. 2\. You have bet {my_bid} chip, and the number of chips
all players have invested is {all_chips}. 3\. After your {pre_action},
{oppoent_actions}. You can choose one of the following actions now: {actions}.

Figure 4: The distribution of hand strengths sampled from poker games ranges
from 0 to 8, corresponding respectively to High Card, One Pair, Two Pair,
Three of a Kind, Straight, Flush, Full House, Four of a Kind, and Straight
Flush.

###  A.2 Negotiation

The "Negotiation" game, as described in Cao et al., is a semi-cooperative
model of agent interaction where communication plays a pivotal role. Here are
the key rules of the Negotiation game:

  1. 1.

Item Pool: Agents are presented with a pool of items, which in the paper’s
example includes three types of items: peppers, cherries, and strawberries.
Each type of item has a quantity associated with it, which is sampled
uniformly for each round of the game.

  2. 2.

Utility Functions: Each agent receives a utility function that specifies the
rewarding value of each item. These utilities are private, meaning that each
agent only knows its own utility values, which are sampled uniformly with at
least one item having non-zero utility.

  3. 3.

Negotiation Rounds: Over a series of negotiation timesteps (N), the agents
take turns to propose how to divide the items in the pool. The number of
turns, N, is sampled between 4 and 10 in each round to prevent a ’first-mover’
advantage.

  4. 4.

Alternating Turns: The agents alternate turns, with one agent (referred to as
Agent A) always acting on odd turns and the other agent (Agent B) on even
turns.

  5. 5.

Proposals and Messages: During each turn, an agent can make a proposal
regarding the division of the items and send a message through a communication
channel. The proposal is a vector indicating the quantity of each item type
that the agent is requesting.

  6. 6.

Termination: Either agent can terminate the negotiation at any timestep with a
special action, which signifies agreement with the most recent proposal made
by the other agent. The negotiation ends, and rewards are distributed based on
the last proposal.

  7. 7.

Rewards: If the negotiation is successfully terminated, the agents receive
rewards based on the dot product of their utility vectors and the items they
receive. If an agent makes an invalid proposal and it is accepted, both agents
receive a reward of zero.

  8. 8.

No Agreement Scenario: If the negotiation reaches the upper limit of allowed
turns without agreement, both agents receive no reward.

The game is designed to study how agents can learn to communicate and
negotiate effectively, with a focus on the emergence of communication
protocols and strategies in a multi-agent reinforcement learning setting.

For utilizing LLM as a player, the game setting prompt and the state
description prompt required for each action are as follows:

Game Setting Prompt You are negotiating the division of Peppers, Strawberries,
and Cherries with the opponent. Different values these items hold for both you
and your opponent. The process is structured into two stages per round: the
proposal stage and the utterance stage. Remember, the key in such negotiations
is understanding that your opponent also has their value system for these
items, which is unknown to you. Balancing between revealing your true desires
and misleading your opponent to gain a favorable outcome is essential. Itś
also important to be adaptive, as the negotiation progresses and you gather
more information about your opponentś preferences and tactics.

Proposals State Prompt Now, you are in the Proposal stage: youĺl determine the
division of items you desire. This is expressed as [a, b, c], where
áŕepresents the quantity of Peppers, b́t́he quantity of Strawberries, and
ćt́he quantity of Cherries you wish to acquire. Itś crucial to base this
division on the perceived value these items have for you, keeping in mind that
the goal is to reach a mutually agreeable solution.

Utterance State Prompt Now, you are in the Utterance Stage: you communicate to
your opponent what you want, again in the format [a, b, c]. This utterance is
your strategic communication and doesnt́ necessarily have to reflect your
actual desires or the proposal you formulated in the first stage. Itś a tool
for negotiation, potentially used to mislead, bluff, or strategically reveal
information to your opponent.

##  Appendix B Reasoning Method Implementation Details

###  B.1 Limit Texas Hold’em

####  B.1.1 Direct

Query Prompt Please provide your results in the form of {’action’: ”}. Just
output the dictionary, don’t use any other text.

####  B.1.2 CoT

Query Prompt Please first think and reason about the current state and then
generate your action as follows: My thought is {Your Thought}, and my action
is {’action’: ”}

####  B.1.3 Reflexion

Query Prompt Please first think and reason about the current state and then
generate your action as follows: My thought is {Your Thought}, and my action
is {’action’: ”}

Reflexion Prompt Please carefully check the thought and the action you just
output , and then refine your answer. The final output is also in the same
format: My revised thought is {Your Thought}. My revised action is {’action:
”}.

####  B.1.4 BIDDER

Hidden State Inference Prompt You are a Poker expert. Based on the public
information provided below, evaluate the relative strength of each player’s
hand. The strongest hand should be rated as 5, and the weakest as 1. Available
History Information: {events} Instructions: 1\. Evaluate the relative strength
of each player’s hand based on the information given. 2\. Consider the
players’ actions and the community cards in your evaluation. 3\. Provide a
rating from 1 to 5, with 5 being the strongest hand and 1 being the weakest
Please provide your evaluation based on the information above. Sample Output
Format: { "Player": { "Rating": <rating> } }

Modeling Prompt You are observing an ongoing poker game. Here are the details:
\- Current community cards: {public_cards} \- Players and their estimated hand
strengths: {hand_strength} The game history so far is as follows: events What
is the most likely action for player when legal actions are: {legal_action}?
The JSON format should look like this: {"action": "<most likely action>"}

Reward Prompt You are observing an ongoing poker game. Here are the details:
\- Current community cards: {public_cards} \- Players and their estimated hand
strengths: {hand_strength} The game history so far is as follows: events
Predict the potential payoff (normalized between 0 and 1) for {player} for
each of the following possible actions and return the results in JSON format:
{action_payoff_template}

###  B.2 Negotiation

For the LLM reasoning baselines in the Negotiation game (including Direct,
CoT, and ToT), we utilize the implementation provided by Duan et
al.444https://github.com/jinhaoduan/GTBench.

####  B.2.1 BIDDER

Hidden State Inference Prompt {state} Based on the public information provided
below, infer the value of each item to your opponent. Opponent behavior:
{events} Item Pool: {item_pool_prompt} Instructions: 1\. Consider the players’
historical actions in your evaluation. 2\. The value is between 1 and 10.
Please provide your evaluation based on the information above. Output Format:
Evaluation: Peppers: <value> Strawberries: <value> Cherries: <value>

Reward Prompt You are negotiating the division of Peppers, Strawberries, and
Cherries with the opponent. Different values these items hold for both you and
your opponent. The process is structured into two stages per round: the
proposal stage and the utterance stage. Now, you are in the Utterance Stage:
you communicate to your opponent what you want, again in the format [a, b, c].
This utterance is your strategic communication and doesn’t necessarily have to
reflect your actual desires or the proposal you formulated in the first stage.
It’s a tool for negotiation, potentially used to mislead, bluff, or
strategically reveal information to your opponent. {item_pool_prompt}
{value_vector} {last_utterance_prompt} The opponent’s evaluation of the value
of each item is: Opponent Value Inference: {infered_values} Instructions: 1\.
Propose the two Utterances with the largest rewards. This also includes
agreeing if you agree with your opponent’s utterance. Each utterance format
is: "<Utterance: [a, b, c]>" (including "<" and ">"). 2\. Calculate the Payoff
for each Utterance (a number); calculate the probability (normalized between 0
and 1) of the opponent agreeing with this utterance, it is necessary to
consider the degree of satisfaction the opponent has with the utterance.
Sample Output Format: Utterances: { "Utterance": "<utterance>", "Payoff":
"<payoff>", "Probability": "<probability>" }, { "Utterance": "<utterance>",
"Payoff": "<payoff>", "Probability": "<probability>" }

##  Appendix C Algorithm Detail of BIDDER

Algorithm 1 Explore $(\mathcal{T},t)$: Exploration with Opponent Modeling

0: $s_{t}$: Current decision context; $I$: Inferred hidden information about
opponent; $T$: Time-step of exploration;

0: $\mathcal{T}(s_{t})$: The traces of exploration.

1: if $t=T$ or $s_{t}$ is terminal node then

2: return $\\{\tau\\}$

3: end if

4: $\mathcal{T}=\emptyset$

5: for each legal action $a_{t}$ of $s_{t}$ do

6: $s_{t+1}\leftarrow s_{t}\times a_{t}\times$ Opponent_Modeling($I$, $\tau$)

7: $\mathcal{T}\leftarrow\mathcal{T}\cup$
Explore$(\tau\cup\\{a_{t},s_{t+1}\\},t+1)$

8: end for

9: return $\mathcal{T}$

Algorithm 2 Rewards Aggregation with Attenuation Coefficient

0: $\mathcal{T}$: Explored trajectories; $A$: The set of valid actions;
$\beta$: Attenuation Coefficient;

0: $G(A)$: The maximum payoff of each action.

1: for each $a\in A$ do

2: $G(a)\leftarrow 0$

3: for each trajectory $\tau\in\mathcal{T}$ do

4: if $\tau$ starts with action $a$ then

5: $G(\tau)\leftarrow\sum_{k=0}^{T}\beta^{i}\cdot\tau[k]$

6: if $G(\tau)>G(a)$ then

7: $G(a)\leftarrow G(\tau)$

8: end if

9: end if

10: end for

11: end for

12:

13: return $\\{G(a)\mid a\in A\\}$


white  listing  #1#2#3

# Handling Long-Tail Queries with Slice-Aware Conversational Systems

Cheng Wang, Sun Kim, Taiwoo Park, Sajal Choudhary
Amazon Alexa AI
{cwngam, kimzs, parktaiw<EMAIL_ADDRESS>
Sunghyun Park, Young-Bum Kim, Ruhi Sarikaya, Sungjin Lee
Amazon Alexa AI
{sunghyu, youngbum, rsarikay<EMAIL_ADDRESS>

###### Abstract

We have been witnessing the usefulness of conversational AI systems such as
Siri and Alexa, directly impacting our daily lives. These systems normally
rely on machine learning models evolving over time to provide quality user
experience. However, the development and improvement of the models are
challenging because they need to support both high (head) and low (tail) usage
scenarios, requiring fine-grained modeling strategies for specific data
subsets or slices. In this paper, we explore the recent concept of slice-based
learning (SBL) (Chen et al., 2019) to improve our baseline conversational
skill routing system on the tail yet critical query traffic. We first define a
set of labeling functions to generate weak supervision data for the tail
intents. We then extend the baseline model towards a slice-aware architecture,
which monitors and improves the model performance on the selected tail
intents. Applied to de-identified live traffic from a commercial
conversational AI system, our experiments show that the slice-aware model is
beneficial in improving model performance for the tail intents while
maintaining the overall performance.

##  1 Introduction

Conversational AI systems such as Google Assistant, Amazon Alexa, Apple Siri
and Microsoft Cortana have become more prevalent in recent years (Sarikaya,
2017). One of the key techniques in those systems is to employ machine
learning (ML) models to route a user’s spoken utterance to the most
appropriate skill that can fulfill the request. This requires the models to
first capture the semantic meaning of the request, which typically involves
assigning the utterance query to the candidate domain, intent, and slots (El-
Kahky et al., 2014). For example, “Play Frozen” can be interpreted with Music
as the domain, Play Music as the intent, and Album Name:Frozen as the slot key
and value. Then, the models can route the request to a specific skill, which
is an application that actually executes to deliver an experience (Li et al.,
2021). For commercial conversational AI systems, there usually exists a large-
scale dataset of user requests with ground-truth semantic interpretations and
skills (e.g., through manual annotations and hand-crafted rules or
heuristics). Along with various contextual signals, it is possible to train ML
models (e.g., deep neural networks) with high predictive accuracy in routing a
user request to the most appropriate skill, which then can continue to
optimize towards better user experience through implicit or explicit user
feedback (Park et al., 2020).

Nevertheless, developing such ML models or improving existing ones towards
better user experience is still challenging. One hurdle is the imbalance in
the distribution of the user queries with a long tail in terms of traffic
volume. This often makes it difficult for the ML models to learn the patterns
from the long-tail queries, some of which could be for critical features.
Several approaches have been proposed to address such imbalance issue (Smith
et al., 2014; He et al., 2008; Chawla et al., 2002). However, they are mainly
based on applying reverse-discriminative sampling strategies, for example,
over-sampling minority and/or under-sampling majority. The sampling methods
are usually insufficient in inspecting and improving model performance on pre-
defined data subgroups.

In this work, we focus on the problem of imbalanced queries, specifically on
tail but critical intents, in the context of the recently proposed slice-based
learning (SBL) (Chen et al., 2019). SBL is a novel programming model that sits
on top of ML systems. The approach first inspects particular data subsets
(Ratner et al., 2019), which are called slices, and it improves the ML model
performance on those slices. While the capability of monitoring specific
slices is added to a pre-trained ML model (which is termed the backbone
model), the approach has shown that overall performance across the whole
traffic is comparable to those without SBL. Motivated by this idea, we propose
to adopt the SBL concept to our baseline skill routing approach (we term the
baseline model as $\mathbf{P}$; please refer to Sec. 3.1 for details) to
improve its performance on tail yet critical intent queries while keeping the
overall performance intact. First, we define slice functions (i.e., labeling
functions) to specify the intents that we want to monitor. A pre-trained
$\mathbf{P}$ is used as a backbone model for extracting the representation for
each query. Then, we extend $\mathbf{P}$ to a slice-aware architecture, which
learns to attend to the tail intent slices of interest.

We perform two experiments using a large-scale dataset with de-identified
customer queries. First, we examine the attention mechanism in the extended
model $\mathbf{P}$ with SBL. In particular, we test two attention weight
functions with different temperature parameters in computing the probability
distribution over tail intent slices. Second, we compare SBL to an upsampling
method in $\mathbf{P}$ for handling tail intents. Our experiments demonstrate
that SBL is able to effectively improve the ML model performance on tail
intent slices as compared to the upsampling approach, while maintaining the
overall performance.

We describe the related work in Section 2. In Section 3, we explain the
baseline skill routing model, $\mathbf{P}$, and then elaborate how to extend
it to a slice-aware architecture. The experiment results are reported in
Section 4, and in Section 5, we discuss the advantages and potential
limitations of applying SBL in our use case. We conclude this work in Section
6.

##  2 Related Work

###  2.1 Slice-Based Learning

Slice-based learning (SBL) (Chen et al., 2019) is a novel programming model
that is proposed to improve ML models on critical data slices without hurting
overall performance. A core idea of SBL is to represent a sample differently
depending on the data subset or slice to which it belongs. It defines and
leverages slice functions, i.e., pre-defined labeling functions, to generate
weak supervision data for learning slice-aware representations. For instance,
in computer vision (CV) applications, a developer can define object detection
functions to detect whether an image contains a bicycle or not. In natural
language understanding (NLP) applications, a developer can define intent-
specific labeling functions such as for Play Music intent. SBL exhibits better
performance than a mixture of experts (Jacobs et al., 1991) and multi-task
learning (Caruana, 1997), with reduced run-time cost and parameters (Chen et
al., 2019). Recently Gustavo et al. (Penha & Hauff, 2020) have employed the
concept of SBL to understand failures of ranking models and identify difficult
instances in order to improve ranking performance. Our work applies the idea
to improve skill routing performance on low traffic but critical intents in
conversational AI systems.

###  2.2 Weakly Supervised Learning

Weakly supervised learning attempts to learn predictive models with noisy and
weak supervision data. Typically, there are three types of weak supervision:
incomplete supervision, inexact supervision, and inaccurate supervision (Zhou,
2018). Various weakly supervised ML models are developed in NLP (Medlock &
Briscoe, 2007; Huang et al., 2014; Wang & Manning, 2014) and in CV (Prest et
al., 2011; Oquab et al., 2015; Peyre et al., 2017). Recently, promising
approaches have been proposed to generate weak supervision data by programming
training data (Ratner et al., 2016). In a large-scale industry setting, weak
supervision data are highly desired given that human annotations are costly
and time-consuming. Our work relates to weakly supervised learning in terms of
inaccurate supervision. We split queries into different groups (slices) by
defining labeling functions (slice functions). Each group is assigned with a
group identity label. In practice, the slice functions may not perfectly
assign labels to input data as mentioned in SBL (Chen et al., 2019; Cabannnes
et al., 2020).

###  2.3 Conversational Skill Routing Models

In conversational AI systems, a skill refers to the application that actually
executes on a user query or request to deliver an experience, such as playing
a song or answering a question. The skills often comprise both first-party and
third-party applications (Li et al., 2021). The skill routing is a mechanism
that maps users’ queries, given contextual information such as semantic
interpretations and device types, to an appropriate application. The routing
decision is usually determined by an ML model that is separate from typical
natural language understanding (NLU) models for domain, intent, slot parsing.
Please refer to section 3.1 for more details.

##  3 Slice-Aware Conversational Skill Routing Models

This section explains our skill routing model (backbone model) and then
explains how we extend the backbone model to a slice-aware architecture by
adapting the concept from SBL (Chen et al., 2019).

(a)  Figure 1:  The slice-aware conversational skill routing model
architecture for handling low traffic but critical intents. It consists of six
components: (1) slice functions define tail intent slices that we want to
monitor; (2) backbone model is our pre-trained skill routing model
$\mathbf{P}$ that is used for feature extraction; (3) slice indicators are
membership functions to predict if a sample query belongs to a tail slice; (4)
slice experts aim to learn slice-specific representations; (5) shared head is
the base task predictive layer across experts; (6) An attention module is used
to re-weight the slice-specific representations $\mathbf{r}$ and form a slice-
aware representation $\mathbf{s}$. Finally, the learned $\mathbf{s}$ is used
to predict a final hypothesis (associated skill). The predicted hypothesis is
used to serve a user query.

###  3.1 Backbone Model

We take our baseline skill routing approach ($\mathbf{P}$) as the backbone
model and aim to make it a slice-aware architecture. $\mathbf{P}$ is a skill
routing model, which takes in a list of routing candidates to select the most
appropriate one. Each routing candidate is represented as a hypothesis with
various contextual signals, such as utterance text, device type, semantic
interpretation, and associated skill. While some contextual signals are common
across all hypotheses, some are unique due to the presence of multiple
competing semantic interpretations and skill-specific context. The core
component of $\mathbf{P}$ consists of attention-based bi-directional LSTMs
(Hochreiter & Schmidhuber, 1997; Graves & Schmidhuber, 2005) with fully
connected layers on top of it. Formally, Let $X$ be the set of query signals
(e.g., utterance text, semantic interpretations, device type, etc.),
$H=\\{h_{1},...,h_{n}\\}$ be the hypothesis list and $h_{g}\in H,g=[1,n]$ be
the ground-truth hypothesis. The learning objective is to minimize the binary
cross entropy:

$\zeta_{base}=\mathcal{L}_{bce}(\pi(\mathcal{M}(X,H)),h_{g}),$ (1)

where $\pi$ is a linear predictive layer which outputs a prediction over
hypotheses $\hat{H}=\\{\hat{h}_{1},...,\hat{h}_{n}\\}$, and $\mathcal{M}$ is a
set of multiple neural network layers, which extract the representation
$\mathbf{x}\in\mathbb{R}^{n\times d}$ for a given ($X,H$) pair, i.e.,
$\mathbf{x}=\mathcal{M}(X,H)$.

To evaluate the effectiveness of trained $\mathbf{P}$, we define offline
evaluation metric called replication accuracy (RA):

$RA(\mathcal{D}_{test})=\sum\nolimits_{(X,H,h_{g})\in\mathcal{D}_{test}}\frac{\mathbb{I}(\hat{h}_{g}=h_{g})}{|\mathcal{D}_{test}|}.$
(2)

The replication accuracy measures how effectively the trained model
$\mathbf{P}$ replicates the current skill routing behavior in production which
is a combination of ML model and rules. Though $\mathbf{P}$ achieves high
performance, replicating most of heuristic patterns, it suffers from low RA in
low-volume traffic, i.e., the tail user queries. We later introduce how we
extend $\mathbf{P}$ with a slice-aware component.

###  3.2 Slice-Aware Architecture

As presented in Figure 1, a slice-aware architecture consists of several
components.

Slice Function. We first define slice (or labeling) functions to slice user
queries according to intent (e.g., “Buy Book”). The selected intents have a
small number of query instances, making the model $\mathbf{P}$ difficult to
learn data patterns from tail intents. Each sample is assigned a slice label
$\gamma\in[0,1]$ in $\\{\gamma_{1},\gamma_{2},...,\gamma_{k}\\}$ for
supervision. $s_{1}$ is the base slice, and $s_{2}$ to $s_{k}$ are the tail
slices.

⬇ def intent_based_slice_function_1(sample): return sample[’intent’] == "Buy
Item" def intent_based_slice_function_2(sample): return sample[’intent’] ==
"Select Music" def intent_based_slice_function_3(sample): return
sample[’intent’] == "Buy Book"
---
Table 1: The slice functions (SFs) which split user queries into multiple data
slices according to the pre-defined tail intents. The non-tail intents are in
a base slice. Note SFs are only available at training stage for generating
weak supervision labels. At inference stage, SFs will not be applied.

Slice Indicator. For each tail intent slice, a slice indicator (membership
function) is learned to indicate whether a sample belongs to this particular
slice or not. For a given representation $\mathbf{x}\in\mathbb{R}^{n\times d}$
from the backbone model, we learn
$u_{i}=f_{i}(\mathbf{x};\mathbf{w}^{f}_{i})$,
$\mathbf{w}^{f}_{i}\in\mathcal{R}^{d\times 1}$, $i\in\\{1,..,k\\}$ that maps
$\mathbf{x}$ to $\mathbf{u}=\\{u_{1},...,u_{k}\\}$. $f_{i}$ is trained with
$\\{\mathbf{x},\gamma\\}$ pairs with the binary cross entropy
$\zeta_{ind}=\sum_{i}^{k}\mathcal{L}_{bce}(\mathbf{u}_{i},\gamma_{i})$.

Slice Expert. For each tail intent slice, a slice expert
$g_{i}(\mathbf{x};\mathbf{w}^{g}_{i})$,
$\mathbf{w}^{g}_{i}\in\mathcal{R}^{d\times d}$ is used to learn a mapping from
$\mathbf{x}\in\mathbb{R}^{n\times d}$ to a slice vector
$r_{i}\in\mathcal{R}^{d}$ with the samples only belonging to the tail slice.
Followed by a shared head, which is shared across all experts and maps $r_{i}$
to a prediction $\hat{h}=\varphi(r_{i};\mathbf{w}_{s})$, $g_{i}$ and $\varphi$
are learned on the base (original) task with ground-truth label $h_{g}$ by
$\zeta_{exp}=\sum_{i}^{k}\gamma_{i}\mathcal{L}_{bce}(\hat{h},h_{g})$.

Attention Module. The attention module decides how to pay special attention to
the monitored slices. The distribution over slices (or attention weights) are
computed based on stacked $k$ membership likelihood $P\in\mathbb{R}^{k}$ and
stacked $k$ experts’ prediction confidence $Q\in\mathbb{R}^{k\times c}$ as
described in (Chen et al., 2019):

$a2=\textsc{softmax}(P+\left|Q\right|).$ (3)

Note, the above equation is used when $c=1$ (i.e., binary classification). As
our task is a multi-class classification task where $c\geq 2$, we use an
additional linear layer to transform $Q\in\mathbb{R}^{k\times c}$ to
$\phi(Q)\in\mathbb{R}^{k}$. Finally, we experiment with the following
different ways to compute attention weights, i.e., slice distribution:

$\displaystyle a1=\textsc{softmax}(P/\tau)$ (4) $\displaystyle
a2=\textsc{softmax}([P+\left|\phi(Q)\right|]/\tau).$ (5)

In Eq. 4, we only use the output of the indicator function (membership
likelihood) in computing attention weights. In Eq. 5 we use both the
membership likelihood and the transformed experts’ prediction scores. The
$\tau$ is a temperature parameter. In principle, smaller $\tau$ can lead to a
more confident slice distribution (Wang & Niepert, 2019; Wang et al., 2021),
hence we aim to examine if a small $\tau$ helps improve the routing
performance.

##  4 Experiments

We evaluate the skill routing model $\mathbf{P}$ with slice-based learning
(SBL) (Chen et al., 2019) (we term it as $\mathbf{S}$) by performing two
groups of experiments. First, we test the attention module with different
methods of computing the attention weights over slices. Second, we compare the
effectiveness of SBL against upsampling – a commonly used method for handling
tail data.

###  4.1 Experiment Setup and Implementation Details

We obtained live traffic from a commercial conversational AI system in
production and processed the data so that individual users are not
identifiable. We randomly sampled to create an adequately large data set for
each training and test dataset. We further split the training set into
training and validation sets with a ratio of 9:1. We used the replication
accuracy (Eq. 2) to measure the model performance.

The existing production model $\mathbf{P}$ and its extension with SBL were
implemented with Pytorch (Paszke et al., 2019). The hidden unit size for slice
component was 128. All models were trained on AWS p3.8xlarge instances with
Intel Xeon E5-2686 CPUs, 244 GB memory, and 4 NVIDIA Tesla V100 GPUs. We used
Adam (Kingma & Ba, 2014) with a learning rate of 0.001 as the optimizer. Each
model was trained with 10 epochs with the batch size of 256. We split the user
queries into 21 data slices in total, one base slice and the rest for 20 tail
intent slices. For each extracted query representation $\mathbf{x}$ for the
tail intents, we add a Gaussian noise
$\mathbf{x}=\mathbf{x}+\delta,~{}\delta\sim\mathcal{N}(0,0.005)$ to augment
the tail queries.

###  4.2 Experiments on the Attention Mechanisms

Table 2 shows the absolute score difference in replication accuracy between
the baseline model and its SBL extension, having the baseline model’s all-
intent accuracy as a reference. As shown in the table, the slice-based
approaches maintain the baseline performance overall, but the RA performance
is lifted on the monitored tail slices. The best attention mechanism
outperforms the baseline by 0.1% in tail intents’ replication accuracy111Given
the large volume of query traffic per day, 0.1% is still a significant
improvement in our system.. Tuning the temperature parameter between
$\tau=0.1$ or $\tau=1.0$ does not significantly improve model performance on
the tail intents.

Attention Methods | All Intents (%) | Tail Intents (%)
---|---|---
$\mathbf{P}$ (baseline model) |  $>$99 | –1.45
SBL, Eq. (4), $\tau=1.0$ | +0.01 | –1.35
SBL, Eq. (5), $\tau=1.0$ | +0.01 | –1.36
SBL, Eq. (4), $\tau=0.1$ | +0.01 | –1.34
SBL, Eq. (5), $\tau=0.1$ | +0.01 | –1.38
Table 2: The performance comparison of the baseline model $\mathbf{P}$ and its
SBL extension with different attention weights in replication accuracy. All
data points denote the absolute difference from the baseline model’s all
intents accuracy value.

###  4.3 Comparison between Slice-Based Learning and Upsampling

As upsampling is a widely used method to alleviate the tail data problem, we
compare the performance between SBL and upsampling methods. Note SBL offers an
additional advantage for inspecting particular tail data groups which are also
critical. We denote the models as the following:

  * •

$\mathbf{P}$ is the baseline model that is trained without applying
upsampling.

  * •

$\mathbf{S}$ is an extension of $\mathbf{P}$ (as a backbone model) to be a
slice-aware model, which is trained with same training set as $\mathbf{P}$.

  * •

$\mathbf{P}_{up}$ is the baseline model that is trained with applying
upsampling.

  * •

$\mathbf{S}_{up}$ is an extension of $\mathbf{P}_{up}$ to be a slice-aware
model, which is trained with same training set as $\mathbf{P}_{up}$.

All the trained models are evaluated on the same test set. Among the
aforementioned attention method choices, Eq. 4 with $\tau=1.0$ is employed for
$\mathbf{S}$ and $\mathbf{S}_{up}$. Our primary goal is to see whether
$\mathbf{S}$ can improve $\mathbf{P}_{up}$.

Table 3 shows the performance comparison. When comparing $\mathbf{P}_{up}$ and
$\mathbf{S}$, we can see $\mathbf{S}$ achieves slightly better performance for
all intents. For the monitored tail intents, $\mathbf{S}$ achieves a slightly
higher score as compared to $\mathbf{P}_{up}$.

Models | All Intents (%) | Tail Intents (%)
---|---|---
$\mathbf{P}$ |  $>$99 | –1.41
$\mathbf{P}_{up}$ | 0.00 | –1.47
$\mathbf{S}$ | +0.01 | –1.30
$\mathbf{S}_{up}$ | +0.01 | –1.37
Table 3: Performance comparison between the baseline model and its slice-aware
architecture. $\mathbf{P}$ is the baseline model without upsampling,
$\mathbf{P}_{up}$ is $\mathbf{P}$ with upsampling. $\mathbf{S}$ is the slice
learning model with $\mathbf{P}$ as the backbone model, and $\mathbf{S}_{up}$
is the slice learning model with $\mathbf{P}_{up}$ as the backbone model. All
data points are absolute score difference from the baseline model’s all intent
accuracy value.

Table 4 presents the absolute RA difference between the baseline and slice-
aware models for the monitored 20 tail intents. Comparing $\mathbf{S}$ and
$\mathbf{P}_{up}$, $\mathbf{S}$ improves the model performance on 14 tail
intents. Compared to $\mathbf{P}_{up}$, $\mathbf{S}$ shows the comparable
performance lift while effectively suppressing performance drops, for example,
intent IDs 2, 3, 6, 15, and 20. As a result, $\mathbf{P}_{up}$ shows lower
performance on 12 intents out of 20 (–2.41% on average), while $\mathbf{S}$
did on only 5 intents (–0.21% on average). This suggests the capability of
slice-based learning in treating target intents through the slice-aware
representation.

Tail Intent ID | $\mathbf{P}$ | $\mathbf{P}_{up}$ | $\mathbf{S}$ | $\mathbf{S}_{up}$ | Sample Size
---|---|---|---|---|---
1 |  $>$99 | –0.03 | 0.00 | –0.02 | Over 10K
2 |  $>$96 | –0.4 | +0.04 | –0.21 | Over 10K
3 |  $>$96 | –0.19 | +0.09 | –0.18 | Over 10K
4 |  $>$72 | +0.07 | +1.98 | +0.96 | Over 10K
5 |  $>$99 | +0.01 | –0.01 | 0.00 | Over 10K
6 |  $>$96 | –0.09 | +0.02 | –0.11 | Over 10K
7 |  $>$96 | +0.03 | +0.02 | –0.04 | Over 10K
8 |  $>$99 | +0.15 | +0.01 | +0.19 | Over 10K
9 |  $>$96 | –0.24 | +0.06 | +0.07 | Over 10K
10 |  $>$96 | +0.08 | –0.03 | 0.00 | Between 1K - 10K
11 |  $>$99 | 0.00 | 0.00 | 0.00 | Between 1K - 10K
12 |  $>$96 | +0.55 | –0.13 | +0.46 | Between 1K - 10K
13 |  $>$96 | +0.36 | +0.42 | +0.53 | Between 1K - 10K
14 |  $>$93 | –0.39 | –0.14 | –0.42 | Between 1K - 10K
15 |  $>$93 | –3.29 | –0.73 | –1.46 | Between 1K - 10K
16 |  $>$96 | –1.2 | 0.00 | –0.93 | Below 1K
17 |  $>$96 | –0.71 | 0.00 | –0.71 | Below 1K
18 |  $>$99 | –0.16 | 0.00 | –0.16 | Below 1K
19 |  $>$99 | –0.96 | 0.00 | –1.15 | Below 1K
20 |  $>$96 | –21.21 | 0.00 | –18.18 | Below 1K
Table 4: Score (in %) differences in RA between the baseline and slice-aware
approaches at the intent level. The baseline model’s accuracy scores are
rounded down to the nearest multiple of 3 percent, while the other models’ are
absolute score differences from the baseline ones. We denote each intent with
their IDs. Sample Size is the number of random instances used for testing.

##  5 Discussion

In our experiments, we have shown the effectiveness of SBL in terms of
improving model performance on tail intent slices. It is beneficial to have ML
models which are slice-aware, particularly when we want to inspect some
specific and critical but low-traffic instances. Although the overall
performance gain of slice-aware approach compared to the upsampling was
marginal, it is worthwhile to note that the slice-aware approach was able to
lift up the replication accuracy for more number of tail intents while
minimizing unexpected performance degradation that was more noticeable in the
upsampling approach. This result implies that the slice-aware approach has
more potential in stably and evenly supporting tail intents.

On the other hand, we also note a potential limitation of SBL in the case of
addressing tail intents in the industry setting. As we increase the number of
tail intents, for instance to 200 intents, the model’s complexity increases as
well, given that an indicator function and an expert head are needed for each
slice. However, this does not necessarily diminish the value of the slice-
aware architecture, as the upsampling method offers no chance for us to
inspect and analyze model failures on particular slices. Further studies are
necessary to employ and fine-tune the slice-based approach to serve tail
traffic in a cost-effective way.

##  6 Conclusion

In this work, we applied and implemented the concept of slice-based learning
to our skill routing model for a large-scale commercial conversational AI
system. To enable the existing model to pay extra attention to selected tail
intents, we tested different ways of computing slice distribution by using
membership likelihood and experts’ prediction confidence scores. Our
experiments show that the slice-based learning can effectively and evenly
improve model performance on tail intents while maintaining overall
performance. We also compared the slice learning method against upsampling in
terms of handling tail intents. The results suggest that slice-based learning
outperforms upsampling by a small margin, while more evenly uplifting tail
intents’ performance. A potential future work would be to explore how to adapt
SBL to monitor a large number of slices with minimum model and runtime
complexity.

## References

  * Cabannnes et al. (2020) Vivien Cabannnes, Alessandro Rudi, and Francis Bach.  Structured prediction with partial labelling through the infimum loss.  In _International Conference on Machine Learning_ , pp. 1230–1239. PMLR, 2020.
  * Caruana (1997) Rich Caruana.  Multitask learning.  _Machine learning_ , 28(1):41–75, 1997.
  * Chawla et al. (2002) Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer.  Smote: synthetic minority over-sampling technique.  _Journal of artificial intelligence research_ , 16:321–357, 2002.
  * Chen et al. (2019) Vincent Chen, Sen Wu, Alexander J Ratner, Jen Weng, and Christopher Ré.  Slice-based learning: A programming model for residual learning in critical data slices.  In _Advances in neural information processing systems_ , pp. 9397–9407, 2019.
  * El-Kahky et al. (2014) Ali El-Kahky, Xiaohu Liu, Ruhi Sarikaya, Gokhan Tur, Dilek Hakkani-Tur, and Larry Heck.  Extending domain coverage of language understanding systems via intent transfer between domains using knowledge graphs and search query click logs.  In _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 4067–4071. IEEE, 2014.
  * Graves & Schmidhuber (2005) Alex Graves and Jürgen Schmidhuber.  Framewise phoneme classification with bidirectional lstm and other neural network architectures.  _Neural networks_ , 18(5-6):602–610, 2005.
  * He et al. (2008) Haibo He, Yang Bai, Edwardo A Garcia, and Shutao Li.  Adasyn: Adaptive synthetic sampling approach for imbalanced learning.  In _2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelligence)_ , pp. 1322–1328. IEEE, 2008\.
  * Hochreiter & Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Huang et al. (2014) Fei Huang, Arun Ahuja, Doug Downey, Yi Yang, Yuhong Guo, and Alexander Yates.  Learning representations for weakly supervised natural language processing tasks.  _Computational Linguistics_ , 40(1):85–120, 2014\.
  * Jacobs et al. (1991) Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton.  Adaptive mixtures of local experts.  _Neural computation_ , 3(1):79–87, 1991.
  * Kingma & Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Li et al. (2021) Han Li, Sunghyun Park, Aswarth Dara, Jinseok Nam, Sungjin Lee, Young-Bum Kim, Spyros Matsoukas, and Ruhi Sarikaya.  Neural model robustness for skill routing in large-scale conversational ai systems: A design choice exploration.  _arXiv preprint arXiv:2103.03373_ , 2021.
  * Medlock & Briscoe (2007) Ben Medlock and Ted Briscoe.  Weakly supervised learning for hedge classification in scientific literature.  In _Proceedings of the 45th annual meeting of the association of computational linguistics_ , pp. 992–999, 2007.
  * Oquab et al. (2015) Maxime Oquab, Léon Bottou, Ivan Laptev, and Josef Sivic.  Is object localization for free?-weakly-supervised learning with convolutional neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 685–694, 2015.
  * Park et al. (2020) Sunghyun Park, Han Li, Ameen Patel, Sidharth Mudgal, Sungjin Lee, Young-Bum Kim, Spyros Matsoukas, and Ruhi Sarikaya.  A scalable framework for learning from implicit user feedback to improve natural language understanding in large-scale conversational ai systems.  _arXiv preprint arXiv:2010.12251_ , 2020.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Penha & Hauff (2020) Gustavo Penha and Claudia Hauff.  Slice-aware neural ranking.  In _Proceedings of the 5th International Workshop on Search-Oriented Conversational AI (SCAI)_ , pp. 1–6, 2020.
  * Peyre et al. (2017) Julia Peyre, Josef Sivic, Ivan Laptev, and Cordelia Schmid.  Weakly-supervised learning of visual relations.  In _Proceedings of the ieee international conference on computer vision_ , pp. 5179–5188, 2017.
  * Prest et al. (2011) Alessandro Prest, Cordelia Schmid, and Vittorio Ferrari.  Weakly supervised learning of interactions between humans and objects.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 34(3):601–614, 2011.
  * Ratner et al. (2016) Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré.  Data programming: Creating large training sets, quickly.  _Advances in neural information processing systems_ , 29:3567–3575, 2016.
  * Ratner et al. (2019) Alexander J Ratner, Braden Hancock, and Christopher Ré.  The role of massively multi-task and weak supervision in software 2.0.  In _CIDR_ , 2019.
  * Sarikaya (2017) Ruhi Sarikaya.  The technology behind personal digital assistants: An overview of the system architecture and key components.  _IEEE Signal Processing Magazine_ , 34(1):67–81, 2017.
  * Smith et al. (2014) Michael R Smith, Tony Martinez, and Christophe Giraud-Carrier.  An instance level analysis of data complexity.  _Machine learning_ , 95(2):225–256, 2014.
  * Wang & Niepert (2019) Cheng Wang and Mathias Niepert.  State-regularized recurrent neural networks.  In _International Conference on Machine Learning_ , pp. 6596–6606. PMLR, 2019.
  * Wang et al. (2021) Cheng Wang, Carolin Lawrence, and Mathias Niepert.  Uncertainty estimation and calibration with finite-state probabilistic {rnn}s.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=9EKHN1jOlA.
  * Wang & Manning (2014) Mengqiu Wang and Christopher D Manning.  Cross-lingual projected expectation regularization for weakly supervised learning.  _Transactions of the Association for Computational Linguistics_ , 2:55–66, 2014.
  * Zhou (2018) Zhi-Hua Zhou.  A brief introduction to weakly supervised learning.  _National science review_ , 5(1):44–53, 2018\.