Information-Gain Complexity
A quantity in linear bandits that characterizes instance-dependent optimality, measuring the cost required to obtain sufficient information to distinguish the optimal action given a fixed action set and unknown parameters.
Timeline (last 90 days)
IAFTRL's regret upper bound in stochastic environments is ~O(C* log T), where C* is the information-acquisition complexity.
IAFTRL dynamically adjusts the regularization strength, incorporating information-acquisition complexity into the design of the FTRL regularization term, thereby automatically adapting to instance difficulty.
The information-acquisition complexity C* is a key quantity characterizing instance-dependent optimal regret for linear bandits, related to the geometric structure of the action set (such as the gaps between the optimal action and suboptimal actions) and to the variance of parameter estimation.
In stochastic linear bandits, the instance-dependent optimal regret lower bound can usually be expressed in the form Ω(C* log T), matching IAFTRL's upper bound (up to logarithmic factors).
All Facts (4)
IAFTRL's regret upper bound in stochastic environments is ~O(C* log T), where C* is the information-acquisition complexity.
50%UnverifiedIAFTRL dynamically adjusts the regularization strength, incorporating information-acquisition complexity into the design of the FTRL regularization term, thereby automatically adapting to instance difficulty.
50%UnverifiedThe information-acquisition complexity C* is a key quantity characterizing instance-dependent optimal regret for linear bandits, related to the geometric structure of the action set (such as the gaps between the optimal action and suboptimal actions) and to the variance of parameter estimation.
50%UnverifiedIn stochastic linear bandits, the instance-dependent optimal regret lower bound can usually be expressed in the form Ω(C* log T), matching IAFTRL's upper bound (up to logarithmic factors).
50%