Bandit Based Pure Exploration of Greedy Learning
Tian Lin, Jian Li, Wei Chen
International Journal of Web Applications, Vol. 15, No. 1, 2023.
DOI: https://doi.org/10.6025/ijwa/2023/15/1/1-11
Link: https://www.dline.info/ijwa/fulltext/v15n1/ijwav15n1_1.pdf
Abstract:
Combinatorial optimization has many greedy algorithms. Using the stochastic based greedy algorithm, we have studied the online learning issues. Primarily, we compared the quasi- greedy regret as a metric for learning and equated with the offline greedy algorithms. Multi-armed bandit based pure exploration at each level of greedy learning is used to develop the two step online greedy algorithm with semi-bandit feed backs. This process works out for regret metrics well. The use of general class of combinatorial structures and reward function permit greedy solutions. We have tested the procedures with the parameters of other problems.