2025-11-24T20:25:17.007327

ReZero: Boosting MCTS-based Algorithms by Backward-view and Entire-buffer Reanalyze

Xuan, Niu, Pu et al.
Monte Carlo Tree Search (MCTS)-based algorithms, such as MuZero and its derivatives, have achieved widespread success in various decision-making domains. These algorithms employ the reanalyze process to enhance sample efficiency from stale data, albeit at the expense of significant wall-clock time consumption. To address this issue, we propose a general approach named ReZero to boost tree search operations for MCTS-based algorithms. Specifically, drawing inspiration from the one-armed bandit model, we reanalyze training samples through a backward-view reuse technique which uses the value estimation of a certain child node to save the corresponding sub-tree search time. To further adapt to this design, we periodically reanalyze the entire buffer instead of frequently reanalyzing the mini-batch. The synergy of these two designs can significantly reduce the search cost and meanwhile guarantee or even improve performance, simplifying both data collecting and reanalyzing. Experiments conducted on Atari environments, DMControl suites and board games demonstrate that ReZero substantially improves training speed while maintaining high sample efficiency. The code is available as part of the LightZero MCTS benchmark at https://github.com/opendilab/LightZero.
academic

ReZero: पश्चदृश्य और संपूर्ण-बफर पुनर्विश्लेषण द्वारा MCTS-आधारित एल्गोरिदम को बढ़ावा देना

मूल जानकारी

  • पेपर ID: 2404.16364
  • शीर्षक: ReZero: पश्चदृश्य और संपूर्ण-बफर पुनर्विश्लेषण द्वारा MCTS-आधारित एल्गोरिदम को बढ़ावा देना
  • लेखक: Chunyu Xuan, Yazhe Niu, Yuan Pu, Shuai Hu, Yu Liu, Jing Yang
  • वर्गीकरण: cs.AI
  • प्रकाशन तिथि: 31 दिसंबर 2024 (arXiv नवीनतम संस्करण)
  • पेपर लिंक: https://arxiv.org/abs/2404.16364

सारांश

मोंटे कार्लो ट्री सर्च (MCTS) पर आधारित एल्गोरिदम, जैसे MuZero और इसके व्युत्पन्न एल्गोरिदम, विभिन्न निर्णय क्षेत्रों में व्यापक सफलता प्राप्त की है। ये एल्गोरिदम पुरानी डेटा की नमूना दक्षता में सुधार के लिए पुनर्विश्लेषण प्रक्रिया का उपयोग करते हैं, लेकिन इसकी कीमत महत्वपूर्ण घड़ी समय की खपत है। इस समस्या को हल करने के लिए, यह पेपर MCTS एल्गोरिदम के ट्री सर्च ऑपरेशन को तेज करने के लिए ReZero नामक एक सामान्य विधि प्रस्तावित करता है। विशेष रूप से, एकल-सशस्त्र बैंडिट मॉडल से प्रेरित होकर, पश्चदृश्य पुनः उपयोग तकनीक के माध्यम से प्रशिक्षण नमूनों का पुनर्विश्लेषण किया जाता है, विशिष्ट उप-नोड्स के मूल्य अनुमान का उपयोग करके संबंधित उप-वृक्षों की खोज समय को बचाया जाता है। इस डिज़ाइन के अनुकूल होने के लिए, छोटे बैच के बजाय संपूर्ण बफर का आवधिक पुनर्विश्लेषण करने की रणनीति अपनाई जाती है। इन दोनों डिज़ाइनों का सहक्रियात्मक प्रभाव खोज लागत को काफी हद तक कम करता है, जबकि प्रदर्शन को सुनिश्चित करता है और यहां तक कि सुधार करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

MCTS एल्गोरिदम को मजबूत शिक्षा में सामना करने वाली मुख्य समस्या अत्यधिक घड़ी समय की खपत है, जो दो पहलुओं में प्रकट होती है:

  1. डेटा संग्रह चरण: एजेंट को हर बार नई स्थिति प्राप्त करने पर कार्रवाई चुनने के लिए MCTS निष्पादित करना पड़ता है
  2. पुनर्विश्लेषण चरण: उच्च गुणवत्ता के अपडेट लक्ष्य प्राप्त करने के लिए, नवीनतम मॉडल के साथ MCTS को फिर से चलाना आवश्यक है

समस्या की महत्ता

  • MCTS एल्गोरिदम नमूना दक्षता के मामले में उत्कृष्ट प्रदर्शन करते हैं, लेकिन समय दक्षता इसके आगे के प्रसार के लिए एक बाधा बन गई है
  • ट्री सर्च गणना सामान्य वेक्टरकृत वातावरण का उपयोग करके समानांतर नहीं की जा सकती, जो गति की कमजोरी को और बढ़ाती है
  • मौजूदा त्वरण विधियों को या तो अतिरिक्त कम्प्यूटेशनल संसाधनों की आवश्यकता है (जैसे SpeedyZero), या खोज स्थान को संपीड़ित करने के लिए स्थिति अमूर्तता का उपयोग करते हैं (जैसे PTSAZero)

अनुसंधान प्रेरणा

यह पेपर मौजूदा विधियों के लिए एक ऑर्थोगोनल त्वरण रणनीति प्रस्तावित करना चाहता है, जिसे न तो स्थिति स्थान संपीड़न की आवश्यकता है और न ही अतिरिक्त हार्डवेयर ओवरहेड का परिचय देता है, बल्कि मूल्य अनुमान के माध्यम से सीधे खोज स्थान को कम करता है।

मुख्य योगदान

  1. पश्चदृश्य पुनर्विश्लेषण तकनीक प्रस्तावित की: एकल-सशस्त्र बैंडिट मॉडल से प्रेरित विधि का उपयोग करके एकल ट्री सर्च को तेज करना, और अभिसरण के लिए सैद्धांतिक गारंटी प्रदान करना
  2. संपूर्ण बफर पुनर्विश्लेषण ढांचा डिज़ाइन किया: MCTS कॉल की संख्या को और कम करना और समानांतरकरण क्षमता को बढ़ाना
  3. सामान्य ढांचा: विभिन्न MCTS एल्गोरिदम में निर्बाध रूप से एकीकृत किया जा सकता है, अतिरिक्त कम्प्यूटेशनल संसाधनों की आवश्यकता नहीं है
  4. व्यापक प्रायोगिक सत्यापन: Atari वातावरण, DMControl सूट और बोर्ड गेम में विधि की प्रभावशीलता को सत्यापित किया गया है

विधि विवरण

कार्य परिभाषा

यह पेपर MCTS एल्गोरिदम की नमूना दक्षता को बनाए रखते हुए इसकी घड़ी समय की खपत को काफी हद तक कम करने का तरीका खोजता है। इनपुट MCTS एल्गोरिदम के प्रक्षेपवक्र डेटा हैं, आउटपुट त्वरित खोज नीति और मूल्य अनुमान हैं।

मुख्य विधि आर्किटेक्चर

1. पश्चदृश्य पुनर्विश्लेषण (Backward-view Reanalyze)

सैद्धांतिक आधार: एकल-सशस्त्र बैंडिट मॉडल से प्रेरित होकर, ट्री सर्च के रूट नोड को बैंडिट के रूप में माना जाता है, प्रत्येक चाइल्ड नोड एक आर्म के रूप में कार्य करता है। यदि किसी चाइल्ड नोड का वास्तविक स्थिति मूल्य पहले से ज्ञात हो, तो उसकी खोज समय को बचाया जा सकता है।

विशिष्ट कार्यान्वयन:

आसन्न समय चरणों S^t_l और S^{t+1}_l के लिए:
- जब S^{t+1}_l की खोज करते हैं, रूट नोड मूल्य m^{t+1}_l प्राप्त करते हैं
- S^t_l की खोज करते समय, S^{t+1}_l का मूल्य m^{t+1}_l पर निर्धारित करते हैं

कार्रवाई चयन रणनीति:

a_root = argmax_a I^t_l(a)

जहां I^t_l(a) = {
    UCBscore(S^t_l, a),  यदि a ≠ a^t_l
    r^t_l + γm^{t+1}_l,  यदि a = a^t_l
}

जब S^{t+1}_l के अनुरूप कार्रवाई चुनते हैं, तो पूर्व-संग्रहीत मूल्य का सीधे उपयोग करते हैं, उप-वृक्ष खोज से बचते हैं।

2. संपूर्ण बफर पुनर्विश्लेषण (Entire-buffer Reanalyze)

डिज़ाइन प्रेरणा: पश्चदृश्य पुनर्विश्लेषण को बैच को छोटे उप-बैच में विभाजित करने की आवश्यकता है, जो समानांतरकरण लाभ को कम कर सकता है।

समाधान:

  1. संग्रह चरण सुधार: नीति नेटवर्क आउटपुट से सीधे नमूना कार्रवाई, MCTS चयन के बजाय
  2. आवधिक पुनर्विश्लेषण: प्रशिक्षण पुनरावृत्तियों की निर्धारित संख्या के बाद संपूर्ण बफर का पुनर्विश्लेषण करें, न कि हर पुनरावृत्ति पर छोटे बैच का

लाभ:

  • DQN की निश्चित लक्ष्य नेटवर्क तंत्र के समान, नीति लक्ष्य अपडेट आवृत्ति को कम करता है
  • सभी MCTS कॉल को पुनर्विश्लेषण प्रक्रिया में केंद्रित करता है, बड़े बैच समानांतरकरण का पूर्ण लाभ उठाता है
  • पुनर्विश्लेषण और प्रशिक्षण प्रक्रिया को अलग करता है, अधिक समानांतरकरण स्थान प्रदान करता है

सैद्धांतिक विश्लेषण

प्रमेय 1: समीकरण (2) की धारणाओं को पूरा करने वाले गैर-स्थिर बैंडिट के लिए, UCB मान के बजाय नमूना अनुमान का उपयोग करके विशिष्ट आर्म का मूल्यांकन करने से ET_i(n)/n → 0 सुनिश्चित होता है जब n → ∞।

यह प्रमेय पश्चदृश्य पुनर्विश्लेषण विधि की अभिसरण को साबित करता है, और कम खेद की ऊपरी सीमा है, जो दर्शाता है कि एल्गोरिदम इष्टतम आर्म के लिए अधिक केंद्रित दौरे वितरण उत्पन्न कर सकता है।

प्रायोगिक सेटअप

डेटासेट और वातावरण

  1. Atari वातावरण: 26 प्रतिनिधि गेम, उच्च-आयामी दृश्य इनपुट और असतत कार्रवाई स्थान के साथ
  2. DMControl सूट: ball_in_cup-catch और walker-stand दो निरंतर नियंत्रण कार्य
  3. बोर्ड गेम: Connect4 और Gomoku, विशेष स्थिति स्थान वाले रणनीति गेम

मूल्यांकन मेट्रिक्स

  • समय दक्षता: समान प्रदर्शन स्तर तक पहुंचने के लिए आवश्यक घड़ी समय
  • नमूना दक्षता: सफल नीति तक पहुंचने के लिए आवश्यक पर्यावरण इंटरैक्शन
  • खोज त्वरण: एकल MCTS का समय खपत और फ़ंक्शन कॉल संख्या

तुलना विधियां

  • MuZero: मूल MuZero एल्गोरिदम
  • EfficientZero: सुधारा हुआ MuZero वेरिएंट
  • ReZero-M: ReZero एकीकृत MuZero
  • ReZero-E: ReZero एकीकृत EfficientZero

कार्यान्वयन विवरण

  • पुनरावृत्ति अनुपात: 0.25
  • पुनर्विश्लेषण आवृत्ति: 1
  • बैच आकार: 256 (Atari), 64 (DMControl)
  • MCTS सिमुलेशन: 50
  • हार्डवेयर: एकल NVIDIA A100 GPU, 30 CPU कोर, 120 GiB मेमोरी

प्रायोगिक परिणाम

मुख्य परिणाम

समय दक्षता में सुधार:

  • अधिकांश गेम में, ReZero को आधारभूत विधियों की तुलना में 2-4 गुना कम घड़ी समय की आवश्यकता है
  • Pong गेम: ReZero-M 1.0±0.1 घंटे बनाम MuZero 4.0±0.5 घंटे
  • MsPacman गेम: ReZero-M 1.4±0.2 घंटे बनाम MuZero 6.9±0.3 घंटे
  • Connect4 गेम: ReZero-M 5.5±0.6 घंटे बनाम MuZero 9.1±0.8 घंटे

नमूना दक्षता संरक्षण: सभी परीक्षण वातावरणों में, ReZero आधारभूत विधियों के साथ तुलनीय या बेहतर नमूना दक्षता बनाए रखता है।

विलोपन प्रयोग

1. पुनर्विश्लेषण आवृत्ति प्रभाव

पुनर्विश्लेषण आवृत्ति {0, 1/3, 1, 2} के प्रभाव का परीक्षण किया गया:

  • उपयुक्त पुनर्विश्लेषण आवृत्ति प्रदर्शन में स्पष्ट कमी के बिना समय खपत को बचा सकती है
  • आवृत्ति 1 पर समय और नमूना दक्षता के बीच सर्वोत्तम संतुलन प्राप्त होता है

2. पश्चदृश्य पुनर्विश्लेषण प्रभाव

विस्तृत आंकड़े दिखाते हैं:

  • औसत खोज समय: ReZero-M 0.69±0.02ms बनाम MuZero 1.08±0.09ms
  • ट्री सर्च कॉल: ReZero-M 6089 बनाम MuZero 13284
  • गतिशील मॉडल कॉल: ReZero-M 122 बनाम MuZero 256

केस विश्लेषण

खिलौना केस सत्यापन: 7×7 ग्रिड दुनिया में प्रयोग सीधे उप-वृक्ष खोज को छोड़ने के त्वरण प्रभाव को प्रदर्शित करते हैं। अंतिम बिंदु से जितना दूर स्थिति है, खोज समय उतना लंबा है, रूट नोड मूल्य सहायता का उपयोग करने के बाद खोज समय सामान्यतः कम हो जाता है।

प्रायोगिक निष्कर्ष

  1. पश्चदृश्य पुनर्विश्लेषण न केवल एकल खोज गति में सुधार करता है, बल्कि नमूना दक्षता में भी सुधार करता है
  2. संपूर्ण बफर पुनर्विश्लेषण MCTS कॉल की संख्या को प्रभावी ढंग से कम करता है
  3. विधि विभिन्न प्रकार के निर्णय वातावरण में सुसंगत त्वरण प्रभाव दिखाती है

संबंधित कार्य

MCTS एल्गोरिदम विकास

  • AlphaGo/AlphaZero: MCTS को गहन सुदृढ़ शिक्षा के साथ जोड़ता है, बोर्ड गेम में सफलता प्राप्त करता है
  • MuZero: अज्ञात पर्यावरण मॉडल परिदृश्य तक विस्तार, व्यापक अनुप्रयोग
  • बाद के सुधार: EfficientZero नमूना दक्षता में सुधार करता है, MuZero Unplugged ऑफलाइन सेटिंग तक विस्तार करता है

MCTS त्वरण अनुसंधान

  • SpeedyZero: समानांतर सिस्टम डिज़ाइन के माध्यम से समय खपत को कम करता है, लेकिन अधिक कम्प्यूटेशनल संसाधनों की आवश्यकता है
  • PTSAZero: स्थिति अमूर्तता के माध्यम से खोज स्थान को संपीड़ित करता है
  • KataGo: भोली सूचना पुनः उपयोग तकनीकों का उपयोग करता है, लेकिन यह पेपर की पश्चदृश्य विधि मौलिक रूप से भिन्न है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. ReZero ने MCTS एल्गोरिदम की अत्यधिक घड़ी समय खपत की समस्या को सफलतापूर्वक हल किया है
  2. पश्चदृश्य पुनर्विश्लेषण और संपूर्ण बफर पुनर्विश्लेषण का सहक्रियात्मक प्रभाव समय दक्षता में काफी सुधार करता है
  3. विधि सामान्य है, विभिन्न MCTS एल्गोरिदम वेरिएंट पर लागू की जा सकती है
  4. नमूना दक्षता को बनाए रखते हुए 2-4 गुना समय त्वरण प्राप्त किया गया है

सीमाएं

  1. एकल-मशीन सेटअप सीमा: वर्तमान प्रयोग मुख्य रूप से एकल-मशीन वातावरण में किए गए हैं, वितरित प्रशिक्षण में अनुकूलन की गुंजाइश है
  2. पर्यावरण कवरेज: निरंतर नियंत्रण वातावरण के प्रयोग अपेक्षाकृत सीमित हैं, अधिक व्यापक बेंचमार्क परीक्षण की आवश्यकता है
  3. सैद्धांतिक विश्लेषण: हालांकि अभिसरण प्रमाण प्रदान किया गया है, वास्तविक जटिल वातावरण में सैद्धांतिक गारंटी को आगे के अनुसंधान की आवश्यकता है

भविष्य की दिशाएं

  1. वितरित अनुकूलन: ReZero को वितरित सुदृढ़ शिक्षा प्रशिक्षण में लागू करना
  2. ऑफलाइन शिक्षा: MuZero Unplugged के साथ संयोजन, ऑफलाइन डेटासेट पर अनुप्रयोग
  3. आधार मॉडल: RT-X जैसे बड़े पैमाने के डेटासेट के साथ निर्णय आधार मॉडल का निर्माण
  4. भारित नमूनाकरण: बफर में नमूनों के भाग को प्राथमिकता देने के लिए अधिक तर्कसंगत तरीके का उपयोग करना

गहन मूल्यांकन

शक्तियां

  1. मजबूत नवीनता: पश्चदृश्य पुनर्विश्लेषण MCTS त्वरण के लिए एक नई सोच है, सैद्धांतिक आधार दृढ़ है
  2. उच्च व्यावहारिक मूल्य: महत्वपूर्ण समय त्वरण प्रभाव MCTS एल्गोरिदम के व्यावहारिक अनुप्रयोग के लिए महत्वपूर्ण है
  3. अच्छी सामान्यता: ढांचा डिज़ाइन इसे विभिन्न MCTS एल्गोरिदम में निर्बाध रूप से एकीकृत करने की अनुमति देता है
  4. व्यापक प्रयोग: विभिन्न पर्यावरण प्रकारों में विधि की प्रभावशीलता को सत्यापित किया गया है, विस्तृत विलोपन प्रयोग सहित

कमियां

  1. सैद्धांतिक विश्लेषण की गहराई: हालांकि अभिसरण प्रमाण प्रदान किया गया है, जटिल वातावरण के लिए सैद्धांतिक गारंटी को अभी भी मजबूत करने की आवश्यकता है
  2. वितरित परिदृश्य: बहु-मशीन बहु-कार्ड वातावरण में सत्यापन और अनुकूलन की कमी
  3. निरंतर नियंत्रण: निरंतर कार्रवाई स्थान में प्रयोग अपेक्षाकृत सीमित हैं
  4. दीर्घकालिक प्रभाव: प्रशिक्षण स्थिरता और अंतिम प्रदर्शन पर दीर्घकालिक प्रभाव को अधिक विश्लेषण की आवश्यकता है

प्रभाव

  1. शैक्षणिक योगदान: MCTS त्वरण के लिए नई अनुसंधान दिशा प्रदान करता है, सिद्धांत और व्यवहार दोनों पर ध्यान केंद्रित करता है
  2. व्यावहारिक मूल्य: MCTS एल्गोरिदम तैनाती की मुख्य बाधा को सीधे हल करता है
  3. पुनरुत्पादनीयता: पूर्ण ओपन-सोर्स कार्यान्वयन प्रदान करता है, अनुसंधान समुदाय के उपयोग और विस्तार को सुविधाजनक बनाता है

लागू परिदृश्य

  1. गेम AI: बोर्ड गेम, वीडियो गेम आदि जिन्हें वास्तविक समय निर्णय की आवश्यकता है
  2. रोबोट नियंत्रण: ऑनलाइन योजना की आवश्यकता वाले रोबोट कार्य
  3. स्वायत्त ड्राइविंग: वास्तविक समय पथ योजना और निर्णय निर्माण
  4. वित्तीय व्यापार: उच्च-आवृत्ति व्यापार में तेजी से निर्णय

संदर्भ

  1. Schrittwieser, J., et al. (2019). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588, 604-609.
  2. Silver, D., et al. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815.
  3. Ye, W., et al. (2021). Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34, 25476-25488.
  4. Mei, Y., et al. (2023). Speedyzero: Mastering atari with limited data and time. ICLR 2023.

समग्र मूल्यांकन: यह एक उच्च गुणवत्ता का अनुसंधान पेपर है जो MCTS एल्गोरिदम की व्यावहारिक तैनाती की बाधा के लिए एक नवीन और व्यावहारिक समाधान प्रस्तावित करता है। विधि डिज़ाइन चतुर है, सैद्धांतिक आधार दृढ़ है, प्रायोगिक सत्यापन व्यापक है, और यह MCTS एल्गोरिदम को व्यावहारिक अनुप्रयोगों में लोकप्रिय बनाने के लिए महत्वपूर्ण मूल्य रखता है।