Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path Based Formulation.
Vineet GoyalRajan UdwaniPublished in: CoRR (2019)
Keyphrases
- competitive ratio
- online algorithms
- monte carlo sampling
- single machine
- lower bound
- online learning
- average case
- optimal strategy
- reward function
- initially unknown
- worst case
- processing times
- scheduling problem
- learning algorithm
- asymptotically optimal
- convergence rate
- reinforcement learning
- completion times
- markov decision processes
- state space
- special case
- combinatorial optimization
- decision problems
- optimal policy