Graph representation based reward shaping approach for addressing reward sparsity in task-oriented dialogue systems

Task-Oriented Dialogue (TOD) systems rely on sequential decision-making to assist users in accomplishing specific goals. Due to this sequential nature, Reinforcement Learning (RL) has been widely adopted to train dialogue systems. However, reward sparsity remains a fundamental challenge in RL-based TOD systems, leading to inefficient exploration and suboptimal policy learning. While prior studies have focused on adopting advanced RL techniques to train TOD agents, the design of an effective reward function has received less attention. To address this challenge, this paper proposes a novel Potential-Based Reward Shaping (PBRS) approach that integrates graph representation learning with spectral graph clustering. This approach leverages graph representation learning algorithms to capture both structural and semantic relationships between dialogue states, facilitating more effective reward propagation. Moreover, the integration of Minimum Cut Pooling (MinCutPool) enables adaptive soft clustering, which promotes generalization across large and dynamic state spaces and remains robust to unseen or isolated states caused by frequent task switching or goal resetting. Extensive experiments were conducted to assess the effectiveness of the proposed approach on three benchmark tasks collected via Amazon Mechanical Turk. Evaluation metrics in this paper include success rate, average reward, dialogue turns, inference latency, number of parameters, CPU training time, and maximum CPU memory. Specifically, on the movie ticket booking task, the proposed GAT+MinCut+CSR model achieved 93.00 %, 28.14, 7.14, 96 ms, 80,143, 19982 s, and 7 GB, respectively, demonstrating superior performance and computational efficiency compared to state-of-the-art baselines.