TNCOA: Efficient Exploration via Observation-Action Constraint on Trajectory-Based Intrinsic Reward

Abstract

Efficient exploration is critical in handling sparse rewards and partial observability in deep reinforcement learning. However, most existing intrinsic reward methods based on novelty rely on single-step observations or Euclidean distances. These approaches struggle to capture trajectory-level novelty and often perform poorly in partially observable settings. Moreover, they typically ignore the role of actions in driving observation changes, as not all actions lead to meaningful state transitions. To overcome these limitations, we propose a trajectory-level novelty measure that estimates the novelty of a state by comparing current observations with past ones along the trajectory. To focus on meaningful exploration, we incorporate the mutual information between actions and trajectory novelty to filter out random fluctuations and retain only novelty caused by the agent's actions. Additionally, we introduce a first-visit constraint on observation–action pairs, rewarding only interactions that result in state transitions to enhance exploration efficiency. We conducted experiments in the MiniGrid-ObstructedMaze environment characterised by complex object interactions and sparse rewards. Results demonstrate that our method achieves state-of-the-art performance in convergence speed and average returns. Furthermore, it shows strong generalisation on high-dimensional Atari benchmarks and demonstrates robust performance in more challenging MiniGrid variants. Implementation code is available at: https://github.com/MurrayMa0816/TNCOA.

Keywords

artificial intelligence / decision making / intelligent systems / machine learning

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (General Program, Grant 62473052) and the InnoHK initiative under the Innovation and Technology Commission (ITC) of the Hong Kong SAR Government. This work was supported by the National Key Laboratory (Grant 241-HF-D09-01).

Ethics Statement

The authors have nothing to report.

Consent

The authors have nothing to report.

Conflicts of Interest

The authors declare no conflicts of interest.

Data Availability Statement

The implementation code is publicly available in an anonymous GitHub repository: https://github.com/MurrayMa0816/TNCOA.

Permission to Reproduce Material From Other Sources

The authors have nothing to report.

References

[1] G. Schoettler, A. Nair, J. Luo, et al., Deep Reinforcement Learning for Industrial Insertion Tasks With Visual Inputs and Natural Rewards,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2020), 5548-5555.

[2] Y. Yang, L. Juntao, and P. Lingling, “Multi-Robot Path Planning Based on a Deep Reinforcement Learning DQN Algorithm,” CAAI Transactions on Intelligence Technology 5, no. 3 (2020): 177-183, https://doi.org/10.1049/trit.2020.0024.

[3] R. Chitnis, S. Tulsiani, S. Gupta, and A. Gupta, “Efficient Bimanual Manipulation Using Learned Task Schemas,” in IEEE International Conference on Robotics and Automation (ICRA) (2020), 1149-1155.

[4] S. Feng, H. Sun, X. Yan, et al., Dense Reinforcement Learning for Safety Validation of Autonomous Vehicles,” Nature 615, no. 7953 (2023): 620-627, https://doi.org/10.1038/s41586-023-05732-2.

[5] J. Zhang, K. Wang, and C. Mu, “Multi-Station Multi-Robot Task Assignment Method Based on Deep Reinforcement Learning,” CAAI Transactions on Intelligence Technology 10, no. 1 (2025): 134-146, https://doi.org/10.1049/cit2.12394.

[6] B. Kang, Z. Jie, and J. Feng, “Policy Optimization With Demonstrations,” in Proceedings of the 35th International Conference on Machine Learning (ICML) (2018), 2469-2478.

[7] S. Narvekar, B. Peng, M. Leonetti, J. Sinapov, M. E. Taylor, and P. Stone, “Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey,” Journal of Machine Learning Research 21, no. 181 (2020): 1-50, https://doi.org/10.48550/arXiv.2003.04960.

[8] Q. Zou, K. Xiong, Q. Fang, and B. Jiang, “Deep Imitation Reinforcement Learning for Self-Driving by Vision,” CAAI Transactions on Intelligence Technology 6, no. 4 (2021): 493-503, https://doi.org/10.1049/cit2.12025.

[9] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, “Concrete Problems in AI Safety,” arXiv preprint arXiv:1606.06565 (2016).

[10] R. S. Sutton and A. G. Barto , Reinforcement Learning: An Introduction (MIT Press, 2018).

[11] D. J. Russo, B. Van Roy, A. Kazerouni, et al. , “A Tutorial on Thompson Sampling,” Foundations and Trends® in Machine Learning 11, no. 1 (2018): 1-96, https://doi.org/10.1561/2200000070.

[12] J. Hao, T. Yang, H. Tang, et al., Exploration in Deep Reinforcement Learning: From Single-Agent to Multi-Agent Domain,” IEEE Transactions on Neural Networks and Learning Systems 35, no. 7 (2024): 8762-8782, https://doi.org/10.1109/tnnls.2023.3236361.

[13] Y. Guo, J. Choi, M. Moczulski, et al., Memory Based Trajectory-Conditioned Policies for Learning From Sparse Rewards,” in Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS, 2020), 11834-11847.

[14] R. Gieselmann and F. T. Pokorny, “Expansive Latent Planning for Sparse Reward Offline Reinforcement Learning,” in Proceedings of the 7th Conference on Robot Learning (CoRL) (2023), 1-22.

[15] S. Parisi, A. Kazemipour, and M. Bowling, “Beyond Optimism: Exploration With Partially Observable Rewards,” in Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS) (2024).

[16] J. Zhang, W. Zhang, D. Zhou, and Q. Gu, “Uncertainty-Aware Reward-Free Exploration With General Function Approximation,” in Proceedings of the 41st International Conference on Machine Learning (ICML) (2024), 60414-60445.

[17] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, “Curiosity-Driven Exploration by Self-Supervised Prediction,” in Proceedings of the 34th International Conference on Machine Learning (ICML) (2017), 2778-2787.

[18] Y. Burda, H. Edwards, A. Storkey, and O. Klimov, “Exploration by Random Network Distillation,” in Proceedings of the 7th International Conference on Learning Representations (ICLR) (2019).

[19] R. Raileanu and T. Rocktäschel , “Ride: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments,” in Proceedings of the 8th International Conference on Learning Representations (ICLR) (2020).

[20] Y. Flet-Berliac, J. Ferret, O. Pietquin, P. Preux, and M. Geist, “Adversarially Guided Actor-Critic,” in Proceedings of the 9th International Conference on Learning Representations (ICLR) (2021).

[21] M. Yuan, B. Li, X. Jin, and W. Zeng, “Rewarding Episodic Visitation Discrepancy for Exploration in Reinforcement Learning,” in Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS) (2022).

[22] S. Wan, Y. Tang, Y. Tian, and T. Kaneko, “DEIR: Efficient and Robust Exploration Through Discriminative-Model-Based Episodic Intrinsic Rewards,” in Proceedings of the 39th International Joint Conference on Artificial Intelligence (IJCAI) (2023), 4289-4298.

[23] H. Ma, F. Li, J. Y. Lim, Z. Luo, T. V. Vo, and T.-Y. Leong, “Catching Two Birds With One Stone: Reward Shaping With Dual Random Networks for Balancing Exploration and Exploitation,” in Proceedings of the 42nd International Conference on Machine Learning (ICML) (2025), 4582-4590.

[24] S. Mahankali, Z.-W. Hong, A. Sekhari, A. Rakhlin, and P. Agrawal, “Random Latent Exploration for Deep Reinforcement Learning,” in Proceedings of the 41st International Conference on Machine Learning (ICML) (2024), 34219-34252.

[25] Y. Wang, K. Zhao, and F. Liu, “Rethinking Exploration in Reinforcement Learning With Effective Metric-Based Exploration Bonus,” in Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS) (2024).

[26] T. Zhang, H. Xu, X. Wang, et al., NovelD: A Simple yet Effective Exploration Criterion,” in Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS) (2021), 25217-25230.

[27] H. Tang, R. Houthooft, D. Foote, et al., # Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning,” in Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS) (2017), 1081-1091.

[28] J. Fu, J. D. Co-Reyes, and S. Levine, “EX2: Exploration With Exemplar Models for Deep Reinforcement Learning,” in Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS) (2017), 1070-1080.

[29] J. Choi, Y. Guo, M. Moczulski, et al., Contingency-Aware Exploration in Reinforcement Learning,” in Proceedings of the 6th International Conference on Learning Representations (ICLR) (2018).

[30] A. P. Badia, P. Sprechmann, A. Vitvitskyi, et al., Never Give Up: Learning Directed Exploration Strategies,” in Proceedings of the 7th International Conference on Learning Representations (ICLR) (2019).

[31] A. Trott, S. Zheng, C. Xiong, and R. Socher, “Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewards,” in Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS) (2019).

[32] M. Chevalier-Boisvert, L. Willems, and S. Pal , Minimalistic Grid World Environment for Openai Gym (2018), https://github.com/maximecb/gym-minigrid.

[33] Y. Fu, R. Peng, and H. Lee, “Go Beyond Imagination: Maximizing Episodic Reachability With World Models,” in Proceedings of the 40th International Conference on Machine Learning (ICML) (2023), 10405-10420.

[34] Z. Wu, H. Lu, J. Xing, et al., PAE: Reinforcement Learning From External Knowledge for Efficient Exploration,” in Proceedings of the 12th International Conference on Learning Representations (ICLR) (2024).

[35] A. Zhu, P.-F. Zhang, R. Qiu, Z. Zheng, Z. Huang, and J. Shao, “Abstract and Explore: A Novel Behavioral Metric With Cyclic Dynamics in Reinforcement Learning,” in Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) (2024), 17150-17158.

[36] A. L. Strehl and M. L. Littman, “An Analysis of Model-Based Interval Estimation for Markov Decision Processes,” Journal of Computer and System Sciences 74, no. 8 (2008): 1309-1331, https://doi.org/10.1016/j.jcss.2007.08.009.

[37] M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos, “Unifying Count-Based Exploration and Intrinsic Motivation,” in Proceedings of the 30th Conference on Neural Information Processing Systems (NeurIPS) (2016), 2845-2853.

[38] G. Ostrovski, M. G. Bellemare, A. van den Oord, and R. Munos, “Count-Based Exploration With Neural Density Models,” in Proceedings of the 34th International Conference on Machine Learning (ICML) (2017), 2721-2730.

[39] M. Seurin, F. Strub, P. Preux, and O. Pietquin, “Don’t Do What Doesn’t Matter: Intrinsic Motivation With Action Usefulness,” in Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) (2021), 2950-2956.

[40] Y. Wang, M. Yang, R. Dong, et al., Efficient Potential-Based Exploration in Reinforcement Learning Using Inverse Dynamic Bisimulation Metric,” in Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS) (2023).

[41] D. Jo, S. Kim, D. W. Nam, et al., LECO: Learnable Episodic Count for Task-Specific Intrinsic Reward,” in Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS) (2022), 30432-30445.

[42] S. Ross, J. Pineau, S. Paquet, and B. Chaib-Draa, “Online Planning Algorithms for POMDPs,” Journal of Artificial Intelligence Research 32 (2008): 663-704, https://doi.org/10.1613/jair.2567.

[43] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms,” arXiv preprint arXiv:1707.06347 (2017).

[44] T. Zhang, P. Rashidinejad, J. Jiao, Y. Tian, J. E. Gonzalez, and S. Russell, “MADE: Exploration via Maximizing Deviation From Explored Regions,” in Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS) (2021).

[45] M. Yuan, B. Li, X. Jin, and W. Zeng, “Automatic Intrinsic Reward Shaping for Exploration in Deep Reinforcement Learning,” in Proceedings of the 40th International Conference on Machine Learning (ICML) (2023), 40531-40554.