Author name cluster

Fang Kong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

1 author row

TCS Journal 2026 Journal Article

Bandit learning in matching markets with relative feedback

Fang Kong
Xiaoxi Zhang
Xiao Huang
Lijun Zhang
Shuai Li

The two-sided matching market problem has been extensively studied in the literature. How to find a stable matching is a key focus in the field. A significant body of recent work considers scenarios where one side of the market (players) has uncertain preferences and learns them through the absolute rewards obtained during repeated interactions with the other side (arms). A common assumption in these works is that arms deterministically resolve conflicts when faced with multiple players. However, in practical applications, the arms’ selection process may also be stochastic due to fluctuations in players’ performances. Under such circumstances, it becomes challenging for players to observe absolute rewards that quantify the arms’ satisfaction. Instead, the relative feedback about which applicant wins in a competition is often more realistic. In this paper, we investigate the pure exploration problem for bandit learning in matching markets where players need to additionally learn the uncertain preferences of arms based on more practical relative feedback. We show that given confidence level δ ∈ (0, 1), the market can reach the player-optimal stable matching in at most O ( max { N, K } log ( 1 / δ ) / Δ 2 + N K log ( 1 / δ ) / ϵ 2 ) rounds with probability at least 1 − δ, where N, K correspond to market size, ϵ represents arms’ relative preference gap, and Δ corresponds to the players’ preference gap. We also conduct experiments to verify the performances of the proposed algorithms.

Details DOI

AAAI Conference 2026 Conference Paper

Evaluating, Synthesizing, and Enhancing for Customer Support Conversation

Jie Zhu
Huaixia Dou
Junhui Li
Lifan Guo
Feng Chen
Chi Zhang
Fang Kong

Effective customer support requires not only accurate problem-solving but also structured and empathetic communication aligned with professional standards. However, existing dialogue datasets often lack strategic guidance, and real-world service data is difficult to access and annotate. To address this, we introduce the task of Customer Support Conversation (CSC), aimed at training customer service supporters to respond using well-defined support strategies. We propose a structured CSC framework grounded in COPC guidelines, defining five conversational stages and twelve strategies to guide high-quality interactions. Based on this, we construct CSConv, an evaluation dataset of 1,855 real-world customer–agent conversations rewritten using LLMs to reflect deliberate strategy use, and annotated accordingly. Additionally, we develop a role-playing approach that simulates strategy-rich conversations using LLM-powered roles aligned with the CSC framework, resulting in the training dataset RoleCS. Experiments show that fine-tuning strong LLMs on RoleCS significantly improves their ability to generate high-quality, strategy-aligned responses on CSConv. Human evaluations further confirm gains in problem resolution.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Online Multi-LLM Selection via Contextual Bandits Under Unstructured Context Evolution

Manhin Poon
Xiangxiang Dai
Xutong Liu
Fang Kong
John C.S. Lui
Jinhang Zuo

Large language models (LLMs) exhibit diverse response behaviors, costs, and strengths, making it challenging to select the most suitable LLM for a given user query. We study the problem of adaptive multi-LLM selection in an online setting, where the learner interacts with users through multi-step query refinement and must choose LLMs sequentially without access to offline datasets or model internals. A key challenge arises from unstructured context evolution: the prompt dynamically changes in response to previous model outputs via a black-box process, which cannot be simulated, modeled, or learned. To address this, we propose the first contextual bandit framework for sequential LLM selection under unstructured prompt dynamics. We formalize a notion of myopic regret and develop a LinUCB-based algorithm that provably achieves sublinear regret without relying on future context prediction. We further introduce budget-aware and positionally-aware (favoring early-stage satisfaction) extensions to accommodate variable query costs and user preferences for early high-quality responses. Our algorithms are theoretically grounded and require no offline fine-tuning or dataset-specific training. Experiments on diverse benchmarks demonstrate that our methods outperform existing LLM routing strategies in both accuracy and cost-efficiency, validating the power of contextual bandits for real-time, adaptive LLM selection.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Simulating Human-Like Counseling: A Path- and Scenario-Guided Framework for Psychological Support Dialogue

Yuanchen Shi
Longyin Zhang
Maodong Li
Yibin Zheng
Xiuhong Wang
Fang Kong

The growing demand for psychological support underscores the lack of high-quality counseling dialogue datasets, particularly in non-English contexts. We propose PGSim, a Path-Guided Simulation framework that mirrors real counseling processes—symptom description, problem identification, cause analysis, strategy planning, and iterative adjustment. PGSim models each user scenario as a fine-grained quadruple {Group, Psychological Problem, Problem Cause, Support Focus} and guides dialogue generation through expert-annotated strategy paths. Real counseling dialogues and expert-edited samples are used to fine-tune two language models: a Dialog Generator for strategy-aligned dialogue creation and a Dialog Modifier for expert-level refinement. After automated and human verification, we construct the Chinese Psychological support Dialogue Dataset (CPsDD), containing 68K dialogues across 13 groups, 16 problems, 13 causes, and 12 support focuses. We further present the Comprehensive Agent Dialogue Support System (CADSS), which integrates profiling, summarization, strategy planning, and empathetic response. Experiments on CPsDD and ESConv demonstrate that CADSS achieves state-of-the-art results on Strategy Prediction and Emotional Support Conversation tasks.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

A Survey on Bandit Learning in Matching Markets

Shuai Li
Zilong Wang
Fang Kong

The two-sided matching market problem has attracted extensive research in both computer science and economics due to its wide-ranging applications in multiple fields. In various online matching platforms, market participants often have unclear preferences. As a result, a growing area of research focuses on the online scenario. Here, one-side participants (players) gradually figure out their unknown preferences through multiple rounds of interactions with the other-side participants (arms). This survey comprehensively reviews and systematically organizes the abundant literature on bandit learning in matching markets. It covers not only existing theoretical achievements but also various other related aspects. Based on the current research, several distinct directions for future study have emerged. We are convinced that delving deeper into these directions could potentially yield theoretical algorithms that are more suitable for real-world situations.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Learning Across the Gap: Hybrid Multi-armed Bandits with Heterogeneous Offline and Online Data

Qijia He
Minghan Wang
Xutong Liu
Zhiyong Wang
Fang Kong

The multi-armed bandit (MAB) is a fundamental online decision-making framework that has been extensively studied over the past two decades. To mitigate the high cost and slow convergence of purely online learning, modern MAB approaches have explored hybrid paradigms that leverage offline data to warm-start online learning. However, existing approaches face a significant limitation by assuming that the offline and online data are homogeneous—they share the same feedback structure and are drawn from the same underlying distribution. This assumption is often violated in practice, where offline data often originate from diverse sources and evolving environments, resulting in feedback heterogeneity and distributional shifts. In this work, we tackle the challenge of learning across this offline-online gap by developing a general hybrid bandit framework that incorporates heterogeneous offline data to improve online performance. We study two hybrid settings: (1) using reward-based offline data to accelerate online learning in preference-based bandits (i. e. , dueling bandits), and (2) using preference-based offline data to improve online standard MAB algorithms. For both settings, we design novel algorithms and derive tight regret bounds that match or improve upon existing benchmarks despite heterogeneity. Empirical evaluations on both synthetic and real-world datasets show that our proposed methods significantly outperform baseline algorithms.

PDF Details

NeurIPS Conference 2024 Conference Paper

Improved Analysis for Bandit Learning in Matching Markets

Fang Kong
Zilong Wang
Shuai Li

A rich line of works study the bandit learning problem in two-sided matching markets, where one side of market participants (players) are uncertain about their preferences and hope to find a stable matching during iterative matchings with the other side (arms). The state-of-the-art analysis shows that the player-optimal stable regret is of order $O(K\log T/\Delta^2)$ where $K$ is the number of arms, $T$ is the horizon and $\Delta$ is the players' minimum preference gap. However, this result may be far from the lower bound $\Omega(\max\{N\log T/\Delta^2, K\log T/\Delta\})$ since the number $K$ of arms (workers, publisher slots) may be much larger than that $N$ of players (employers in labor markets, advertisers in online advertising, respectively). In this paper, we propose a new algorithm and show that the regret can be upper bounded by $O(N^2\log T/\Delta^2 + K \log T/\Delta)$. This result removes the dependence on $K$ in the main order term and improves the state-of-the-art guarantee in common cases where $N$ is much smaller than $K$. Such an advantage is also verified in experiments. In addition, we provide a refined analysis for the existing centralized UCB algorithm and show that, under $\alpha$-condition, it achieves an improved $O(N \log T/\Delta^2 + K \log T / \Delta)$ regret.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility

Fang Kong
Shuai Li

Two-sided matching markets have been widely studied in the literature due to their rich applications. Since participants are usually uncertain about their preferences, online algorithms have recently been adopted to learn them through iterative interactions. An existing work initiates the study of this problem in a many-to-one setting with responsiveness. However, their results are far from optimal and lack guarantees of incentive compatibility. We first extend an existing algorithm for the one-to-one setting to this more general setting and show it achieves a near-optimal bound for player-optimal regret. Nevertheless, due to the substantial requirement for collaboration, a single player's deviation could lead to a huge increase in its own cumulative rewards and a linear regret for others. In this paper, we aim to enhance the regret bound in many-to-one markets while ensuring incentive compatibility. We first propose the adaptively explore-then-deferred-acceptance (AETDA) algorithm for responsiveness setting and derive an upper bound for player-optimal stable regret while demonstrating its guarantee of incentive compatibility. This result is a significant improvement over existing works. And to the best of our knowledge, it constitutes the first player-optimal guarantee in matching markets that offers such robust assurances. We also consider broader substitutable preferences, one of the most general conditions to ensure the existence of a stable matching and cover responsiveness. We devise an online DA (ODA) algorithm and establish an upper bound for the player-pessimal stable regret for this setting.

PDF Details DOI

TMLR Journal 2024 Journal Article

Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization

Fang Kong
Xiangcheng Zhang
Baoxiang Wang
Shuai Li

Learning Markov decision processes (MDP) in an adversarial environment has been a challenging problem. The problem becomes even more challenging with function approximation since the underlying structure of the loss function and transition kernel are especially hard to estimate in a varying environment. In fact, the state-of-the-art results for linear adversarial MDP achieve a regret of $\tilde{\mathcal{O}}({K^{6/7}})$ ($K$ denotes the number of episodes), which admits a large room for improvement. In this paper, we propose a novel explore-exploit algorithm framework and investigate the problem with a new view, which reduces linear MDP into linear optimization by subtly setting the feature maps of the bandit arms of linear optimization. This new technique, under an exploratory assumption, yields an improved bound of $\tilde{\mathcal{O}}({K^{4/5}})$ for linear adversarial MDP without access to a transition simulator. The new view could be of independent interest for solving other MDP problems that possess a linear structure.

PDF Details

AAMAS Conference 2023 Conference Paper

Online Influence Maximization under Decreasing Cascade Model

Fang Kong
Jize Xie
Baoxiang Wang
Tao Yao
Shuai Li

We study online influence maximization (OIM) under a new model of decreasing cascade (DC). This model is a generalization of the independent cascade (IC) model by considering the common phenomenon of market saturation. In DC, the chance of an influence attempt being successful reduces with previous failures. The effect is neglected by previous OIM works under IC and linear threshold models. We propose the DC-UCB algorithm to solve this problem, which achieves a regret bound of the same order as the state-of-theart works on the IC model. Extensive experiments on both synthetic and real datasets show the effectiveness of our algorithm.

PDF

IJCAI Conference 2022 Conference Paper

Thompson Sampling for Bandit Learning in Matching Markets

Fang Kong
Junming Yin
Shuai Li

The problem of two-sided matching markets has a wide range of real-world applications and has been extensively studied in the literature. A line of recent works have focused on the problem setting where the preferences of one-side market participants are unknown a priori and are learned by iteratively interacting with the other side of participants. All these works are based on explore-then-commit (ETC) and upper confidence bound (UCB) algorithms, two common strategies in multi-armed bandits (MAB). Thompson sampling (TS) is another popular approach, which attracts lots of attention due to its easier implementation and better empirical performances. In many problems, even when UCB and ETC-type algorithms have already been analyzed, researchers are still trying to study TS for its benefits. However, the convergence analysis of TS is much more challenging and remains open in many problem settings. In this paper, we provide the first regret analysis for TS in the new setting of iterative matching markets. Extensive experiments demonstrate the practical advantages of the TS-type algorithm over the ETC and UCB-type baselines.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Towards Discourse-Aware Document-Level Neural Machine Translation

Xin Tan
Longyin Zhang
Fang Kong
Guodong Zhou

Current document-level neural machine translation (NMT) systems have achieved remarkable progress with document context. Nevertheless, discourse information that has been proven effective in many NLP tasks is ignored in most previous work. In this work, we aim at incorporating the coherence information hidden within the RST-style discourse structure into machine translation. To achieve it, we propose a document-level NMT system enhanced with the discourse-aware document context, which is named Disco2NMT. Specifically, Disco2NMT models document context based on the discourse dependency structures through a hierarchical architecture. We first convert the RST tree of an article into a dependency structure and then build the graph convolutional network (GCN) upon the segmented EDUs under the guidance of RST dependencies to capture the discourse-aware context for NMT incorporation. We conduct experiments on the document-level English-German and English-Chinese translation tasks with three domains (TED, News, and Europarl). Experimental results show that our Disco2NMT model significantly surpasses both context-agnostic and context-aware baseline systems on multiple evaluation indicators.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Hierarchical Macro Discourse Parsing Based on Topic Segmentation

Feng Jiang
Yaxin Fan
Xiaomin Chu
Peifeng Li
Qiaoming Zhu
Fang Kong

Hierarchically constructing micro (i. e. , intra-sentence or inter-sentence) discourse structure trees using explicit boundaries (e. g. , sentence and paragraph boundaries) has been proved to be an effective strategy. However, it is difficult to apply this strategy to document-level macro (i. e. , interparagraph) discourse parsing, the more challenging task, due to the lack of explicit boundaries at the higher level. To alleviate this issue, we introduce a topic segmentation mechanism to detect implicit topic boundaries and then help the document-level macro discourse parser to construct better discourse trees hierarchically. In particular, our parser first splits a document into several sections using the topic boundaries that the topic segmentation detects. Then it builds a smaller and more accurate discourse sub-tree in each section and sequentially forms a whole tree for a document. The experimental results on both Chinese MCDTB and English RST-DT show that our proposed method outperforms the state-of-the-art baselines significantly.

PDF Details

NeurIPS Conference 2021 Conference Paper

The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle

Fang Kong
Yueran Yang
Wei Chen
Shuai Li

Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example \cite{WangC18} has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problem-dependent regret lower bound of order $\Omega(\log T/\Delta^2)$ to quantify the hardness of TS to solve CMAB problems with greedy oracle, where $T$ is the time horizon and $\Delta$ is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.

PDF Details

NeurIPS Conference 2020 Conference Paper

Online Influence Maximization under Linear Threshold Model

Shuai Li
Fang Kong
Kejie Tang
Qizhi Li
Wei Chen

Online influence maximization (OIM) is a popular problem in social networks to learn influence propagation model parameters and maximize the influence spread at the same time. Most previous studies focus on the independent cascade (IC) model under the edge-level feedback. In this paper, we address OIM in the linear threshold (LT) model. Because node activations in the LT model are due to the aggregated effect of all active neighbors, it is more natural to model OIM with the nodel-level feedback. And this brings new challenge in online learning since we only observe aggregated effect from groups of nodes and the groups are also random. Based on the linear structure in node activations, we incorporate ideas from linear bandits and design an algorithm $\ltlinucb$ that is consistent with the observed feedback. By proving group observation modulated (GOM) bounded smoothness property, a novel result of the influence difference in terms of the random observations, we provide a regret of order $\tilde{O}(\mathrm{poly}(m)\sqrt{T})$, where $m$ is the number of edges and $T$ is the number of rounds. This is the first theoretical result in such order for OIM under the LT model. In the end, we also provide an algorithm $\oimetc$ with regret bound $O(\mathrm{poly}(m)\ T^{2/3})$, which is model-independent, simple and has less requirement on online feedback and offline computation.

PDF Details

IJCAI Conference 2019 Conference Paper

Incorporating Structural Information for Better Coreference Resolution

Fang Kong
Fu Jian

Coreference resolution plays an important role in text understanding. In the literature, various neural approaches have been proposed and achieved considerable success. However, structural information, which has been proven useful in coreference resolution, has been largely ignored in previous neural approaches. In this paper, we focus on effectively incorporating structural information to neural coreference resolution from three aspects. Firstly, nodes in the parse trees are employed as a constraint to filter out impossible text spans (i. e. , mention candidates) in reducing the computational complexity. Secondly, contextual information is encoded in the traversal node sequence instead of the word sequence to better capture hierarchical information for text span representation. Lastly, additional structural features (e. g. , the path, siblings, degrees, category of the current node) are encoded to enhance the mention representation. Experimentation on the data-set of the CoNLL 2012 Shared Task shows the effectiveness of our proposed approach in incorporating structural information into neural coreference resolution.

PDF Details

IJCAI Conference 2013 Conference Paper

A Clause-Level Hybrid Approach to Chinese Empty Element Recovery

Fang Kong
Guodong Zhou

Empty elements (EEs) play a critical role in Chinese syntactic, semantic and discourse analysis. Previous studies employ a language-independent sentence-level approach to EE recovery, by casting it as a linear tagging or structured parsing problem. In comparison, this paper proposes a clauselevel hybrid approach to address specific problems in Chinese EE recovery, which recovers EEs in Chinese language from the clause perspective and integrates the advantages of both linear tagging and structured parsing. In particular, a comma disambiguation method is employed to improve syntactic parsing and help determine clauses in Chinese. In this way, the noise introduced by sentencelevel syntactic parsing and multiple EEs in the same position of a linear sentence can be well addressed. Evaluation on Chinese Treebank 6. 0 shows the significant performance improvement of our clause-level hybrid approach over the state-ofthe-art sentence-level baselines, and its great impact on a state-of-the-art Chinese syntactic parser.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Improve Tree Kernel-Based Event Pronoun Resolution with Competitive Information

Fang Kong
Guodong Zhou

Event anaphora resolution plays a critical role in discourse analysis. This paper proposes a tree kernel-based framework for event pronoun resolution. In particular, a new tree expansion scheme is introduced to automatically determine a proper parse tree structure for event pronoun resolution by considering various kinds of competitive information related with the anaphor and the antecedent candidate. Evaluation on the OntoNotes English corpus shows the appropriateness of the tree kernel-based framework and the effectiveness of competitive information for event pronoun resolution.

PDF Details DOI