Abstract: We reformulate the widths problem in the framework of information-based complexity theory and study the Kolmogorov width and linear width for the generalized Besov classes in the randomized setting. Applying the discretization technique and some properties of pseudo-s-scale, we determine the exact asymptotic orders of these widths on these classes for certain values of the parameters p, q, θ. Our results show that the Monte Carlo methods lead to a better convergence rate than that of the deterministic ones for some parameters p, q. The maximal gain can reach a factor n-1/2 roughly.