तकनीकी सारांश: अनुकूलन क्षमता और इष्टतमता के साथ गैर-स्थिर गतिशील मूल्य निर्धारण (Non-Stationary Dynamic Pricing with Adaptivity and Optimality)

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र गैर-स्थिरता के तहत प्रासंगिक गतिशील मूल्य निर्धारण (contextual dynamic pricing) की समस्या को संबोधित करता है। एक फर्म $T$ अनुक्रमिक रूप से आने वाले उपभोक्ताओं को उत्पाद बेचती है। प्रत्येक समय $t$ पर, एक संदर्भ वेक्टर (context vector) $z_t \in \mathbb{R}^d$ (जो उत्पाद और उपभोक्ता की जानकारी को दर्शाता है) देखा जाता है। फर्म एक मूल्य $p_t \in [l, u]$ निर्धारित करती है और मांग प्रतिक्रिया $y_t$ का अवलोकन करती है।

माना गया मांग मॉडल एक सामान्यीकृत रैखिक मॉडल (Generalized Linear Model - GLM) है जिसमें एक अज्ञात पैरामीटर $\theta_t \in \mathbb{R}^{2d}$ समय के साथ विकसित होता है। विशेष रूप से, अपेक्षित मांग इस प्रकार दी गई है:
$$\mathbb{E}[y_t | x_t, \theta_t] = \psi'(x_t^\top \theta_t) = \psi'(z_t^\top \alpha_t - (z_t^\top \beta_t)p_t)$$
जहाँ $x_t = (z_t^\top, -p_t z_t^\top)^\top$ है।

मुख्य चुनौती यह है कि पैरामीटर अनुक्रम $\{\theta_t\}_{t=1}^T$ गैर-स्थिर (non-stationary) है और इसका स्वरूप फर्म के लिए अज्ञात है। शोध पत्र दो अलग-अलग गैर-स्थिरता शासन (regimes) पर विचार करता है:

1. संरचित गैर-स्थिरता (Structured Non-Stationarity): पैरामीटर खंडवार स्थिर (piecewise constant) हैं जिनमें $s_T - 1$ अज्ञात परिवर्तन-बिंदु (change-points) हैं।
2. असंरचित गैर-स्थिरता (Unstructured Non-Stationarity): पैरामीटर कुल भिन्नता बजट $V_T$ के अधीन सुचारू रूप से या मनमाने ढंग से बदलते हैं।

उद्देश्य एक ऐसी मूल्य निर्धारण नीति डिजाइन करना है जो पश्चग्रह (regret) को कम करे, जिसे एक सर्वज्ञ (clairvoyant) व्यक्ति की तुलना में संचयी राजस्व हानि के रूप में परिभाषित किया गया है, जो वास्तविक अनुक्रम $\{\theta_t\}$ और प्रत्येक चरण पर इष्टतम मूल्य $p_t^*$ को जानता हो। महत्वपूर्ण रूप से, एल्गोरिदम को अनुकूलनीय (adaptive) होना चाहिए, जिसका अर्थ है कि इसे यह जाने बिना कि वातावरण संरचित है या असंरचित, या $s_T$ या $V_T$ के विशिष्ट मान क्या हैं, इष्टतम प्रदर्शन प्राप्त करना चाहिए।

2. कार्यप्रणाली: MCP-DP एल्गोरिदम

लेखक मल्टीस्केल चेंज-पॉइंट डिटेक्शन आधारित डायनेमिक प्राइसिंग (MCP-DP) एल्गोरिदम का प्रस्ताव करते हैं। यह एल्गोरिदम युगों (epochs) में कार्य करता है, जिन्हें आगे डायडिक ब्लॉकों (dyadic blocks) में विभाजित किया गया है। प्रत्येक ब्लॉक के भीतर, यह एक एक्सप्लोर-देन-कमिट (Explore-Then-Commit - ETC) रणनीति को एक नवीन मल्टीस्केल सैंपलिंग स्कीम (MSS) और एक लाइकलीहुड-रेशियो टेस्ट (LRT) के साथ जोड़ता है।

मुख्य घटक:

• संदर्भ मॉडल अनुमान (Reference Model Estimation): एक ब्लॉक के प्रारंभ में, एल्गोरिदम पिछले ब्लॉक में संचित मूल्य अन्वेषण सेट (price exploration set) से अधिकतम संभाव्यता अनुमान (Maximum Likelihood Estimation - MLE) का उपयोग करके एक संदर्भ पैरामीटर $\hat{\theta}$ का अनुमान लगाता है।
• स्थानीयकृत मूल्य अन्वेषण (Localized Price Exploration): समान मूल्य नमूनाकरण (uniform price sampling) के बजाय, MCP-DP लालची मूल्य $p^*(z_t, \hat{\theta})$ के आसपास एक स्थानीयकृत विक्षेपण योजना (localized perturbation scheme) का उपयोग करता है। यह अन्वेषण के दौरान पश्चग्रह को कम करता है और साथ ही सांख्यिकीय वैधता (यह सुनिश्चित करना कि डिज़ाइन मैट्रिक्स सुव्यवस्थित रहे) बनाए रखता है।
• मल्टीस्केल शेड्यूलिंग (MSS): अज्ञात परिमाण और समय के परिवर्तनों का पता लगाने के लिए, MSS प्रत्येक ब्लॉक के भीतर विभिन्न लंबाई (स्केल्स) के अन्वेषण अंतराल को बेतरतीब ढंग से शेड्यूल करता है। बड़े, अचानक परिवर्तनों का पता लगाने के लिए छोटे अंतराल अधिक बार नमूने लेते हैं, जबकि लंबे अंतराल छोटे, क्रमिक बदलावों का पता लगाते हैं।
• लाइकलीहुड-रेशियो टेस्ट (LRT): प्रत्येक निर्धारित अन्वेषण अंतराल के अंत में, एल्गोरिदम पिछले संदर्भ मॉडल $\hat{\theta}_{pre}$ और उस अंतराल पर फिट किए गए नए MLE $\hat{\theta}_J$ के बीच एक LRT करता है।
  • टेस्ट सांख्यिकी $\Lambda_J(\hat{\theta}_{pre}) = L_J(\hat{\theta}_{pre}) - L_J(\hat{\theta}_J)$ है।
  • यदि सांख्यिकी एक थ्रेशोल्ड $\gamma \propto d \log(dT)$ से अधिक हो जाती है, तो एल्गोरिदम मानता है कि एक महत्वपूर्ण परिवर्तन हुआ है, वर्तमान युग को समाप्त करता है, और एक नए युग के साथ पुनरारंभ करता है।
• अनुकूलन क्षमता (Adaptivity): अन्वेषण की मल्टीस्केल प्रकृति एल्गोरिदम को बिना यह जाने कि विशिष्ट शासन या पैरामीटर ($s_T, V_T$) क्या हैं, दोनों (संरचित और असंरचित) स्थितियों को एक साथ संभालने की अनुमति देती है।

3. मुख्य योगदान

1. MCP-DP एल्गोरिदम और पश्चग्रह सीमाएँ (Regret Bounds)

शोध पत्र पेश करता है कि MCP-DP पहला डायनेमिक प्राइसिंग एल्गोरिदम है जो संरचित और असंरचित दोनों प्रकार की गैर-स्थिरता के प्रति अनुकूलनीय (adaptive) सिद्ध हुआ है।

• पश्चग्रह ऊपरी सीमा (Regret Upper Bound): एल्गोरिदम निम्नलिखित क्रम का पश्चग्रह प्राप्त करता है:
  $$\tilde{O}\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$
  यह सीमा "बेस्ट-ऑफ-बौथ-वर्ल्ड्स" दर का प्रतिनिधित्व करती है, जो शुद्ध रूप से संरचित और शुद्ध रूप से असंरचित सेटिंग्स के लिए इष्टतम दरों को एक साथ मैच करती है।
• पूर्व ज्ञान की आवश्यकता नहीं: एल्गोरिदम को परिवर्तन-बिंदुओं की संख्या $s_T$, भिन्नता बजट $V_T$, न्यूनतम परिवर्तन आकार, या खंड की लंबाई के ज्ञान की आवश्यकता नहीं होती है।

2. डिज़ाइन-समायोजित भिन्नता बजट (Design-Adjusted Variation Budget)

लेखक एक नया अवधारणा डिज़ाइन-समायोजित भिन्नता बजट ($V_T$) पेश करते हैं। मौजूदा भिन्नता बजटों के विपरीत, जो पैरामीटर्स के बीच कच्चे अंतर $\|\theta_t - \theta_{t-1}\|$ को मापते हैं, $V_T$ भिन्नता को संदर्भ वितरण (विशेष रूप से डिज़ाइन मैट्रिक्स $\Sigma_z$) द्वारा भारित (weight) करता है।

• महत्व: यह प्रासंगिक सेटिंग्स में गैर-स्थिरता का अधिक सटीक लक्षण वर्णन प्रदान करता है। यह इस अंतर्ज्ञान को पकड़ता है कि संदर्भ $z_t$ द्वारा कम प्रतिनिधित्व किए गए दिशाओं में मापदंडों में परिवर्तन का मांग और पश्चग्रह पर कम प्रभाव पड़ता है। यह परिभाषा साहित्य में मौजूदा सीमाओं का सामान्यीकरण और उसे कड़ा करती है।

3. मिनिमैक्स लोअर बाउंड्स (Minimax Lower Bounds)

शोध पत्र गैर-स्थिर प्रासंगिक डायनेमिक प्राइसिंग के लिए एक नया मिनिमैक्स लोअर बाउंड स्थापित करता है:
$$\Omega\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$

• आयामी निर्भरता (Dimensionality Dependence): यह डायनेमिक प्राइसिंग साहित्य में पहला लोअर बाउंड है जो स्पष्ट रूप से दोनों मामलों (संरचित और असंरचित) के लिए संदर्भ आयाम $d$ पर निर्भरता को वर्णित करता है।
• तकनीकी नवीनता: इसका प्रमाण $T \to \infty$ होने पर विचलित होने वाले आयाम $d$ को संभालने के लिए असौड के लेम्मा (Assouad's lemma) पर आधारित एक नए निर्माण का उपयोग करता है, जो पश्चग्रह को मल्टीपल-क्लासिफिकेशन एरर समस्या से जोड़ता है।

4. सैद्धांतिक और सांख्यिकीय आधार

• उच्च-संभाव्यता MLE सीमाएँ: लेखक गैर-स्थिरता के तहत मिश्रण GLMs के लिए MLE के भविष्यवाणी त्रुटि पर एक नया उच्च-संभाव्यता ऊपरी सीमा प्राप्त करते हैं। यह परिणाम स्वतंत्र रूप से भी महत्वपूर्ण है और LRT की इष्टतमता का आधार बनता है।
• LRT एक पश्चग्रह सरोगेट के रूप में: शोध पत्र सिद्ध करता है कि LRT सांख्यिकी अप्रत्यक्ष (unobserved) शोषण पश्चग्रह (exploitation regret) के लिए एक सरोगेट के रूप में कार्य करती है, जिससे एल्गोरिदम को वास्तविक मापदंडों को जाने बिना अत्यधिक पश्चग्रह का पता लगाने की अनुमति मिलती है।

4. परिणाम और अनुभवजन्य सत्यापन

विभिन्न संदर्भ आयामों ($d$) और समय क्षितिज ($T$) के साथ रैखिक और लॉजिस्टिक मांग मॉडल पर व्यापक संख्यात्मक प्रयोग किए गए।

• बेसलाइन सेटिंग्स: MCP-DP की तुलना CPDP (अचानक परिवर्तनों के लिए अनुकूलित) और MWDP (सुचारू परिवर्तनों के लिए अनुकूलित) से की गई।
  • स्थिर सेटिंग्स में, MCP-DP ने CPDP का प्रदर्शन किया और MWDP से बेहतर प्रदर्शन किया।
  • अचानक परिवर्तन सेटिंग्स में, MCP-DP ने CPDP का मुकाबला किया।
  • सुचारू परिवर्तन सेटिंग्स में, MCP-DP ने MWDP का मुकाबला किया।
  • महत्वपूर्ण रूप से, MCP-DP ने बिना ट्यूनिंग के सभी शासन में मजबूत प्रदर्शन बनाए रखा, जबकि बेंचमार्क अपने विशिष्ट धारणाओं के मेल न खाने पर विफल रहे।
• जटिल सेटिंग्स: प्रतिकूल परिवर्तन पैटर्न (जहाँ CPDP का निश्चित शेड्यूल विफल हो जाता है) या विचलित परिवर्तन गणना/बजट वाले परिदृश्यों में, MCP-DP ने गैर-अनुकूल बेंचमार्क की तुलना में बेहतर मजबूती और कम पश्चग्रह प्रदर्शित किया।
• डिज़ाइन-समायोजित बजट सत्यापन: विभिन्न संदर्भ वितरणों (Z1 बनाम Z2) के साथ प्रयोगों ने पुष्टि की कि डिज़ाइन-समायोजित बजट के विरुद्ध मापे जाने पर MCP-DP का प्रदर्शन स्थिर रहता है, जबकि मानक $L_2$ भिन्नता बजट स्थिरता की व्याख्या करने में विफल रहे।

5. महत्व और दावे

शोध पत्र डायनेमिक प्राइसिंग साहित्य में एक लंबे समय से चली आ रही कमी को भरने का दावा करता है। गैर-स्थिर मूल्य निर्धारण पर पिछले कार्यों में अनुकूलन क्षमता का अभाव था, जिन्हें अचानक बनाम सुचारू परिवर्तनों के लिए अलग-अलग एल्गोरिदम की आवश्यकता थी और अक्सर परिवर्तन के परिमाण या बजट के ज्ञान की आवश्यकता होती थी।

• पहला अनुकूल एल्गोरिदम: MCP-DP को एक एकल, अनुकूल ढांचे के भीतर बिना किसी पूर्व ज्ञान के (जैसे $s_T$ या $V_T$) दोनों प्रकार की गैर-स्थिरता के लिए इष्टतम पश्चग्रह दर प्राप्त करने वाले पहले एल्गोरिदम के रूप में प्रस्तुत किया गया है।
• इष्टतमता: एल्गोरिदम को (लॉगारिदमिक कारकों तक) मिनिमैक्स इष्टतम दिखाया गया है, जो नए प्राप्त लोअर बाउंड से मेल खाता है।
• पद्धतिगत प्रगति: यह कार्य रेखांकित करता है कि मौजूदा अनुकूल बैंडिट साहित्य (जैसे स्विचिंग बैंडिट) को निरंतर क्रिया स्थान (continuous action space) और इस तथ्य के कारण सीधे डायनेमिक प्राइसिंग पर लागू नहीं किया जा सकता है कि "सर्वश्रेष्ठ हाथ" (इष्टतम मूल्य) संदर्भ के साथ बदलता है। प्रस्तावित LRT-आधारित दृष्टिकोण विशेष रूप से संदर्भ वितरण के सापेक्ष मूल्य निर्धारण नीति के पश्चग्रह को ट्रैक करके इस समस्या का समाधान करता है।

लेखक उल्लेख करते हैं कि जबकि वर्तमान कार्य स्टोकेस्टिक संदर्भों को मानता है, पद्धति को प्रतिकूल (adversarial) संदर्भों तक विस्तारित करना एक भविष्य की दिशा है, क्योंकि वर्तमान LRT सफलता डिज़ाइन मैट्रिक्स की स्टोकेस्टिक प्रकृति पर निर्भर करती है।