Localized exploration in contextual dynamic pricing achieves dimension-free regret

• URL: http://arxiv.org/abs/2412.19252v1
• Date: Thu, 26 Dec 2024 15:29:58 GMT
• Title: Localized exploration in contextual dynamic pricing achieves dimension-free regret
• Abstract summary: We study the problem of contextual dynamic pricing with a linear demand model.<n>We propose a novel localized exploration-then-commit algorithm.<n>We show how to balance the exploration and exploitation when the horizon is limited.
• Score: 9.130911865751099
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of contextual dynamic pricing with a linear demand model. We propose a novel localized exploration-then-commit (LetC) algorithm which starts with a pure exploration stage, followed by a refinement stage that explores near the learned optimal pricing policy, and finally enters a pure exploitation stage. The algorithm is shown to achieve a minimax optimal, dimension-free regret bound when the time horizon exceeds a polynomial of the covariate dimension. Furthermore, we provide a general theoretical framework that encompasses the entire time spectrum, demonstrating how to balance exploration and exploitation when the horizon is limited. The analysis is powered by a novel critical inequality that depicts the exploration-exploitation trade-off in dynamic pricing, mirroring its existing counterpart for the bias-variance trade-off in regularized regression. Our theoretical results are validated by extensive experiments on synthetic and real-world data.

Related papers

• DiPO: Disentangled Perplexity Policy Optimization for Fine-grained Exploration-Exploitation Trade-Off [87.58233482504308]
  Reinforcement Learning with Verifiable Rewards (RLVR) has catalyzed significant advances in the reasoning capabilities of Large Language Models (LLMs)<n>This paper fully analyze the exploration and exploitation dilemma of extremely hard and easy samples during the training and propose a new fine-grained trade-off mechanism.
  arXiv  Detail & Related papers  (2026-04-15T14:12:10Z)
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• How to Set the Learning Rate for Large-Scale Pre-training? [73.03133634525635]
  We formalize this investigation into two distinct research paradigms: Fitting and Transfer.<n>Within the Fitting Paradigm, we introduce a Scaling Law for search factor, effectively reducing the search complexity from O(n3) to O(n*C_D*C_) via predictive modeling.<n>We extend the principles of $$Transfer to the Mixture of Experts (MoE) architecture, broadening its applicability to encompass model depth, weight decay, and token horizons.
  arXiv  Detail & Related papers  (2026-01-08T15:55:13Z)
• Infrequent Exploration in Linear Bandits [39.8867004581646]
  We introduce a simple and practical framework, INFEX, explicitly designed for infrequent exploration.<n> INFEX executes a base exploratory policy according to a given schedule while predominantly choosing greedy actions in between.<n>Our theoretical analysis demonstrates that INFEX achieves instance-dependent regret matching standard provably efficient algorithms.
  arXiv  Detail & Related papers  (2025-10-29T22:25:43Z)
• Utility Fairness in Contextual Dynamic Pricing with Demand Learning [23.26236046836737]
  This paper introduces a novel contextual bandit algorithm for personalized pricing under utility fairness constraints. Our approach, which incorporates dynamic pricing and demand learning, addresses the critical challenge of fairness in pricing strategies.
  arXiv  Detail & Related papers  (2023-11-28T05:19:23Z)
• When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning [62.00672284480755]
  This paper aims to recover the structure of rewards and environment dynamics that underlie observed actions in a fixed, finite set of demonstrations from an expert agent. Accurate models of expertise in executing a task has applications in safety-sensitive applications such as clinical decision making and autonomous driving.
  arXiv  Detail & Related papers  (2023-02-15T04:14:20Z)
• Latent State Marginalization as a Low-cost Approach for Improving Exploration [79.12247903178934]
  We propose the adoption of latent variable policies within the MaxEnt framework. We show that latent variable policies naturally emerges under the use of world models with a latent belief state. We experimentally validate our method on continuous control tasks, showing that effective marginalization can lead to better exploration and more robust training.
  arXiv  Detail & Related papers  (2022-10-03T15:09:12Z)
• Calibration of Derivative Pricing Models: a Multi-Agent Reinforcement Learning Perspective [3.626013617212667]
  One of the most fundamental questions in quantitative finance is the existence of continuous-time diffusion models that fit market prices of a given set of options. Our contribution is to show how a suitable game theoretical formulation of this problem can help solve this question by leveraging existing developments in modern deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2022-03-14T05:34:00Z)
• Globally Convergent Policy Search over Dynamic Filters for Output Estimation [64.90951294952094]
  We introduce the first direct policy search algorithm convex which converges to the globally optimal $textitdynamic$ filter. We show that informativity overcomes the aforementioned degeneracy.
  arXiv  Detail & Related papers  (2022-02-23T18:06:20Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• Geometric Entropic Exploration [52.67987687712534]
  We introduce a new algorithm that maximises the geometry-aware Shannon entropy of state-visits in both discrete and continuous domains. Our key theoretical contribution is casting geometry-aware MSVE exploration as a tractable problem of optimising a simple and novel noise-contrastive objective function. In our experiments, we show the efficiency of GEM in solving several RL problems with sparse rewards, compared against other deep RL exploration approaches.
  arXiv  Detail & Related papers  (2021-01-06T14:15:07Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
  Contextual multi-armed bandit (MAB) achieves cutting-edge performance on a variety of problems. In this paper, we propose a hierarchical adaptive contextual bandit method (HATCH) to conduct the policy learning of contextual bandits with a budget constraint.
  arXiv  Detail & Related papers  (2020-04-02T17:04:52Z)
• Dynamic Subgoal-based Exploration via Bayesian Optimization [7.297146495243708]
  Reinforcement learning in sparse-reward navigation environments is challenging and poses a need for effective exploration. We propose a cost-aware Bayesian optimization approach that efficiently searches over a class of dynamic subgoal-based exploration strategies. An experimental evaluation demonstrates that the new approach outperforms existing baselines across a number of problem domains.
  arXiv  Detail & Related papers  (2019-10-21T04:24:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.