Leader-Follower semi-Markov Decision Problems: Theoretical Framework and Approximate Solution
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 111-118
Abstract
Leader-follower problems are hierarchical decision problems in which a leader uses incentives to induce certain desired behavior among a set of self-interested followers. Dynamic leader-follower problems extend this structure to multi-period decision situations. In this work we propose a Markov decision process (MDP) framework for a class of dynamic leader-follower problems that have important applications and discuss their approximate solution using reinforcement learning (RL). In these problems, the leader makes incentive decisions intermittently while the followers make their decisions in every period. Our theoretical framework and computational approach are based on the observation that such dynamic problems can be thought of as consisting of two coupled sequential decision processes, that of the leader and of the followers. In our formulation, the leader's decision problem that has the structure of a single-agent semi-Markov decision process (SMDP), and the followers' sequential decision problem structured as a stochastic game (multiagent competitive MDP) operate over the same state space. We call this MDP framework a leader-follower semi-Markov decision process (LFSMDP). We consider approximate solution of these problems using RL and demonstrate the solution approach in the special case where the followers' stochastic game is a repeated game.Keywords
This publication has 16 references indexed in Scilit:
- Reinforcement learning for long-run average costEuropean Journal of Operational Research, 2004
- Convergent multiple-timescales reinforcement learning algorithms in normal form gamesThe Annals of Applied Probability, 2003
- Multitime scale Markov decision processesIEEE Transactions on Automatic Control, 2003
- Multiagent learning using a variable learning rateArtificial Intelligence, 2002
- Performance-Based Incentives in a Dynamic Principal-Agent ModelManufacturing & Service Operations Management, 2000
- 10.1162/jmlr.2003.4.6.1039Applied Physics Letters, 2000
- Solving Semi-Markov Decision Problems Using Average Reward Reinforcement LearningManagement Science, 1999
- Stochastic approximation with two time scalesSystems & Control Letters, 1997
- Optimal and near-optimal incentive strategies in the hierarchical control of markov chainsAutomatica, 1985
- An incentive model of duopoly with government coordinationAutomatica, 1981