Computer Science – Learning
Scientific paper
2011-04-28
Computer Science
Learning
Scientific paper
In this paper,we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. However, it is known be PSPACE-Hard to approximate to any non-trivial factor. Thus the optimality is very difficult to obtain due to its high complexity. A natural method is to obtain the greedy policy considering its stability and simplicity. However, the greedy policy will result in the optimality loss for its intrinsic myopic behavior generally. In this paper, by analyzing one class of so-called standard reward function, we establish the closed-form condition about the discounted factor \beta such that the optimality of the greedy policy is guaranteed under the discounted expected reward criterion, especially, the condition \beta = 1 indicating the optimality of the greedy policy under the average accumulative reward criterion. Thus, the standard form of reward function can easily be used to judge the optimality of the greedy policy without any complicated calculation. Some examples in cognitive radio networks are presented to verify the effectiveness of the mathematical result in judging the optimality of the greedy policy.
Chen Lin
Liu Quan
Wang Kehao
No associations
LandOfFree
On Optimality of Greedy Policy for a Class of Standard Reward Function of Restless Multi-armed Bandit Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Optimality of Greedy Policy for a Class of Standard Reward Function of Restless Multi-armed Bandit Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Optimality of Greedy Policy for a Class of Standard Reward Function of Restless Multi-armed Bandit Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-449780